Ok. So I got this problem I have for homework... but I am lazy. Let a and n be positive integers with n != 1. Prove that, if a<sup>n</sup> - 1 is a prime number, then a = 2 and n is a prime number. In other words, that the only primes of this form are Mersenne primes. I can easily show that a = 2. However, Let a<sup>n</sup> - 1 = a<sup>mn</sup> - 1. I want to show that m = 1 and n must be a prime. a<sup>mn</sup> - 1 = (a<sup>m</sup> - 1)*(a<sup>m(n-1)</sup> + a<sup>m(n-2)</sup> + ... + a<sup>m</sup> + 1). Since a<sup>mn</sup> - 1 is prime, one of the two factors = 1. I think I am justified to say that the second factor is greater than the first factor, therefore the first factor = 1. So, a<sup>m</sup> - 1 = 1. Implying that ln(2)/ln(a) = m. ANd since I proved that a = 2, m = 1. So, how do I show that n is prime? I think I pretty much shown that, but I cannot think of the statement I need to say that allows me to make that jump. Because, if I repeat the process and let n = xy, then I again, show that x = 1. So, then I show that mn = n = xy. But... ? Maybe I am missing the obvious Please Register or Log in to view the hidden image!
Yes. But how does that help? And there was a slight typo in my post. I essentially said "let n = mn." However, I think you know what I mean. I was factoring n. The end result is still the same... m = 1. But that fact doesn't tell me if n is prime or not. All I get is that n = n. 4 = 4 but 4 isn't prime.
If n isn't prime, you'll be able to find an integer m (other than n) such that n/m is an integer. Then 2<sup>n</sup>=(2<sup>m</sup>)<sup>n/m</sup>, which would imply that a<sup>n</sup>-1=prime is satisfied for integer values of a other than 2. Because you've already proved that a can only equal 2, n can only be divisible by 1 (and itself obviously) and is therefore itself prime.
Ahh.. I see. I missed that one Please Register or Log in to view the hidden image! Thank you Please Register or Log in to view the hidden image!
Ok. Here is my structure of the proof. For some reason, the logic seems right but wrong at the same time. The whole things works out on a "truth table" ONLY when A is true, which is what I assume to be true. A A => B A AND B => C Therefore, A => B AND C. Correct? A is "a^n - 1 is prime). I assume this is true, so A. B is "a = 2" C is "n is prime."
It proves "A => B and C", but not "B and C => A". You've proven that all the primes in the set {a<sup>n</sup>-1} are a subset of {2<sup>p</sup>-1 | p is prime}.
Which is good, he should be worried if he thought he had proven "B and C=>A"! It's pretty normal for a theorem to be stated in such a way that you use some of it's consequences to prove the other consequences, but you don't actually have to do that here. If n=xy, x<=y positive integers, you have: a^n-1=(a^x-1)*(a^(x(y-1))+...+a^y+1) So a^n-1 is divisible by a^x-1. a^x-1 is less than a^n-1, so if the latter is prime we must have a^x=2, which is only possible if a=2 and x=1.
Oh god no. I know that would be a bad thing. Or I could have done that Please Register or Log in to view the hidden image! My proof is a bit long, but I think it works. Thank you guys for the assistance.
Heh relax. I only added that because I didn't see what else could be bothering you. The logic here: is watertight Please Register or Log in to view the hidden image!
