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?

  • $\begingroup$ HINT : $2^{17}\equiv1\pmod n$ $\endgroup$ – lab bhattacharjee Apr 19 '13 at 11:17
  • $\begingroup$ @labbhattacharjee $n$? So not prime? So Eulers Theorem? How would I do inverse $varphi$ then to workout that $n$? $\endgroup$ – Kaish Apr 19 '13 at 11:19
  • $\begingroup$ en.wikipedia.org/wiki/… shows that it's prime $\endgroup$ – lab bhattacharjee Apr 19 '13 at 11:23
  • $\begingroup$ I think you need to execute en.wikipedia.org/wiki/Fermat_primality_test $\endgroup$ – lab bhattacharjee Apr 19 '13 at 11:26
  • 2
    $\begingroup$ 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. $\endgroup$ – 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$.

  • $\begingroup$ $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$). $\endgroup$ – Jyrki Lahtonen Apr 19 '13 at 11:32
  • $\begingroup$ 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. $\endgroup$ – Kaish Apr 19 '13 at 12:28
  • 2
    $\begingroup$ @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}$. $\endgroup$ – Calvin Lin Apr 19 '13 at 14:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.