# Use Fermat's theorem to verify that $17\mid(11^{104})-1$

Use Fermat's theorem to verify that $17\mid(11^{104})-1$.

I was able to prove the statement true simply by breaking down $11^{104}=-1 \pmod{17}$ but I was unsure how to do this using Fermat's theorem.

Fermat's theorem is $a^{p-1}=1 \pmod p$ so would I have $11^{16}=1 \pmod{16}$ then $1^4=1 \pmod{16}$ but at this point I was stuck?

• Do you mean $17 | 11^{104} + 1$? May 12, 2014 at 2:43

Well, $104 = 8 \times 13$. Fermat tells you $a^{16} \equiv 1 \bmod 17$ for any $a$ not divisible by $17$. If $11^8 \equiv b \mod 17$, we have $b^2 \equiv 11^{16} \equiv 1 \bmod 17$. Since $b^2 - 1 = (b-1)(b+1)$, we know that either $b\equiv 1 \bmod 17$ or $b=-1 \bmod 17$. Which is it?
Well, there are eight quadratic residues mod $17$, which you can easily enumerate: $1^2, 2^2, \ldots, 8^2$. The degree-8 polynomial $x^8 - 1$ can't have more than eight roots in any field, so these are all of them. If $11$ isn't in the list, you can't have $11^8 \equiv 1 \bmod 17$.