Friday, 2 September 2016

number theory - Prove that 71003100 is divisible by 1000





Prove that 71003100 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: 71007φ(250)1(mod250)31003φ(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
71003100(mod8) and

71003100(mod125).
You have already done the latter. But 721(mod8)
and 321(mod8) so it's a fair bet that 71003100(mod8) too.


No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

How to find lim without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...