0
$\begingroup$

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?

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

1 Answer 1

1
$\begingroup$

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$.

$\endgroup$

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.