1. ## eulers theorme

Use eulers theorem to find the least nonnegative residue modulo m of integer n

n=79^79, m=9

2. 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}$

3. s

4. 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??

5. 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$