Using Fermats Little Theorem to show $2^{17} -1$ is prime

Show that $n = 2^{17} - 1$ is prime by using Fermat's Little Theorem $2^{p-1} \equiv 1 \mod p$ for any $p$ dividing $n$.

I said, that by FLT, we get $2^{16} \equiv 1 \mod 17$, and we can see that $1 \equiv 1 \mod 17$ and so we get

$$n = 1 - 1 = 0 \mod 17$$

but then all this tells me is that $n = 17k$ for some $k$ and not that it is prime. Where have I gone wrong?

• HINT : $2^{17}\equiv1\pmod n$ – lab bhattacharjee Apr 19 '13 at 11:17
• @labbhattacharjee $n$? So not prime? So Eulers Theorem? How would I do inverse $varphi$ then to workout that $n$? – Kaish Apr 19 '13 at 11:19
• en.wikipedia.org/wiki/… shows that it's prime – lab bhattacharjee Apr 19 '13 at 11:23
• I think you need to execute en.wikipedia.org/wiki/Fermat_primality_test – lab bhattacharjee Apr 19 '13 at 11:26
• Actually, from $2^{16}\equiv 1[17]$, you get $2^{17}\equiv 2[17]$ (that's still FLT), hence $n\equiv 1[17]$. Not what you said. – Julien Apr 19 '13 at 11:30

If $p|n$ is prime, then $2^{p-1}\equiv 1\pmod p$, but also $2^{17}\equiv 1\pmod p$, hence if $k=(p-1)a+17b$ then $2^k\equiv 1\pmod p$. If $p-1$ is not a multiple of $17$, we can find such a linear combination with $k=a(p-1)+b17=1$, i.e. $2\equiv 1\pmod p$, contradiction. Therefore $p\equiv1\pmod{17}$ for any $p|n$. Now use trial divisions with primes of the form $p=17m+1<\sqrt n\approx 362$, that is $p=103$, $137$, $239$, and $307$.
• $p$ must be odd, so $p-1$ must be a multiple of $34$. This means that $2$ must be a quadratic residue (it is of order 17). This doesn't help much, but does imply that you don't have to test the candidate $307$ as all the candidates must be congruent to $\pm1\pmod8$. By CRT we can see that an eventual prime factor must be congruent to either $1$ or $103$ modulo $136$, which helps locating your list (don't need to check the entire residue class modulo $17$). – Jyrki Lahtonen Apr 19 '13 at 11:32
• Sorry, I don't understand this answer properly. I have a few questions: 1) How do you know $2^{17} \equiv 1 \mod p$? That doesn't come from Fermat's Little Theorem does it? 2) Where has that $k = ...$ come from? 3) I get the way you can find the solutions to that linear combination but I don't understand that "i.e $2 \equiv 1 \mod p$, contradiction" bit and why that means $p \equiv 1 \mod 17$. I understand the last bit. – Kaish Apr 19 '13 at 12:28
• @Kaish OP has laid it out steps, and you could work through the details. Here are more specific details 1) follows from $0\equiv n = 2^{17} -1 \pmod{p}$. 2) He is letting $k$ be a linear combination. From Bezout's Lemma / Euclidean Algorithm, we know that there exists integers a and b such that $(p-1)a + 17b = \gcd(p-1, 17)$, which is either 1 or 17. 3) If the GCD is equal to 1, then $1 = 2^k = 2^1 = 2 \pmod{p}$ which is the contradiction. 4) Hence, the GCD is equal to 17, so $p-1 \equiv 0 \pmod{17}$ or $p \equiv 1 \pmod{17}$. – Calvin Lin Apr 19 '13 at 14:33