I think this was one of the number theory proofs in Euclid, so it’s been known for millennia.
By way of illustration, say you have 2^n - 1, for some n that isn’t prime. In base 2, that number will be written as n 1s in a row. For instance, 2^15 - 1 = 111111111111111. But since 15 is composite, I can group those 1s into groups of equal size: Say, 111 111 111 111 111. Which means that 2^15 - 1 = 1001001001*111.
Here is something to ponder: suppose I write down a number. You can check whether it is prime or composite in polynomial time (in terms of the number of digits). But if you want to factor the number [a composite one]… well, how are you going to do it fast? It does not seem so easy. That is the point.
Actually, it’s not at all strange to skip primes. Euclid’s method for proving that there is no largest prime implies a method of finding new primes that may very well skip primes.
Euclid’s method - take a list of primes (say 2, 3, 5), multiply them together (you get 30) and add 1. The result, 31, is guaranteed to be either a prime (it is!) or the product of primes not on your previous list, but it’s not guaranteed to be the next largest prime at all (in this case, you skipped 7, 11, 13, 17, 19, 23 and 29)
The above discussions hint at, but do not say explicitly, this: Yes, if p is composite in 2^p-1, then 2^p-1 must be composite. BUT if p is prime, then 2^p-1 MIGHT or MIGHT NOT be prime. In that case, it remains a candidate but must be further tested.
50-some years ago, a friend challenged me to prove this. It took me about 90 seconds to come up with exactly this proof.
I recently discovered the largest prime number (no, it’s not Mersenne) which, unfortunately, the margin of this post is too narrow to contain.