Art of Problem Solving

AoPS Online

Euler's theorem

Contents

1 Theorem
2 Example
- 2.1 Question
- 2.2 Solution

Theorem

Euler's Theorem states that ${a}^{\phi(n)} \equiv 1 \quad\mod n$ , where $\phi(n)$ is Euler's Totient Theorem, and $a$ and $n$ are coprime.

Example

Question

Find $7^{18} \pmod{54}$

Solution

$\phi(54) = 54*1/2*2/3 = 18$ Therefore $7^{18} \equiv {7}^{\phi(54)} \equiv \boxed{1} \quad\mod 54$

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Euler%27s_theorem&oldid=196399"

© 2024 AoPS Incorporated