An Interesting Thing About Primes

I read this article today: http://www.wired.com/2016/03/mathematicians-discovered-prime-conspiracy/. It was very interesting, so I read more about primes and Mersenne primes. Then I came across a theorem that goes like this:
if 2^n-1 (where ^ refers to exponentiation and let's call that expression "n exp" henceforth) is a prime, then n is also prime. 

Exponentiation explained:

2^3=2*2*2 (3 times) = 8

3^2 =3*3 (2 times) =9 

I was like what??? Though there was a link to a proof, I wanted to study this myself. 

Armed with Microsoft excel and a laptop, I started looking up values for this "n exp" for various positive integral values of n. I used formulas to find out whether the "n exp" was a prime or not. I could only go up to n=49 (due to some limitations: "n exp" was a 15 digit number for n=49) which was good enough to start with. I had tweak the excel a little to improve performance. MS Excel 2016 performance beceme horrible when the number of rows exceeded 60,000.

• Where n was a multiple of 4, 2^n would always end in the digit 6 and "n exp" would end in the digit 5,  hence would always be a multiple of 5 and so "n exp" will not be a prime.
• Where n was a multiple of 2, "n exp" always turned out to be a multiple of 3. Actually this point, covers values of n in the previous point also making the previous point redundant. That left only odd values of n to look at. 
• Actually where n is a multiple of 2 (let's say n=2k), "n exp" becomes 2^2k - 1 = (2^k)^2 - 1^2 = (2^k + 1) * (2^k - 1). Hence "n exp" is composite for even values of n. The only exception is when k =1, "n exp" = 3 whose factors evaluate to 1 and 3, yet 3 is still prime for obvious reasons.
• Now we come to the case where n is odd. Here I found an interesting thing. Where n was a multiple of 3, "n exp" always had 7 as a factor. For example: with n = 3, 6, 9, "n exp" equals 7, 63, 511: each of which is a multiple of 7. This was weird. I didn't know there were hints / rules for finding whether a number was a multiple of 7. I wanted to see if this was always true. I tried to use induction. 
• Let's say n=3a where a is a positive integer.
• "n exp" = 2^3a-1 =7k (being a multiple of 7)
• 2^3a=7k+1
• Evaluate "n exp" for the next value of a (=a+1): 2^(3(a+1))-1 = 2^3a * 2^3 -1 = 8(2^3a) - 1 = 8(7k+1) -1 = 56k +8  - 1 = 56k +7 = 7 * (8k+1). Proved through induction. Remember k is an integer.

I had proved that "n exp" is a composite when n is an even number. Now coming to the point of "n exp" being always a composite even when n is an odd composite... my thoughts are these.

Let us assume n = a*b where a and b are both odd integers. n will then be an odd composite number.
2^(ab)-1
=(2^a)^b - 1 which has factor 2^a-1 as per factoring rule number 7 here. 

• Incidentally when a=3, 2^a-1 = 8-1 = 7.  Hence 7 is a factor of "n exp" whenever n is a multiple of a=3. 
• Same way, whenever n is a multiple of 5, "n exp" is a multiple of 31. And so on.

The same proof could be used for cases where n is an even number. I guess I went in a roundabout fashion!!.

The next thing to look at is: why is "n exp" a composite for some prime values of n such as 11, 23, 29, 37, 41, 43 etc.

• Where n=11, "n exp" has 23 as a factor.
• Where n=23, "n exp" has 47 as a factor.
• Where n=29, "n exp" has 233, 1103, 2089 as factors. Obviously each factor will have another corresponding factor equaling which is the quotient of "n exp" and the original factor. 
• When n=37, "n exp" has 223 as a factor.
• When n=41, "n exp" has 13367 as a factor.
• When n=43, "n exp" has 431 as a factor.
• When n=47, "n exp" has 2351 as a factor.
• The question I have is: what is common to 11, 23, 29, 37, 41, 43, 47? How come "n exp" is not a prime for these values of n? is there a pattern to the factors listed above (23, 47, 233 etc)?

The first few Mersenne primes apparently are: 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607. I have confirmed with my working on excel the Mersenne primes till 31. 

Additional reading:

• https://primes.utm.edu/notes/74207281.htm
• https://primes.utm.edu/lists/small/10000.txt
• https://primes.utm.edu/lists/small/millions/ 
• http://primes.utm.edu/mersenne/index.html
• https://www.quantamagazine.org/20130519-unheralded-mathematician-bridges-the-prime-gap/