6
$\begingroup$

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

$\endgroup$
  • 7
    $\begingroup$ 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. $\endgroup$ – Don Thousand Dec 7 '19 at 20:22
  • $\begingroup$ @DonThousand Thank you! $\endgroup$ – Alex D Dec 7 '19 at 20:27
6
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ From a comment by Don Thousand. $\endgroup$ – lhf Dec 7 '19 at 20:50
  • $\begingroup$ In particular, repeated squaring gives $5^2=3,\,5^4=-2,\,5^8=4$. $\endgroup$ – J.G. Dec 7 '19 at 20:54
4
$\begingroup$
  • multiply by 25 getting $5^{10(n+1)}-100$
  • Take remainders using Fermat, getting $1-1\equiv 0\pmod{11}$
$\endgroup$
  • $\begingroup$ +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). $\endgroup$ – Bill Dubuque Dec 10 '19 at 5:54
  • $\begingroup$ It's not mod for that first part simply $p|a\implies p|ab$ ... $\endgroup$ – Roddy MacPhee Dec 10 '19 at 11:10
  • $\begingroup$ 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. $\endgroup$ – Bill Dubuque Dec 10 '19 at 15:38
  • $\begingroup$ I didn't really use much ... $\endgroup$ – Roddy MacPhee Dec 10 '19 at 15:56
  • $\begingroup$ 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. $\endgroup$ – Bill Dubuque Dec 10 '19 at 16:18
3
$\begingroup$

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

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

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.