3
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ By Euler's theorem $\left(37^{25}\right)^4-\left(37^{5}\right)^4\equiv 1-1\equiv 0\pmod{10}$. $\endgroup$ – user236182 Sep 13 '15 at 22:06
  • $\begingroup$ 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. $\endgroup$ – user236182 Sep 14 '15 at 8:40
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

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

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

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