# Mersenne Primes and Fermat's Little Theorem

This is essentially a two part problem.

Prove that $2^{4n+3} = 1$ (mod $8n+7$) with $8n+7$ a prime.

Using this prove that $2^{4019} - 1$ is not a Mersenne prime, $4019$ is a prime

For first part I got, $2^{4n+3} = a^{8n+6} = a^{\phi(p)} = 1 \pmod p = 1\pmod{8n+7}$

But how do I use this to prove $2^{4019} - 1$ not a Mersenne prime?

-
This has nothing to do with quadratic reciprocity. –  Tim Ratigan Dec 19 '13 at 21:21
Maybe you have met the fact that $2$ is a quadratic residue of any prime of the form $8k\pm 1$. From that you can show that $2^{4019}\equiv 1\pmod {8039}$. This says that $8039$ divides $2^{4019}-1$. You may even have met in class exactly the same argument to show that $23$ divides $2^{11}-1$, or that $47$ divides $2^{23}-1$. –  André Nicolas Dec 19 '13 at 23:30
–  lab bhattacharjee Dec 20 '13 at 3:16

$8039$ is prime
$8039\equiv 7\pmod 8$
$8039=2\cdot 4019+1$
What is the difference between $=$ and $\equiv$? –  Link Dec 19 '13 at 22:02
@Link "$\equiv$" is typically used for equivalence mod $m$, where as "$=$" is actual equality. For instance, $1\equiv 4\equiv 7\equiv 10\pmod 3$, but $1\ne4\ne7\ne10$. –  Tim Ratigan Dec 19 '13 at 22:16