Deduce that ## 13\mid (11^{12n+6}+1) ##

[Math100]

Homework Statement

From Fermat's theorem deduce that, for any integer $n\geq 0, 13\mid (11^{12n+6}+1)$.

Relevant Equations

None.

Proof:

Let $n\geq 0$ be any integer.
Applying the Fermat's theorem produces:
$a=11, p=13$ and $p\nmid a$.
Then $11^{13-1}\equiv 1\pmod {13}\implies 11^{12}\equiv 1\pmod {13}$.
Observe that
\begin{align*}
&11^{12n+6}+1\equiv [(11^{12})^{n}\cdot 11^{6}+1]\pmod {13}\\
&\equiv [1^{n}(-2)^{6}+1]\pmod {13}\\
&\equiv (64+1)\pmod {13}\\
&\equiv 65\pmod {13}\\
&\equiv 0\pmod {13}.\\
\end{align*}
Thus $13\mid (11^{12n+6}+1)$.
Therefore, $13\mid (11^{12n+6}+1)$ for any integer $n\geq 0$.

 

[fresh_42]

Correct. If you want to try, you could probably try a proof by induction, too.

 

[Math100]

Correct. If you want to try, you could probably try a proof by induction, too.

True, but I like using Fermat's theorem more. It's easier than proof by induction. I do want to admit that, I definitely need to practice more about writing proofs by induction, since I am not good at it.