2.3 Euler's Theorem | 2.3 Euler's Theorem | Unit 2: Structures | Mathematics for Computer Science | Electrical Engineering and Computer Science

Euler's Theorem

What is the value of $\Phi(175)$ , where $\Phi$ is Euler's Totient function?
Exercise 1
 Text Response Answer:120

Noting that $175 = 5^2 \cdot 7$ . It follows that $\Phi(175)=(5^2 - 5^1)(7-1) = 20 \cdot 6 = 120$ .
What is the remainder of $22^{12001}$ divided by $175$ ?
Exercise 2
 Text Response Answer:22

$22^{12001} = 22^{(120 \cdot 100) + 1} = 22^{120^{100}} \cdot 22 \equiv 1^{100} \cdot 22 \equiv 22 \text{ mod } 175$ .