State/Fermat Euler theorem

From SlugmathWiki

Theorem
Proof

Theorem: (Fermat-Euler theorem) Suppose that $m$ is a positive integer. Suppose that $a \in \ZZ$ and $GCD(a,m) = 1$. Then, $$\bar a^{\phi(m)} = \bar 1, \mbox{ modulo } m,$$ where $\phi(m)$ denotes the totient of $m$.

Logical Connections

This statement logically relies on the following definitions and statements: Def/Residue, Def/Totient, Def/Invertible residue, State/Relative primality to the modulus is equivalent to invertibility of a residue, State/Products of invertible residues are invertible, Def/Permutation

The following statements and definitions rely on the material of this page: State/Fermats little theorem

To visualize the logical connections between this statements and other items of mathematical knowledge, you can visit the following cluster(s), and click the "Visualize" tab: Clust/Modular arithmetic

Suppose that $m$ is a positive integer, $a \in \ZZ$, and $GCD(a,m) = 1$.

Let $Res(m)$ denote the set of residues mod $m$, i.e.,

$$Res(m) = \{ \bar 0, \bar 1, \ldots, \overline{m-1} \}.$$ Let $\Phi(m)$ denote the set of invertible residues, mod $m$, i.e., $$\Phi(m) = \{ \bar x \in Res(m) \mbox{ such that } \exists \bar y \in Res(m), \mbox{ such that } \bar x \bar y = \bar 1 \}.$$ Thus the totient of $m$ is, by definition, $$\phi(m) = \vert \Phi(m) \vert.$$ For any integer $x$, recall that $\bar x$ is invertible (modulo $m$) if and only if $GCD(x,m) = 1$. In particular, $\bar a \in \Phi(m)$. Define a function $\mu_{\bar a} \colon \Phi(m) \rightarrow \Phi(m)$, by the formula: $$\mu_{\bar a}(\bar x) = \bar a \bar x,$$ for all $\bar x \in \Phi(m)$. We claim that $\mu_{\bar a}$ is an bijective function from $\Phi(m)$ to itself.

	Suppose that $\bar x \in \Phi(m)$.
	Observe that $\mu_{\bar a}(\bar x) = \bar a \bar x$ lies in $\Phi(m)$, since the product of invertible residues is an invertible residue. Hence $\mu_{\bar a}$ is a function from $\Phi(m)$ to itself. Since $\bar a \in \Phi(m)$, there exists a residue $\bar b$ such that $\bar b \bar a = \bar 1$. In particular, $\bar b \in \Phi(m)$, and $\mu_{\bar b}$ is a function from $\Phi(m)$ to itself, by the same argument that applied to $\mu_{\bar a}$. Observe now that: $$[\mu_{\bar b} \circ \mu_{\bar a}](\bar x) = \mu_{\bar b}(\bar a \bar x) = \bar b \bar a \bar x = \bar x.$$ $$[\mu_{\bar a} \circ \mu_{\bar b}](\bar x) = \mu_{\bar a}(\bar b \bar x) = \bar a \bar b \bar x = \bar x.$$ Hence $\mu_{\bar b} \circ \mu_{\bar a}$ and $\mu_{\bar a} \circ \mu_{\bar b}$ are both equal to the identity function from $\Phi(m)$ to itself.
	Hence $\mu_{\bar a}$ is a bijective function from $\Phi(m)$ to itself.

Thus $\mu_{\bar a}$ is a permutation of $\Phi(m)$.

Now, we find that: $$\prod_{\bar n \in \Phi(m)} \bar n = \prod_{\bar n \in \Phi(m)} \mu_{\bar a}(\bar n) = \prod_{\bar n \in \Phi(m) } \bar a \bar n = \bar a^{\phi(m)} \prod_{\bar n \in \Phi(m)} \bar n.$$ The first equality arises from the fact that $\mu_{\bar a}$ is a permutation of the indexing set $\Phi(m)$ of the product. The second equality arises from the definition of $\mu_{\bar a}$. The third equality follows from "pulling out" $\bar a$ from each term of the product via commutativity of multiplication, and observing that the indexing set $\Phi(m)$ has cardinality $\phi(m)$.

By transitivity of equality, we find that: $$\bar P = \bar a^{\phi(m)} \bar P, \mbox{ if } \bar P = \prod_{\bar n \in \Phi(m)} \bar n.$$ Since $\bar P$ is a product of invertible residues, and the product of invertible residues is an invertible residue, we find that $\bar P$ is an invertible residue. Hence, multiplying the previous equation by a multiplicative inverse of $\bar P$ yields: