Prove that $7^{100} - 3^{100}$ is divisible by $1000$

Question

Prove that $7^{100} - 3^{100}$ is divisible by $1000$

Equivalently, we want to show that $$7^{100} = 3^{100} \pmod {1000}$$

I used WolframAlpha (not sure if that's the right way though) and found that $\varphi (250) = 100$.

So by Euler's theorem: $$7^{100} \equiv 7^{\varphi(250)} \equiv 1 \pmod {250} \\ 3^{100} \equiv 3^{\varphi(250)} \equiv 1 \pmod {250}$$

but of course, we want $\pmod {1000}$.

Is that what I'm intended to do in this exercise (how to proceed if so)? Is there a solution without the need to use WolframAlpha?

Thanks!

Answer 1

Wolfie A is never the right way.

By the Chinese remainder theorem, all you need is to prove both $$7^{100}\equiv3^{100}\pmod8$$ and $$7^{100}\equiv3^{100}\pmod{125}.$$ You have already done the latter. But $7^2\equiv1\pmod 8$ and $3^2\equiv1\pmod 8$ so it's a fair bet that $7^{100}\equiv3^{100} \pmod8$ too.

Answer 2

By the binomial theorem, $$ 3^{100} =(7-10)^{100} =7^{100}-\binom{100}{1}7^{99}10+\binom{100}{2}7^{98}10^2 + 10^3a $$ Now $ \binom{100}{1}10=1000 $ and $ \binom{100}{2}10^2 = 495000 $

Answer 3

\begin{eqnarray} 7^{100}-3^{100} &=& (10-3)^{100}-3^{100}\\ &=& \underbrace{{100\choose 0}10^{100}-{100\choose 1}10^{99}\cdot 3+...-{100\choose 97}10^3 \cdot 3^{97}}_{10^3k}+{100\choose 98}10^2 \cdot 3^{98} -{100\choose 99}10 \cdot 3^{99}+3^{100}-3^{100}\\ &=&1000k +50\cdot 99\cdot10^2 \cdot 3^{98} -100\cdot 10 \cdot 3^{99} \end{eqnarray}

Answer 4

I am not sure about the following method, which is rather unusual. If it doesn't work please comment why. Also, since this is probably too long to be a comment, I have posted it here.

Firstly, we can factor the expression by the difference of two squares: $$7^{100}-3^{100}=(7^{50}-3^{50})(7^{50}+3^{50})=(7^{25}-3^{25})(7^{25}+3^{25})(7^{50}-3^{50})$$ We shall concentrate on only the first two factors and use the facts that $7^5=16807$ ends in $07$ and that $3^5=243$ ends in $43$. Note that $43^5 = 147008443$.

Now $7^{25}=(7^5)^5$, so by the first fact $7^5$ ends in $...807$. Similarly, $3^{25}=(3^5)^5$, so by the second fact, $3^{25}$ ends in $...443$.

Hence $7^{25}-3^{25}$ ends in $64$ (since $807-443=364$) and $7^{25}+3^{25}$ ends in $250$ (since $807+443=1250$). The result follows since $1000$ divides $64 \times 250$.

Answer 5

Using http://mathworld.wolfram.com/CarmichaelFunction.html,

$\lambda(1000)=\cdots=100$

$\implies a^{100}\equiv1\pmod{1000}$ for $(a,1000)=1\iff(a,10)=1$

Answer 6

Hint:

$7^2=50-1,7^4=(50-1)^2=1+100\cdot24$

Using binomial expansion,

$7^{4n}=(1+100\cdot24)^n\equiv1+2400n\pmod{1000}\equiv1+400n$

$3^4=1+80$

$3^{4m}=(1+80)^m\equiv1+80m+80^2\binom m2\pmod{1000}$

Answer 7

$$(5+2)^{100}-(5-2)^{100} = \sum_{\substack{0\leq k \leq 100\\ k\text{ odd}}}\binom{100}{k} 5^k 2^{101-k}$$ hence the LHS $\pmod{5^3}$ is just $\binom{100}{1}5^1 2^{100}$, i.e. zero. The LHS is also a multiple of $8$ since any odd square is $\equiv 1\pmod{8}$. By the Chinese remainder theorem $7^{100}-3^{100}\equiv 0\pmod{1000}$.