1. ## Last two digits...

I have to find the last two digits of 222227^2010.

So I know that this gets reduced to 27^2010 mod 100

But I don't know how to solve 27^x = 1(mod 100) to get this process going. Or am I going about it wrong?

I have to find the last two digits of 222227^2010.

So I know that this gets reduced to 27^2010 mod 100

But I don't know how to solve 27^x = 1(mod 100) to get this process going. Or am I going about it wrong?
$\phi(100)=40$ and $(27,100)=1\implies 27^{40}\equiv1\bmod{100}$

Now $2010=50\cdot40+10 \implies 27^{2010}=27^{50\cdot40+10}=\left(27^{40}\right)^{ 50}\cdot27^{10}\equiv1\cdot27^{10}=27^{10}\bmod{10 0}$.

Observe $10=8+2=2^3+2$

$27^2\equiv 29\bmod{100}$
$27^4=\left(27^2\right)^2\equiv 29^2\equiv 41\bmod{100}$
$27^8=\left(27^4\right)^2\equiv 41^2\equiv 81\bmod{100}$

Thus $27^{10}=27^{8+2}=27^8\cdot27^2\equiv 81\cdot29=2349\equiv49\bmod{100}$

Therefore the last two digits of $222227^{2010}$ are $49$.

3. Originally Posted by chiph588@
$\phi(100)=40$ and $(27,100)=1\implies 27^{40}\equiv1\bmod{100}$
This is the part I don't get. What does the phi mean, and what does the (27,100) mean? How did you get that 27^40 = 1 so simply?

4. $\phi(100)$ is the "totient function", the number of integers less than 100 and coprime to 100. Chiph588 then uses "Euler's theorem": For any a coprime to n, $a^{\phi(n)}\equiv 1 (mod n)$.

5. What's a quick way to figure out the totient function?

6. $27^{2010} = 3^{6030} = 3^{6028+2} = 9 (81^{1507})$

$81^{1507} = (80 + 1)^{1507}$

$= 80^{1507} + 80^{1506}(1507) + .... + \frac{1507(1506)}{2} 80^2 + 1507(80) + 1$

$\equiv 60+1 \bmod{100} \equiv 61 \bmod{100}$

Therefore ,

$27^{2010} \equiv 9(61) \bmod{100} \equiv 549 \equiv 49 \bmod{100}$

What's a quick way to figure out the totient function?

You may show that $f: x \to ax ~ a,x \in \mathbb{U}(m)$ is a bijection . Then , obtaining the product :

$\prod_{x \in \mathbb{U}(m)} x \equiv \prod_{x \in \mathbb{U}(m)} a x$

$1 \equiv a^{\phi(m)}$

7. Originally Posted by simplependulum
$= 80^{1507} + 80^{1506}(1507) + .... + \frac{1507(1506)}{2} 80^2 + 1507(80) + 1$

$\equiv 60+1 \bmod{100} \equiv 61 \bmod{100}$
What's going on here?

I used a very primitive approach . . .

Find the last two digits of: . $N \;=\;222227^{2010}$

I know that this gets reduced to: . $27^{2010}\text{ (mod 100)}$

We have: . $N \;=\;\left(3^3\right)^{2010} \;=\;3^{6030}$

I found that:

. . $\begin{array}{cc}3^n & \text{ends in} \\ \hline
3^1 & 03 \\ 3^2 & 09 \\ 3^3 & 27 \\ 3^4 & 81 \\ 3^5 & 43 \\ \vdots & \vdots \\
3^{10} & 49 \\ \vdots & \vdots \\ 3^{20} & 01 \end{array}$

Hence: . $3^{20} \:\equiv\:01\text{ (mod 100)}$

We have: . $N \;=\;3^{6030} \;=\;3^{20(301) + 10} \;=\;\left(3^{20}\right)^{301}\cdot 3^{10}$

Hence: . $N \;\equiv\;(01)^{301}\cdot 3^{10}\text{ (mod 100)}$

. . . . . . . . $\equiv\;3^{10}\text{ (mod 100)}$

. . . . . . . . $\equiv\;49\text{ (mod 100)}$

Therefore, $222227^{2010}$ ends in 49.