# Find the last two digits of $33^{100}$

Find the last two digits of $33^{100}$

By Euler's theorem, since $\gcd(33, 100)=1$, then $33^{\phi(100)}\equiv 1 \pmod{100}$. But $\phi(100)=\phi(5^2\times2^2)=40.$

So $33^{40}\equiv 1 \pmod{100}$ Then how to proceed?

With the suggestion of @Lucian:

$33^2\equiv-11 \pmod{100}$ then $33^{100}\equiv(-11)^{50}\pmod{100}\equiv (10+1)^{50}\pmod{100}$

By using the binomial expansion, we have: $33^{100}\equiv (10^{50}+50\cdot 10^{49}+ \cdots + 50\cdot 10+1)\pmod{100}$ $\implies 33^{100}\equiv (50\cdot 10+1)\pmod{100}\equiv 01 \pmod{100}$

You can use fast exponentiation: modulo $100$ $$33^2\equiv -11,\quad 33^4\equiv 21,\quad 33^8\equiv 441\equiv 41,\quad 33^{16}\equiv1681\equiv -19$$ whence $\,33^{20}\equiv -19\cdot 21 =-(20-1)(20+1)\equiv 1$.

Hint: $33^2\equiv-11\bmod100$.

• $(-11)^{50}=11^{50}=(10+1)^{50}=\ldots$ Commented Jun 28, 2015 at 13:54
• Not understand. Would you please give further steps. Commented Jun 28, 2015 at 13:59
• @math131: Expand using the binomial theorem, and notice that all terms except the last two are multiples of $100$. Commented Jun 28, 2015 at 14:05
• I have edited my answer. Please check. Commented Jun 28, 2015 at 15:04
• @math131: Yes, you are correct. Mathematica confirms the result. Commented Jun 28, 2015 at 16:13

Another approach:

$$\text{Euler's formula: }\quad a^{\phi(n)}\equiv 1 \pmod{n} \text{ when} \gcd(a,n)=1$$

$$\phi(100)=\phi(2^2)\phi(5^2)=2\cdot 20=40$$

$$\gcd(100,33)=1$$

$$33^{40}\equiv 1 \pmod {100}$$

$$33^{100}\equiv (33^{40})^{2}3^{20}\equiv 3^{20}\pmod {100}$$

$$\equiv (3^5)^4\equiv43^4\equiv 49^2\equiv 01\pmod {100}$$

$$(33)^{100}\equiv(33)^{5\cdot5\cdot4}\equiv(93)^{5\cdot4}\equiv(93)^4\equiv 01\pmod{100}$$

\begin{align} 33^{100}&=9^{50}\cdot11^{100}\\ &=(1-10)^{50}(1+10)^{100}\\ &=(1-50\cdot10+\cdots)(1+100\cdot10+\cdots)\\ &\equiv1\mod100 \end{align}

It can be proved that for any odd number $$n$$ not ending with 5,

$${{n}^{20}}\equiv 1\,(\bmod \ 100)$$

By Euler's theorem, $$\phi (25)=25\left( 1-\frac{1}{5} \right)=20$$ and $$n$$ is coprime to 25, so

$${{n}^{20}}\equiv 1\,(\bmod \ 25)$$ ...... (1)

As square of any natural number is either of the type $$4k$$ or $$4k+1$$, hence

$${{n}^{20}}\equiv 1(\bmod \ 4)$$ ....... (2)

Combining the results of (1) and (2), we get,

$${{n}^{20}}\equiv 1\,(\bmod \ 100)$$

So last two digits of numbers like $${{33}^{20}},\ {{17}^{20}},\ {{19}^{20}},\,{{47}^{20}}$$ etc are $$01$$.