I know I'm supposed to use modular arithmetic, but I must be messing up my process somehow. Can someone explain how to do this?
$4^{999}$'s last two digits in other words (What is $4^{999}$'s remainder when divided by $100$)
$\begingroup$
$\endgroup$
1
-
$\begingroup$ One way is to work separately modulo $4$ (trivial) and modulo $25$. $\endgroup$– André NicolasJul 29, 2015 at 19:46
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
Since $\phi(25)=20$, we have: $$ 4^{999}\equiv 4^{-1}\equiv 19\pmod{25} $$ while obviously $4^{999}\equiv 0\pmod{4}$, hence by the Chinese theorem: $$ 4^{999} \equiv 44\pmod{100}. $$
answered Jul 29, 2015 at 19:52
$\begingroup$
$\endgroup$
3
$$ 4^6 = 4096 \equiv -4 \bmod 100 $$
so the cycle must repeat every $2(6-1) = 10$ powers of $4$. Now,
$$ 4^9 = 2^{18} = 262144 $$
so the last two digits are $44$.
answered Jul 29, 2015 at 19:53
-
$\begingroup$ Thank you! I'm just learning NT and am rubbish at mod, so this helped a lot. :) $\endgroup$ Jul 29, 2015 at 19:54
-
$\begingroup$ The Chinese remainder theorem approach is more systematic; my solution here is much more ad hoc (but I knew someone would post the CRT solution). Jack D'Aurizio's solution does not expand on the details of how to construct the solution; look here for a description of how to do so: en.wikipedia.org/wiki/Chinese_remainder_theorem $\endgroup$ Jul 29, 2015 at 19:57
-
$\begingroup$ I preferred your solution because keep in mind my lack of mod experience, and this is a method I am more familiar with. Thanks for the link. $\endgroup$ Jul 29, 2015 at 20:05