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