# eulers theorme

• October 7th 2008, 08:51 PM
rmpatel5
eulers theorme
Use eulers theorem to find the least nonnegative residue modulo m of integer n

n=79^79, m=9
• October 7th 2008, 09:42 PM
o_O
Note that: $79 \equiv 7 \ (\text{mod }9)$, i.e. $79^{79} \equiv 7^{79} \ (\text{mod } 9)$

By Euler's theorem:
$\begin{array}{rcll}7^{\varphi (9)} & \equiv & 1 & (\text{mod } 9) \qquad \varphi (9) = \varphi (3^2) = 3 \cdot 2 = 6 \\ 7^6 & \equiv & 1 & (\text{mod } 9) \\ \left(7^6\right)^{13} & \equiv & 1^{13} & (\text{mod } 9) \\ & \vdots & & \end{array}$
• October 7th 2008, 09:49 PM
bigb
s
• October 7th 2008, 09:50 PM
rmpatel5
Quote:

Originally Posted by o_O
Note that: $79 \equiv 7 \ (\text{mod }9)$, i.e. $79^{79} \equiv 7^{79} \ (\text{mod } 9)$

By Euler's theorem:
$\begin{array}{rcll}7^{\varphi (9)} & \equiv & 1 & (\text{mod } 9) \qquad \varphi (9) = \varphi (3^2) = 3 \cdot 2 = 6 \\ 7^6 & \equiv & 1 & (\text{mod } 9) \\ \left(7^6\right)^{13} & \equiv & 1^{13} & (\text{mod } 9) \\ & \vdots & & \end{array}$

could u possibly finish out the problem and explain it as like an example problem. The book only talks about this topic and just dives into problem set without any examples. Also, why is it not 79^6 but rather 7^6??
• October 7th 2008, 10:00 PM
o_O
Well we want to find: $7^{79} \equiv a \ (\text{mod } 9)$ for some $a$.

We have that $\left(7^6\right)^{13} = 7^{78} \equiv 1 \ (\text{mod }9)$

Not too hard to see how we get to $7^{79}$.

As for calculating $\varphi (m)$, you need to find its prime power decomposition. With this, use the fact that:
(1) $\varphi (p^n) = p^{n-1} (p-1)$
(2) $\varphi (m)$ is multiplicative which means $\varphi (p_{1}^{e_{1}} \cdot p_{2}^{e_{2}}) = \varphi (p_{1}^{e_{1}}) \cdot \varphi (p_{2}^{e_{2}})$

where $p$ is prime.

For example: $\varphi (20) = \varphi (2^2 \cdot 5) = \varphi (2^2) \cdot \varphi (5) = 2^1 (2 - 1) \ \cdot \ 4 \ = 8$