Euler's Theorem

Dependencies:

1. Coprime Used in definition
2. Modular Equivalence Used in definition
3. Euler's Totient Function Used in definition
4. Zn* is a group Used in proof
5. Group element to the power group size equals identity Used in proof

Dependencies:

1. Coprime Used in definition
2. Modular Equivalence Used in definition
3. Euler's Totient Function Used in definition
4. Multiplication permutes Zn* Used in proof

If $a$ and $n$ are coprime, then $a^{\phi(n)} \equiv 1 \pmod{n}$, where $\phi$ is the Euler's Totient function.

Proof using Abstract Algebra

• $\mathbb{Z}_n^*$ is a group under multiplication modulo $n$.
• The order of $\mathbb{Z}_n^*$ is $\phi(n)$ as per the definition of $\mathbb{Z}_n^*$ and $\phi(n)$.
• $\forall a \in G, a^{|G|} = e$.

These facts combined together complete the proof.

Direct Proof

Let $\mathbb{Z}_n^* = \{x_1, x_2, \ldots\}$ be the set of all numbers less than $n$ which are coprime to $n$. $\mathbb{Z}_n^*$ has size $\phi(n)$, as per the definition of $\phi(n)$.

Let $a\mathbb{Z}_n^* = \{ax_1, ax_2, \ldots\}$. $\Rightarrow a\mathbb{Z}_n^* = \mathbb{Z}_n^*$.

$$ \prod \left(a\mathbb{Z}_n^*\right) \equiv \prod_{i=1}^{\phi(n)} (ax_i) \equiv a^{\phi(n)} \prod_{i=1}^{\phi(n)} x_i \equiv a^{\phi(n)} \prod \mathbb{Z}_n^* \pmod{n} $$

$$ \Rightarrow a^{\phi(n)} \equiv 1 \pmod{n} $$

Further Reading

https://en.wikipedia.org/wiki/Euler%27s_theorem

Dependency for: None

Info:

• Depth: 7
• Number of transitive dependencies: 27

Transitive dependencies:

1. Every number has a prime factorization
2. Euler's Totient Function
3. Coprime
4. Integer Division Theorem
5. GCD is the smallest Linear Combination
6. Existence of Modular Inverse
7. Euclid's lemma
8. Modular Equivalence
9. ab is coprime to x iff a and b are coprime to x
10. If x divides ab and x is coprime to a, then x divides b
11. Multiplication permutes Zn*
12. Group
13. Coset
14. Size of coset equals size of subset
15. Identity of a group is unique
16. Order of element in finite group is finite
17. Subgroup
18. Inverse of a group element is unique
19. gH = H iff g in H
20. Two cosets are either identical or disjoint
21. Lagrange's Theorem
22. Zn* is a group
23. Conditions for a subset to be a subgroup
24. Cyclic Group
25. Order of cyclic subgroup is order of generator
26. Order of element divides order of group
27. Group element to the power group size equals identity