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.
Asked
Active
Viewed 879 times
4
-
3By 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 08:40
5 Answers
3
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}$
barak manos
- 43,109
1
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$?
Eemil Wallin
- 693
1
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.
727
- 1,607
-
$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
-
-
1
$\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.
vudu vucu
- 1,040
0
= 37^100 − 37^20 ---------> (i)
As 37 and 100 are co-prime numbers so by Euler's theorem Euler's theorem Wikipedia 37^100 ≡ 1
and 37 and 20 are co-prime, so similarly 37^20 ≡ 1.
So equ.(i) can be written as:
≡ 1 - 1
≡ 0
which is multiple of 10.
