Find the remainder of $3^{333}$ divided by $100$

Find the remainder of $$3^{333}$$ divided by $$100$$

So I can find that $$100=2^2\cdot 5^2$$

Then I want to find $$3^{333}$$ mod $$4$$ and mod $$25$$ and use chinese remainder theorem to find a solution mod $$100$$.

I can find that $$3^{333}\equiv (-1)$$ mod $$4$$

But then $$3^{333}=((3^3)^3)^{37}\equiv (27^3)^{37}\equiv (2^3)^{37}\equiv 8^{37}$$ mod $$25$$

But I cannot find $$8^{37}$$ mod $$25$$

• Mar 20 '20 at 20:57
• @WhatsUp I can see I can reduce it to $3^{320}\times 3^{13}\equiv 3^{13}$ mod $100$, but not sure what I do with $3^{13}$ Mar 20 '20 at 21:01
• You used the first link I gave. Now use the second one. Mar 20 '20 at 21:02
• $3^{20}=3 486 784 401\equiv 1 \text{ mod }100$. Just a little hint :)
– user759746
Mar 20 '20 at 21:03
• Hint $\large\ 3^{333} = 3(-1+10)^{166} =\,\ldots$ (Binomial Theorem, only first two terms survive $\bmod 100$) Mar 20 '20 at 21:11

$$3^{333}$$ being divided by 100.

$$=(3^9)^{37}$$

$$=19683^{37}$$

$$=(19700-17)^{37}$$

$$\equiv -17^{37} \quad \bmod 100$$

$$-17^{37} =-17(17^{36})=-17(300-11)^{18}$$

$$\equiv -17(11^{18}) \quad \bmod 100$$

$$-17(11^{18})=-17((1300+31)^6)$$

$$\equiv -17(31^6) \quad \bmod 100$$

$$-17(31^6)=-17(1000-39)^3$$

$$\equiv -17 \cdot -39^3 \quad \bmod 100$$

$$17 \cdot 39^3=17 \cdot 39 \cdot (1500+21)$$

$$=(700-37)(1500+21)$$

And after all the work $$-37 \cdot 21=-777 \equiv -77 (\bmod 100)$$

But if the answer had to be positive then $$100-77=\boxed{23}$$

So you need, as you noted, $$3^{13}\pmod {100}$$. Try successive squaring. $$3^2=9,3^4=9^2=81,3^8=81^2=(-19)^2=61, 3^{12}=3^4\cdot3^8=81\cdot61=41,3^{13}=3\cdot41=23\pmod{100}$$.

We have $$3^{333} \equiv 2^{111}\equiv1024^{11}\times2\equiv-2 \pmod{25}$$ (note that I used your calculation for the first equality here and the well-known fact that $$2^{10}=1024$$)

So, if $$x=3^{333}$$, $$x=-2+25k \equiv-2+k \equiv-1 \pmod4$$

Hence $$k \equiv1 \pmod 4$$

Therefore $$x=-2+25(1+4k')=23+100k' \equiv23 \pmod{100}$$

Use the totient function. $$2$$ and $$5$$ are distinct primes so $$\phi(100)=\phi(2^25^2)=\phi(2^2)\phi(5^2)=[2(2-1)][5(5-1)]=40.$$

Now since $$\gcd(3,100)=1$$ we have $$1\equiv 3^{\phi(100)}\equiv 3^{40} \mod 100.$$

Therefore $$3^{333}\equiv (3^{40})^8\cdot 3^{13}\equiv (1)^8\cdot 3^{13}\equiv 3^{13} \mod 100.$$

To finish, see my comment to the Q.

Using $$\ ab\bmod ac = a\,(b\bmod c) =$$ mod Distributive Law to factor out $$\,a = 4$$

$$3^{\large 333}\!+\!1\bmod 100 = 4\left[\dfrac{\color{#90f}{3^{\large 333}}\!+\!1}4\bmod 25\right] = 4\left[\dfrac{\color{#90f}{23}\!+\!1}4\bmod 25\right] = 4,\$$ by

$$\!\bmod 25\!:\,\ \color{#c00}{3^{\large 20}\equiv 1}\ \Rightarrow\ \color{#90f}{3^{\large 333}}\equiv \underbrace{3(\color{#0a0}{3^{\large 3}})^{\large 4}(\color{#c00}{3^{\large 20}})^{\large 16}}_{\textstyle 3\,(\color{#0a0}2)^{\large 4}\,\color{#c00}1^{\large 16}}\equiv \color{#90f}{23},\,$$ by $$\rm\color{#c00}{Euler\ \phi(5^2)=4\cdot 5}$$

Remark  The prior line is a special case of modular order reduction - the key to simplifying the computation of large modular powers.

As explained in the first link, the mod Distributive Law is an operational form of CRT. You can use the standard CRT formula along with the above computation mod $$25$$ to obtain the same result. In fact already $$23\equiv -1\pmod{\!4}$$ so we're done - we don't even need to apply the CRT formula.

Another quick way: $$\, 3^{\large 333} = 3(-1+10)^{\large 166} =\,\ldots\,$$ and Binomial expanding only the first $$2$$ terms survive $$\!\bmod 100$$.

Use Euler.

$$\phi(25) = 20$$ so $$8^{20}\equiv 1 \pmod {25}$$

So we need to figure out $$8^{17}\equiv 8^{-3}$$ which is which will be equivalent to $$k^3$$ where $$k$$ is the multiplicative inverse of $$8$$. $$8*3=24\equiv -1$$ so $$8*(-3)\equiv 1 \pmod{25}$$ and $$8^{17} \equiv (-3)^3 \equiv -27\equiv -2\equiv 23 \pmod {25}$$.

.....

Or back to the $$3$$

$$3^{333}=3^{320}3^{13}\equiv 3^{13}\pmod {25}$$.

As $$3^{20}\equiv 1$$ its a good guess that $$3^{10} \equiv \pm 1$$.

Many ways to do this but $$3^{10} = 3^3*3^3*3^3*3\equiv 27*27*27*3\equiv 2*2*2*3\equiv 24 \equiv -1 \pmod {20}$$. So $$3^{13}\equiv -3^3\equiv -27\equiv -2 \equiv 23$$.

.....OR.....

$$100 = 10^2$$

$$3^2 = 10-1$$

So $$3^{10} = (10-1)^5\equiv 50-1$$

$$3^{20} \equiv (50-1)^2 \equiv 1\pmod {100}$$.

So $$3^{333}\equiv 3^{13}\equiv 3^{10}*3^{3}\equiv (50-1)*27\equiv 50*(26+1)-27\equiv 50 - 27 \equiv 23\pmod{100}$$