# Last two digits of a large exponent

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?

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

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

• using chinese remainder theorem would only work for mod 10 then.. – user251865 May 2 '19 at 2:21
• @BarryChau: thank you; I have corrected – J. W. Tanner May 2 '19 at 2:27
• If you don't know $2^{20}=1048576$, you may know $2^{10}=1024\equiv{-1}\pmod{25}$ – J. W. Tanner May 2 '19 at 2:29
• As pointed out by Bill Dubuque, $2^{\phi(25)}=2^{20}\equiv1\pmod{25}$ – J. W. Tanner May 2 '19 at 3:06
• $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}$ – J. W. Tanner May 3 '19 at 4:22

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

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

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}$$.