# How do you prove $37^{100} - 37^{20}$ is a multiple of $10$ using induction?

I've tried making it $37^{5n} - 37^n$ is a multiple of $10.$ Then I made the base case be $n = 0,$ so $1 - 1 = 0$ which is a multiple of $10.$ I assumed $37^{5n} - 37^n$ is a multiple of $10$ for all $n \geqslant0.$ The inductive step is really hard however. I did $37^{5(n + 1)} - 37^{n+1}$ which I simplified to $37^{5n + 5} - 37^{n+1}.$ I tried factoring and made it $37^5\cdot37^{5n} - 37\cdot(37^n).$ I don't know where to go from here though.

• By Euler's theorem $\left(37^{25}\right)^4-\left(37^{5}\right)^4\equiv 1-1\equiv 0\pmod{10}$. – user236182 Sep 13 '15 at 22:06
• More generally, $a^5-a$ is a multiple of $10$ (in this case $a=37^n$). It's a consequence of Fermat's Little Theorem. – user236182 Sep 14 '15 at 8:40

Without using induction:

$7^k\equiv7^{k+5}\pmod{10}\implies$

$37^k\equiv37^{k+5}\pmod{10}\implies$

$37^{20}\equiv37^{25}\equiv37^{30}\equiv\ldots\equiv37^{100}\pmod{10}\implies$

$37^{100}-37^{20}\equiv0\pmod{10}$

Hint:

you have $37*37^{5n}-37*37^n = 37*(37^{5n}-37^n)$.

What do you know about the divisibility of $37^{5n}-37^n$?

I know OP requested induction, but I would like to post this anyway on the off-chance that someone finds it interesting:

This is the same as proving that $10 {\large\mid} 37^{80}-1$, since $37^{100}-37^{20} = 37^{20}(37^{80}-1)$ and $37^{20}$ has only powers of $37$ as divisors since $37$ is prime.

Clearly $2{\large\mid}37^{80}-1$ since $37^{80}-1$ is even, so we must only show that $5{\large\mid}37^{80}-1$. Observe that $37 \equiv 2 \pmod{5}$, therefore $37^{80} \equiv 2^{80} \pmod{5}$. Thus we have $2^{80} \equiv (2^{10})^8 \equiv (1024)^8 \equiv (4)^8 \equiv (4^2)^4 \equiv 1^4 \equiv 1 \pmod{5}$.

Thus $37^{80} \equiv 1 \pmod{5}$, and so $37^{80} - 1 \equiv 0 \pmod{5}$, as desired.

• $37^{80}\equiv 2^{80}\equiv \left(2^2\right)^{40}\equiv (-1)^{40}\equiv 1\pmod{5}$. – user236182 Sep 13 '15 at 22:04
• @user236182 I guess you're better at skinning cats than I am. – 727 Sep 13 '15 at 22:08

$\phi(10)=4$. Therefore $37^5 \equiv 37 \mod 10$. (Actually we can easily calculate it without using Euler phi function).

$37^{5n}\cdot37^5-37^n\cdot37 \equiv 37\cdot(37^{5n}-37^n) \mod 10$. Now we have induction.

Note that we didn't need induction.