# Using Fermat's Little Theorem to Show Divisibility

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

• This is far too complicated. Note that $5^8\equiv4\mod{11}$, and that by Fermat's Little Theorem, $5^{10}\equiv1\mod{11}$. The rest follows. – Don Thousand Dec 7 '19 at 20:22
• @DonThousand Thank you! – Alex D Dec 7 '19 at 20:27

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

• From a comment by Don Thousand. – lhf Dec 7 '19 at 20:50
• In particular, repeated squaring gives $5^2=3,\,5^4=-2,\,5^8=4$. – J.G. Dec 7 '19 at 20:54
• multiply by 25 getting $$5^{10(n+1)}-100$$
• Take remainders using Fermat, getting $$1-1\equiv 0\pmod{11}$$
• +1 That's one way I'd show it too. Worth emphasis is that $\bmod 11\!\!:\,\ 25 x\equiv 0 \iff x\equiv 0\$ by $\ 25\,$ is invertible (so cancellable). – Bill Dubuque Dec 10 '19 at 5:54
• It's not mod for that first part simply $p|a\implies p|ab$ ... – Roddy MacPhee Dec 10 '19 at 11:10
• Of course we can rewrite congruences in divisibility language, but generally that's not a good thing to do since it often obfuscates innate arithmetical structure. – Bill Dubuque Dec 10 '19 at 15:38
• I didn't really use much ... – Roddy MacPhee Dec 10 '19 at 15:56
• To finish requires your way you could justify the inference $\ 11\mid 25x \,\Rightarrow\, 11\mid x,\,$ which is the divisibility form of what I wrote above. We can't possibly know what you intended to "use much" since you did not finish the argument, i.e. you omitted that step. – Bill Dubuque Dec 10 '19 at 16:18

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

• persistence of 0 Mod, modulo multiples for the win. – Roddy MacPhee Dec 8 '19 at 11:22

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

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