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?
$\displaystyle \phi(100)=40$ and $\displaystyle (27,100)=1\implies 27^{40}\equiv1\bmod{100}$

Now $\displaystyle 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 $\displaystyle 10=8+2=2^3+2$

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

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

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

3. Originally Posted by chiph588@
$\displaystyle \phi(100)=40$ and $\displaystyle (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. $\displaystyle \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, $\displaystyle a^{\phi(n)}\equiv 1 (mod n)$.

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

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

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

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

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

Therefore ,

$\displaystyle 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 $\displaystyle f: x \to ax ~ a,x \in \mathbb{U}(m)$ is a bijection . Then , obtaining the product :

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

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

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

$\displaystyle \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: .$\displaystyle N \;=\;222227^{2010}$

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

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

I found that:

. . $\displaystyle \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: .$\displaystyle 3^{20} \:\equiv\:01\text{ (mod 100)}$

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

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

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

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

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