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

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!

• Use the formula $\varphi(p_1^{n_1}\cdot\ldots\cdot p_k^{n_k})=p_1^{n_1-1}(p_1-1)\cdot\ldots\cdot p_k^{n_k-1}(p_k-1)$ where $p_1, \ldots,p_k$ are all mutually different prime numbers. In our case, $\varphi (2\cdot 5^3)=2^0 (2-1)\cdot 5^2 (5-1)=25\cdot 4=100$. No need to engage a computer. – user491874 Dec 2 '17 at 16:21
• @user8734617, but you knew a-priori that $\varphi(250) = 100$. Thank you anyways :) – Elimination Dec 3 '17 at 11:12
• My comment was not about how to solve the problem, see Lord Shark's answer, for example. It was more about how to, having undeniably used 'Wolfie A', justify your solution by other means. Sorry for any misunderstanding. – user491874 Dec 3 '17 at 12:36

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.

• Oooh, I don't know about that! There are problems in mathematics for which computer assistance is entirely appropriate, aren't there? Isn't that precisely why we invented computers? In this case, your solution is great, and I agree that the machines needn't get involved..... – G Tony Jacobs Dec 2 '17 at 15:53
• Come on guys, if computer assistance in this sort of problems was allowed, what's to stop the OP to just calculate the three last digits of $7^{100}$ and $3^{100}$ etc. – user491874 Dec 2 '17 at 16:13
• @GTonyJacobs If computer assistance was allowed, this kind of problem would be redundant. In that case, OP could just calculate the number and divide it by 1000. Problems like this are posed as an exercise, and not because their solution is of particular interest. – Jannik Pitt Dec 2 '17 at 16:32
• @Elimination: I'd see that $3^5 = 243 = 250-7 \equiv -243\pmod{125}$ (that's easily calculated even without a computer). Thus $3^{100} =(3^5)^{20}\equiv(-7)^{20}\pmod{125}$. But with an even exponent, the minus sign cancels, so you only have to check $7^{20}\equiv7^{100} \pmod{125}$. Since $\gcd(7^{20},125)=0$, you can cancel out $7^{20}$ remaining with the $7^{80}\equiv 1 \pmod{125}$. Next, I'd try small divisors of $80$. $7^2=49$ obviously doesn't work. $7^4 = (50-1)^2 = 2401$ isn't good either, but $01$ at the end looks good, however we'd need to get rid of the $4$ in the hundred's place. … – celtschk Dec 2 '17 at 17:51
• That's best done by trying to do another $()^5$ so we get a $()^{20}$ in total; note that we can drop the initial $2$ for that as $1000\equiv 0\pmod{125}$, and we only need the lowest two terms of the binomial formula as $100^2\equiv 0\pmod{125}$, so $7^{20}=(7^4)^5\equiv 401^5 \equiv 5\cdot 400 + 1 = 2001\equiv 1\pmod{125}$. Thus $7^{80}=(7^{20})^4\equiv 1^4=1\pmod{125}$ which we've seen above is equivalent to $3^{100}\equiv 7^{100} \pmod{125}$. But then, the binomial formula ansatz from other answers is IMHO the better solution in this case anyway (note I also used a binomial formula above). – celtschk Dec 2 '17 at 17:58

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

• You've got some of the last exponents wrong. For example, $2+99 = 101 \ne 100$. – celtschk Dec 2 '17 at 17:28
• Fixed, thanks. :) – Aqua Dec 2 '17 at 18:33

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$

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

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

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

• 14 ends with 4 but 14×250 ends in 500. – user491874 Dec 2 '17 at 17:33
• @user8734617 edited: $64 \times 250 = 16000$ – TheSimpliFire Dec 2 '17 at 20:02

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

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