# Section6.3Fermat's and Euler's Theorems¶ permalink

The Euler $\phi$-function is the map $\phi : {\mathbb N } \rightarrow {\mathbb N}$ defined by $\phi(n) = 1$ for $n=1$, and, for $n \gt 1$, $\phi(n)$ is the number of positive integers $m$ with $1 \leq m \lt n$ and $\gcd(m,n) = 1$.

From Proposition 3.4, we know that the order of $U(n)$, the group of units in ${\mathbb Z}_n$, is $\phi(n)$. For example, $|U(12)| = \phi(12) = 4$ since the numbers that are relatively prime to 12 are 1, 5, 7, and 11. For any prime $p$, $\phi(p) = p-1$. We state these results in the following theorem.

The following theorem is an important result in number theory, due to Leonhard Euler.

##### Proof

If we consider the special case of Euler's Theorem in which $n = p$ is prime and recall that $\phi(p) = p - 1$, we obtain the following result, due to Pierre de Fermat.