Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Euler's theorem

Revision as of 09:21, 27 August 2016 by Mathletema (talk | contribs) (Created the page as well as added an example with solution)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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} \quad\mod 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=80084"