# Thread: Mersenne Primes

1. ## Mersenne Primes

How can I prove that if $\displaystyle a^n - 1$ is prime, then $\displaystyle a = 2$ and $\displaystyle n$ is prime?

2. Originally Posted by raheel88
How can I prove that if $\displaystyle a^n - 1$ is prime, then $\displaystyle a = 2$ and $\displaystyle n$ is prime?
First note $\displaystyle n$ must be prime. Suppose $\displaystyle n=cd$, then $\displaystyle a^n-1=a^{cd}-1=(a^c-1)\cdot \left(1+a^c+a^{2c}+a^{3c}+\cdots+a^{(d-1)c}\right)$.

I'll get back to you with your other question.

3. Originally Posted by chiph588@
First note $\displaystyle n$ must be prime. Suppose $\displaystyle n=cd$, then $\displaystyle a^n-1=a^{cd}-1=(a^c-1)\cdot \left(1+a^c+a^{2c}+a^{3c}+\cdots+a^{(d-1)c}\right)$.

I'll get back to you with your other question.
$\displaystyle a=2$ because $\displaystyle a-1\mid a^n-1$. Can you see why?

4. Originally Posted by chiph588@
$\displaystyle a=2$ because $\displaystyle a-1\mid a^n-1$. Can you see why?
of course!

we've already proved that $\displaystyle a^n-1$ is prime so $\displaystyle a-1$ must be equal to 1!

thanks chiph588... I've got another problem posted that is most definitely more challenging and in your forte.

regards

5. Originally Posted by raheel88
of course!

we've already proved that $\displaystyle a^n-1$ is prime so $\displaystyle a-1$ must be equal to 1!

thanks chiph588... I've got another problem posted that is most definitely more challenging and in your forte.

regards
I didn't quite follow your explanation there. My explanation is

$\displaystyle a \equiv 1\ (\text{mod}\ (a-1))$

Therefore $\displaystyle a^n-1 \equiv 1^n - 1 \equiv 0\ (\text{mod}\ (a-1))$.

Edit: Never mind, I guess you weren't trying to explain that part. The wording is just a bit odd though, in terms of, we haven't proven that $\displaystyle a^n-1$ is prime, merely stating conditions for it being possible.

6. Originally Posted by undefined
I didn't quite follow your explanation there. My explanation is

$\displaystyle a \equiv 1\ (\text{mod}\ (a-1))$

Therefore $\displaystyle a^n-1 \equiv 1^n - 1 \equiv 0\ (\text{mod}\ (a-1))$.

Edit: Never mind, I guess you weren't trying to explain that part.
Another way is to observe $\displaystyle a^n-1 = (a-1)(a^{n-1}+a^{n-2}+\cdots+a+1)$.

7. Originally Posted by undefined
I didn't quite follow your explanation there. My explanation is

$\displaystyle a \equiv 1\ (\text{mod}\ (a-1))$

Therefore $\displaystyle a^n-1 \equiv 1^n - 1 \equiv 0\ (\text{mod}\ (a-1))$.

Edit: Never mind, I guess you weren't trying to explain that part. The wording is just a bit odd though, in terms of, we haven't proven that $\displaystyle a^n-1$ is prime, merely stating conditions for it being possible.
yeh sorry...i meant to say that we're assuming that $\displaystyle a^n - 1$ is prime, not that we've already proven it.