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.