Prove that 7100−3100 is divisible by 1000
Equivalently, we want to show that 7100=3100(mod1000)
I used WolframAlpha (not sure if that's the right way though) and found that φ(250)=100.
So by Euler's theorem: 7100≡7φ(250)≡1(mod250)3100≡3φ(250)≡1(mod250)
but of course, we want (mod1000).
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
7100≡3100(mod8) and
7100≡3100(mod125).
You have already done the latter. But 72≡1(mod8)
and 32≡1(mod8) so it's a fair bet that 7100≡3100(mod8) too.
No comments:
Post a Comment