Using Fermat's Little Theorem to Show Divisibility

Question

I was asked to prove, using Fermat's Little Theorem, that $11|5^{10n+8}-4$ for $n\ge0$. I proved it but I was wondering whether there's an easier way (still using Fermat's). Here is my proof:

\begin{alignat}{3} 11|5^{10n+8}-4&\iff5^{10n+8}-4&&\equiv0 &&&\mod11\\ \quad&\iff 25^{5n+4}-4&&\equiv0 &&&\mod 11\\ \quad&\iff \qquad3^{5n+4}&&\equiv 4 &&&\mod 11\\ \quad&\iff \qquad3^{5n+5}&&\equiv 12 &&&\mod 11\\ \quad&\iff \qquad3^{5(n+1)}&&\equiv 1 &&&\mod 11.\\ \end{alignat} For $n\ge1$, let S(n) be the statement

$$ S(n) :3^{5(n+1)}\equiv 1 \mod 11.$$ We will prove by induction on $n$ that $S(n)$ holds.

Base case ($n=1$). By Fermat's Little Theorem, $S(1)$ is true.

Inductive Step. Fix some $k\ge1$ and suppose $S(k)$ is true. To be shown is that the statement $$S(k+1):3^{5(k+2)}\equiv 1 \mod 11$$ follows. Beginning with the LHS of $S(k+1)$,

\begin{alignat}2 \quad&3^{5(k+2)}&&=3^{5(k+1)+5}\tag{1}\\ \quad&\ \implies &&=3^{5}3^{5(k+1)}\tag{2}\\ \quad& \overset{\text{IH}}{\implies} &&\equiv3^{5}(1)\mod 11\tag{3}\\ \quad&\ \implies &&\equiv1\mod 11\tag{4},\\ \end{alignat} arriving to the RHS of $S(k+1)$, concluding the inductive step. It is proved, then, by MI that $S(n)$ holds for all $n\ge1.$ Since $S(0)$ holds by $(4)$, then $S(n)$ is true for all $n\ge0$.

Answer 1

We have $$ 5^{10n+8} = 5^{10n} 5^8 = (5^{10})^n 5^8 \equiv 1 \cdot 5^8 \equiv 4 \bmod 11 $$

Answer 2

$$10n+8=10(n+1)-2$$ we know that $5^{10}\equiv 1 \mod 11$ by Fermat.

we just need to prove that $$5^{-2}-2^2=$$ $$(5^{-1}+2)(5^{-1}-2)\equiv 0 \mod 11$$

which is true since the inverse $5^{-1}$ is $9$ .

Answer 3

• multiply by 25 getting $5^{10(n+1)}-100$
• Take remainders using Fermat, getting $1-1\equiv 0\pmod{11}$

Answer 4

Much easier way!

By FLT $5^{10} \equiv 1 \pmod{11}$ so $5^{10n+8}\equiv 5^8$ and $5^{10n +8} -4 \equiv 5^8 -4\pmod {11}$.

So you just have to show that one case the $5^8 \equiv 4 \pmod {11}$. Then every case will be $5^{10n + 8} - 4\equiv 0 \pmod{11}$

Admittedly that requirse calculations but there are 3 ways, each more clever than the other

1) $5^2 = 25\equiv 3 \pmod {11}$. $5^4\equiv 3^2 \equiv 9\equiv -2 \pmod {11}$. $5^8\equiv (-2)^2 \equiv 4 \pmod {11}$.

2) $5^8*5^2 \equiv 5^{10} \equiv 1\pmod {11}$

$5^8*5^2 \equiv 5^8*3 \equiv 1\pmod{11}$ so as $11$ is prime $3^{-1}$ exist as is.... $1 \equiv 12=3*4\pmod{11}$ so $5^8*3*4 \equiv 4\pmod {11}$ and $5^8\equiv 4\pmod {11}$.

3) I'll admit I didn't come up with this.

If $5^8 -4 \equiv A\pmod{11}$ then

$(5^8-4)*25 \equiv A*25\pmod{11}$

$5^{10} - 100 \equiv 3A$

$1 - 1 \equiv 3A$

$3A \equiv 0\pmod {11}$ and as $11$ is primes $A\equiv 0 \pmod{11}$.

Answer 5

$10\equiv-1\bmod11,$ so $10^8 \equiv(-1)^8=1\bmod11,$

so $5^{10n+8}\equiv5^8\equiv5^82^{10}=10^82^2\equiv4\bmod 11,$

since $5^{10}$ and $2^{10}\equiv1\bmod11$ by Fermat's little theorem.