0
$\begingroup$

What are the last two digits of 2^403? I have tried using the Totient function, but two is not coprime with any power of 10. How do i do this via mod 100?

$\endgroup$
  • $\begingroup$ The last two digits of the exponent are $03$. I don't think your title really expresses the question you want to ask. $\endgroup$ – bof May 2 '19 at 2:19
2
$\begingroup$

$2^{20}=1048576\equiv1\pmod{25},$ so $2^{400}\equiv1\pmod{25},$ so $25$ divides $2^{400}-1,$

so $100$ divides $2^{402}-4,$ so $2^{402}\equiv4 \pmod {100}.$ Can you take it from here?

$\endgroup$
  • $\begingroup$ using chinese remainder theorem would only work for mod 10 then.. $\endgroup$ – user251865 May 2 '19 at 2:21
  • $\begingroup$ @BarryChau: thank you; I have corrected $\endgroup$ – J. W. Tanner May 2 '19 at 2:27
  • 1
    $\begingroup$ If you don't know $2^{20}=1048576$, you may know $2^{10}=1024\equiv{-1}\pmod{25}$ $\endgroup$ – J. W. Tanner May 2 '19 at 2:29
  • $\begingroup$ As pointed out by Bill Dubuque, $2^{\phi(25)}=2^{20}\equiv1\pmod{25}$ $\endgroup$ – J. W. Tanner May 2 '19 at 3:06
  • $\begingroup$ $2^{100}\equiv1 \pmod{125},$ so $ 2^{400}\equiv1\pmod{125}$, so $125$ divides $2^{400} - 1,$ so $1000$ divides $2^{403}-8,$ so actually $2^{403}\equiv8\pmod{100\color{blue}0}$ $\endgroup$ – J. W. Tanner May 3 '19 at 4:22
1
$\begingroup$

$2^{\large 403}\!\bmod 100 = 2^{\large 2}(2(\color{#c00}{2^{\large 20}})^{\large 20}\! \bmod 25) = 4(2)\,\ $ by $\ \color{#c00}{2^{\large 20}}\!\equiv 1\pmod{25}\ $ by Euler $\phi,\,$

& $\,\ ab\bmod ac = a\,(b\bmod c),\, $ the mod Distributive Law.

$\endgroup$
0
$\begingroup$

You may not have to use the Totient function.

Notice that $2^{10}=1024 \equiv 24 \mod(100)$.

$24^2=576\equiv76\equiv-24 \mod(100)$.

Similarly, $(-24)^2=576\equiv76\equiv-24 \mod(100)$.

Then, we have $2^{403}=2^{320}\cdot2^{80}\cdot2^3 = (((((2^{10})^2)^2)^2)^2)^2\cdot(((2^{10})^2)^2)^2)\cdot2^3\equiv -24\cdot-24\cdot8\mod(100)$

This is equivalent to $-24\cdot 8 \mod(100)=\boxed{08}$

$\endgroup$
0
$\begingroup$

you can check (for example with wolframalpha) that the sequence $(2^n \pmod{100} :n\geq 2)$ seems to be periodic with period 20, repeating the string $4, 8, 16, 32, 64, 28, 56, 12, 24, 48, 96, 92, 84, 68, 36, 72, 44, 88, \ 76, 52$. This can then be proved by induction. So to find $2^{n+1} \pmod{100}$ for any $n$ it's enough to look at the remainder when $n$ is divided by $20$. So we find $2^{403} = 2^{1+402}=2^{1+20\times 20 +2}\equiv 2^{1+2}\equiv 8 \pmod{100}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.