# Proof

(related to Theorem: Euler-Fermat Theorem)

• By hypothesis, $m > 1$ is a positive integer, $a\perp m$ are co-prime, and $\phi(m)$ is the Euler function of $m.$
• Let $a_1,\ldots,a_{\phi(m)}$ be a reduced residue system modulo $m.$
• Since $a\perp m$, according to the creation of reduced residue systems from others, the numbers $aa_1,\ldots,aa_{\phi(m)}$ also build a reduced residue system.
• Therefore, the product of the integers $a_1,\ldots,a_{\phi(m)}$ and the product of the integers $aa_1,\ldots,aa_{\phi(m)}$ are congruent modulo $m.$
• Therefore, the following equation holds $$\left(1\cdot\prod_{n=1}^{\phi(m)}a_n\right)(m)\equiv\left(\prod_{n=1}^{\phi(m)}a a_n\right)(m)\equiv \left(a^{\phi(m)}\cdot \prod_{n=1}^{\phi(m)}a_n\right)(m).$$
• By definition of a reduced residue system modulo $m,$ the numbers $a_1,\ldots,a_{\phi(m)}$ are all co-prime to $m,$ and thus, the product $\prod_{n=1}^{\phi(m)}a_n$ is also co-prime to $m.$
• Therefore, according to cancellation of congruences eith factor co-prime to module, it follows $$1(m)\equiv a^{\phi(m)}(m).$$

Github: ### References

#### Bibliography

1. Landau, Edmund: "Vorlesungen über Zahlentheorie, Aus der Elementaren Zahlentheorie", S. Hirzel, Leipzig, 1927