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

real analysis - How to find lim_{hrightarrow 0}frac{sin(ha)}{h}

How to find \lim_{h\rightarrow 0}\frac{\sin(ha)}{h} without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...