next up previous contents
Next: Public Key Cryptography Up: The classical sets of Previous: Systems of congruences   Contents

Euler's Phi Function

Definition 6.9.1   For $ m \in \mathbb{N}$, define $ \phi(m)$ to be the number of nonnegative integers less than $ m$ which are coprime to $ m$.

$ \phi(1) = 1$. If $ p$ is prime then $ \phi(p) = p - 1$ and $ \phi(p^a)
= p^a \left( 1 - \frac{1}{p} \right)$.

Lemma 6.9.2   If $ m,n \in \mathbb{N}$ with $ (m,n) = 1$ then $ \phi(m n) = \phi(m)
\phi(n)$. $ \phi$ is said to be multiplicative.

Let $ U_m = \{ x \in \mathbb{Z}: 0 \le x < m, (x,m) = 1$, the reduced set of residues or set of invertible elements. Note that $ \phi(m) =
\lvert U_m\rvert $.

Proof. If $ a \in U_m$ and $ b \in U_n$ then there exists a unique $ x \in
U_{mn}$. with $ c \equiv a \pmod{m}$ and $ c \equiv b \pmod{n}$ (by theorem (8.1)). Such a $ c$ is prime to $ mn$, since it is prime to $ m$ and to $ n$. Conversely, any $ c \in U_{mn}$ arises in this way, from the $ a \in U_m$ and $ b \in U_n$ such that $ a
\equiv c \pmod{m}$, $ b \equiv c \pmod{n}$. Thus $ \lvert U_{mn}\rvert = \lvert U_m\rvert
\lvert U_n\rvert $ as required. $ \qedsymbol$

An immediate corollary of this is that for any $ n \in \mathbb{N}$,

$\displaystyle \phi(n) = n \prod_{\substack{p \mid n \\  p\text{ prime}}} \left( 1 -
 \frac{1}{p} \right).$    

Theorem 6.9.3 (Fermat-Euler Theorem)   Take $ a$ and $ m$ in $ \mathbb{N}$ such that $ (a,m) = 1$. Then $ a^{\phi(m)} \equiv 1 \pmod{m}$.

Proof. Multiply each residue $ r_i$ by $ a$ and reduce modulo $ m$. The $ \phi(m)$ numbers thus obtained are prime to $ m$ and are all distinct. So the $ \phi(m)$ new numbers are just $ r_1, \dots, r_{\phi(m)}$ in a different order. Therefore

$\displaystyle r_1 r_2 \dots r_{\phi(m)}$ $\displaystyle \equiv a r_1 a r_2 \dots a r_{\phi(m)}
 \pmod{m}$    
  $\displaystyle \equiv a^{\phi(m)} r_1 r_2 \dots r_{\phi(m)} \pmod{m}.$    

Since $ (m,r_1 r_2 \dots r_{\phi(m)}) = 1$ we can divide to obtain the result. $ \qedsymbol$

Corollary 6.9.4 (Fermat's Little Theorem)   If $ p$ is a prime and $ a \in \mathbb{Z}$ such that $ p \nmid a$ then $ a^{p-1}
\equiv 1 \pmod{p}$.

Remark 6.9.5 (For algebraists)   This can also be seen as a consequence of Lagrange's Theorem, since $ U_m$ is a group under multiplication modulo $ m$.

Fermat's Little Theorem can be used to check that $ n \in \mathbb{N}$ is prime. If there exists an $ a$ coprime to $ n$ such that $ a^{n-1}
\not\equiv 1 \pmod{n}$ then $ n$ is not prime.

Subsections
next up previous contents
Next: Public Key Cryptography Up: The classical sets of Previous: Systems of congruences   Contents
root 2002-06-10