Difference between revisions of "Euler's theorem"

(Question)
(Question)
 
Line 5: Line 5:
  
 
===Question===
 
===Question===
Find <math>7^{18} \pmod 5</math>
+
Find <math>7^{18} \pmod{54}</math>
  
 
===Solution===
 
===Solution===
 
<math>\phi(54) = 54*1/2*2/3 = 18</math> Therefore <math>7^{18} \equiv {7}^{\phi(54)} \equiv \boxed{1} \quad\mod 54</math>
 
<math>\phi(54) = 54*1/2*2/3 = 18</math> Therefore <math>7^{18} \equiv {7}^{\phi(54)} \equiv \boxed{1} \quad\mod 54</math>

Latest revision as of 18:58, 3 August 2023

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$