1. ## Modular Exponentiation

Hello!

I am trying to apply a result from a theorem to an example.

There is a thorem that states, for $\displaystyle a, n \in Z$ and $\displaystyle gcd(a,n)=1$ and Euler's phi-function,

$\displaystyle a^{\phi(n)}\ mod\ n = 1\ mod\ n$

So I am trying to determine the last two digits of $\displaystyle 3^{3^{100}}$

So, Essentially, $\displaystyle 3^{3^{100}}\ mod\ 100 = ?$

Well, $\displaystyle 3^{3^{100}} = 27^{100}$ I believe.

Then, since
$\displaystyle gcd(27, 100) = 1$,
we have $\displaystyle 27^{\phi(100)}\ mod\ 100= 1\ mod\ 100$

Well, $\displaystyle \phi(100) = \phi(5^2)\phi(2^2) = (5^2 - 5)(2^2 - 2) = (20)(2) = 40$

so... $\displaystyle 27^{40}\ mod\ 100 = 1\ mod\ 100$
then $\displaystyle 27^{80}\ mod\ 100 = 1\ mod\ 100$
but we still have a $\displaystyle 27^{20}\ mod\ 100$ left to deal with. That is where I'm stuck.

Anybody have any ideas? Thanks!!

2. $\displaystyle \phi(100)=40$ So we have $\displaystyle 3^{40}\equiv 1 (\bmod.100)$

Now note that if $\displaystyle a\equiv b (\bmod.40)$ then $\displaystyle a = b + 40\cdot k$ and so $\displaystyle 3^{a} = 3^b\cdot \left(3^{40}\right)^k \equiv 3^b\cdot 1^k \equiv 3^b (\bmod.100)$ so to find $\displaystyle 3^{3^{100}}(\bmod.100)$ we may instead find $\displaystyle 3^{100} (\bmod.40)$ and raise 3 to that -module 100.

Now what can you say about $\displaystyle 3^{100} (\bmod.40)$ ? ... 3⁴ = ?

Note that if you didn't spot the thing about 3⁴ you could still repeat the procedure above for 3¹⁰⁰ mod 40

3. Originally Posted by matt.qmar
Hello!

I am trying to apply a result from a theorem to an example.

There is a thorem that states, for $\displaystyle a, n \in Z$ and $\displaystyle gcd(a,n)=1$ and Euler's phi-function,

$\displaystyle a^{\phi(n)}\ mod\ n = 1\ mod\ n$

So I am trying to determine the last two digits of $\displaystyle 3^{3^{100}}$

So, Essentially, $\displaystyle 3^{3^{100}}\ mod\ 100 = ?$

Well, $\displaystyle 3^{3^{100}} = 27^{100}$ I believe.

Then, since
$\displaystyle gcd(27, 100) = 1$,
we have $\displaystyle 27^{\phi(100)}\ mod\ 100= 1\ mod\ 100$

Well, $\displaystyle \phi(100) = \phi(5^2)\phi(2^2) = (5^2 - 5)(2^2 - 2) = (20)(2) = 40$

so... $\displaystyle 27^{40}\ mod\ 100 = 1\ mod\ 100$
then $\displaystyle 27^{80}\ mod\ 100 = 1\ mod\ 100$
but we still have a $\displaystyle 27^{20}\ mod\ 100$ left to deal with. That is where I'm stuck.

Anybody have any ideas? Thanks!!
Euler's Theorem. Let $\displaystyle n$ be a positive integer. Then $\displaystyle a^{\phi(n)}\equiv1\pmod n$, if $\displaystyle \displaystyle gcd(a,n)=1$.

First $\displaystyle 3^{3^{100}}$ actually means $\displaystyle 3^{(3^{100})}$, not $\displaystyle (3^3)^{100}$!

Since $\displaystyle \phi(100)=40$ we want to find the remainder of $\displaystyle 3^{100}$ when divided by $\displaystyle 40$. Begin with the observation that $\displaystyle 3^4=81\equiv1\pmod{40}$, so $\displaystyle 3^{100}=(3^4)^{25}\equiv1\pmod{40}$. Therefore $\displaystyle 3^{100}=1+40\cdot k$ for some positve integer $\displaystyle k$.

Now we calculate modulo 100. Euler's Theorem implies that $\displaystyle 3^{40}\equiv1\pmod{100}$; thus $\displaystyle 3^{3^{100}}=3^{1+40k}=3\cdot(3^{40})^k\equiv3\cdot 1^k\equiv3\pmod{100}$.