Verify that ## 17 ## divides ## 11^{104}+1 ##

[Math100]

Homework Statement

Use Fermat's theorem to verify that ## 17 ## divides ## 11^{104}+1 ##.

Relevant Equations

None.

Proof:

Fermat's theorem states:
Let ## p ## be a prime and suppose that ## p\nmid a ##. Then ## a^{p-1}\equiv 1\pmod {p} ##.
By using Fermat's theorem, we will prove that ## 17 ## divides ## 11^{104}+1 ##.
Suppose ## a=11, p=17 ## and ## p\nmid a ##.
Then ## 11^{17-1}\equiv 1\pmod {17}\implies 11^{16}\equiv 1\pmod {17} ##.
Observe that ## 104=16\cdot 6+8 ##.
This means
\begin{align*}
&11^{104}\equiv 11^{16\cdot 6+8}\equiv [(11^{16})^{6}\cdot 11^{8}]\pmod {17}\\
&\equiv [1^{6}(11^{2})^{4}]\pmod {17}\equiv 16\pmod {17}.\\
\end{align*}
Thus ## 11^{104}+1\equiv 0\pmod {17}\implies 17\mid (11^{104}+1) ##.
Therefore, ## 17 ## divides ## 11^{104}+1 ##.

 

[fresh_42]

You could have given me an additional calculation ##(11^2)^4\equiv (121)^4\equiv 2^4\equiv 16\pmod{17}## as it is not immediately clear that ##(11^2)^4 \equiv 16\pmod{17}.## On the other hand, maybe it is just the time difference, will say already evening over here.

That's all. The rest is fine.

 

[Math100]

You could have given me an additional calculation ##(11^2)^4\equiv (121)^4\equiv 2^4\equiv 16\pmod{17}## as it is not immediately clear that ##(11^2)^4 \equiv 16\pmod{17}.##

That's all. The rest is fine.

I apologize. I always tend to skip a few steps when writing proofs.

 

[Math100]

It's a bad habit and I must abandon this vice.

 

[fresh_42]

It's a bad habit and I must abandon this vice.

Don't mind. I was just lazy. Your proof is well written so it can be read fluently, except that nobody knows what ##11^8## is.

 

[mathwonk]

nice job. note that it is also fairly easy to do this directly by repeated modular arithmetic, without fermat, using that 11 is -6, mod 17, and 6 is 2 times 3 and 2^4 is -1, and 3^4 is -4, hence 3^8 is -1, mod 17. hence (11)^104 is -1, mod 17.