Modular Exponentiation

**matt.qmar** · November 13th 2010, 11:46 AM

Hello!

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

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

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

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

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

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

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

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

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

Anybody have any ideas? Thanks!!

**PaulRS** · November 13th 2010, 01:46 PM

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

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

Now what can you say about $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

**melese** · November 13th 2010, 01:54 PM

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 $a, n \in Z$ and $gcd(a,n)=1$ and Euler's phi-function,

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

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

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

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

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

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

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

Anybody have any ideas? Thanks!!

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

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

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

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

Thread: Modular Exponentiation

LinkBack

Thread Tools

Display