\( \newcommand{\e}{\epsilon} \newcommand{\NN}{\mathbb{N}} \newcommand{\ZZ}{\mathbb{Z}} \newcommand{\gcd}{\mathop{gcd}} \newcommand{\mod}[1]{\quad(\mathop{mod} #1)} \newcommand{\divides}{\,|\,} \)
Definition 1. For \(n\in\NN\), Euler's totient function is defined to be the number of integers \(1\le k\le n\) which are relatively prime to \(n\).
Proposition 2. The function \(\phi\) is a multiplicative function.
Proof. Let \(m\) and \(n\) be two relatively prime positive integers. Consider the map \[ k + mn\ZZ \in \ZZ/mn\ZZ \longmapsto (k + m\ZZ, k + n\ZZ) \in \ZZ/m\ZZ \times \ZZ/n\ZZ \] First, this map is well-defined, for if \(k_1 + mn\ZZ = k_2 + mn\ZZ\) then \(mn \divides (k_1 - k_2)\) and so both \(m\) and \(n\) divide \(k_1 - k_2\) and so both \(k_1 + m\ZZ = k_2 + m\ZZ\) and \(k_1 + n\ZZ = k_2 + n\ZZ\). Also it is clearly a ring homomorphism. Further, the map is one-to-one because if \(k + mn\ZZ\) maps to zero it means that both \(m\) and \(n\) divide \(k\) and since \(\gcd(m,n) = 1\), then \(mn \divides k\). Since the cardinalities of \(\ZZ/m\ZZ \times \ZZ/n\ZZ\) and \(\ZZ/mn\ZZ\) are both \(mn\), the map must also be onto; thus it is a ring isomorphism. (This gives a quick non-constructive proof of the Chinese Remainder Theorem). Finally it follows that the group of invertibles of the two rinmgs \(\ZZ/m\ZZ \times \ZZ/n\ZZ\) and \(\ZZ/mn\ZZ\) correspond and so have the same cardinalities too. But these cardinalities are precisely \(\phi(m)\phi(n)\) and \(\phi(mn)\) respectively.
Lemma 3. For a prime \(p\) and \(k\in\NN\), \(\phi(p^k) = p^k - p^{k-1}\). In particular \(\phi(p) = p - 1\).
Proof. Of the \(p^k\) numbers between \(1\) and \(p^k\), the only ones which are not relatively prime to \(p^k\) are multiples of \(p\), of which there are precisely \(p^{k-1}\).
Proposition 4. (Euler's Product Formula) For any \(n\in\NN\), \[ \phi(n) = n \prod_{p \divides n} \left( 1 - \frac{1}{p} \right) \]
Proof. By the Fundamental Theorem of Arithmetic, \(n = p_1^{k_1} \cdots p_n^{k_n}\). So \[ \begin{align} \phi(n) &= \prod_{i=1}^n \phi(p_i^{k_i}) \\ &= \prod_{i=1}^n (p_i^{k_i} - p_i^{k_i}) \\ &= \prod_{i=1}^n p_i^{k_i} \left( 1 - \frac{1}{p_i} \right) \\ &= n \prod_{p \divides n} \left( 1 - \frac{1}{p} \right) \\ \end{align} \]
Proposition 5. (Euler's Theorem) For any \(a\) and \(n\) with \(\gcd(a, n) = 1\), \[ a^{\phi(n)} \equiv 1 \mod{n} \]
Proof. Since \(a\) belongs to the group of invertibles in \(\ZZ/n\ZZ\), by Lagrange's Theorem its order divides the order of the group, which is \(\phi(n)\).
Corollary 6. (Fermat's Little Theorem) If \(p\) is prime then for any whole number \(a\), \[ a^p \equiv a \mod{p} \]
Proof. If \(\gcd(a, p) = 1\) then \(a^{p-1} = a^{\phi(p)} \equiv 1 \mod{p}\). On the other hand if \(p\divides a\) then \(a^p\) and \(a\) are both congruent to zero.