Prove that 7100−3100 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
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.
No comments:
Post a Comment