Proof. We have \[\begin{aligned} \gcd(a, m) = 1 &\iff \exists u, v \in \mathbb{Z}\ \text{ such that }\ ua + v m = 1\\ &\iff \exists u, v\in\mathbb{Z}\ \text{ such that }\ ua = 1 - v m\\ &\iff \exists u \in \mathbb{Z}\ \text{ such that } ua = 1 \bmod m\\ &\iff a \bmod m \ \text{is invertible}. \end{aligned}\]

Proof. Thanks to the Chinese remainder theorem, we know that the rings \(\mathbb{Z}/ mn\mathbb{Z}\) and \((\mathbb{Z}/ m\mathbb{Z}) \times (\mathbb{Z}/ n\mathbb{Z})\) are isomorphic. It follows that their unit groups are isomorphic; but the unit group of \((\mathbb{Z}/ m\mathbb{Z}) \times (\mathbb{Z}/ n\mathbb{Z})\) is obviously just \(U_m \times U_n.\)

Proof. An integer is coprime to \(p^k\) iff it is not a multiple of \(p.\) Out of the \(p^k\) integers \(\{0, 1, \dots, p^{k-1} - 1\},\) exactly \(p^{k-1}\) of them are multiples of \(p.\) So \(\varphi(p^k) = p^k - p^{k-1} = p^{k-1}(p - 1).\)

Proof. Euler’s result is just Lagrange’s theorem from group theory (“the order of any element of a group divides the size of the group”) applied to the group \(U_m.\)

For Fermat’s little theorem, specialising Euler’s theorem shows that \(a^{p-1} = 1 \bmod p\) for all \(a\) coprime to \(p,\) and it follows that \(a^p = a \bmod p.\) On the other hand, if \(a\) is not coprime to \(p,\) then \(p \mid a,\) so \(a^p = a = 0 \bmod p\) and the result holds in this case too.

Proof. For each \(d\) dividing \(n,\) the map \(r \mapsto \tfrac{n}{d} \cdot r\) gives a bijection between the sets \[S_d = \left\{ r \in \{0, \dots, d - 1\} : \gcd(r, d) = 1\right\}\] and \[T_d = \left\{ s \in \{0, \dots, n - 1\} : \gcd(s, n) = \tfrac{n}{d} \right\}.\] So we have \(\# T_d = \# S_d = \varphi(d).\) However, each \(s \in T = \{0, \dots, n-1\}\) lies in exactly one of the sets \(T_d\); so the sum of their sizes must be \(\#T = n.\)

Proof. Note that \(a\) is a primitive root iff the order of \(a\) in \(U_p\) is exactly \(p - 1\) (so Euler’s theorem is the “best possible” bound).

Let \(n = p - 1\); and for \(d \mid n,\) let \(\psi(d)\) denote the number of elements of \(U_p\) whose order is precisely \(d.\) We claim that for any \(d \mid n,\) either \(\psi(d) = 0,\) or \(\psi(d) = \varphi(d).\)

To see this, suppose \(\psi(d) > 0.\) Then there exists some element \(a\) of order exactly \(d.\) Hence the set \(\{1, a, \dots, a^{d-1}\}\) has \(d\) distinct elements, and all of them have order dividing \(d\); that is, they are roots of \(X^d - 1.\) Since this polynomial has degree \(d\) (and \(\mathbb{F}_p\) is a field), it can’t have more than \(d\) roots in \(\mathbb{F}_p.\) So our set is actually all of the elements of \(U_p\) of order dividing \(d.\) In particular, \(\psi(d)\) is the number of \(h\) in \(\{0, \dots, d-1\}\) such that \(a^h\) has order exactly \(d.\) However, \(a^h\) has order exactly \(d\) iff \(h\) is coprime to \(d\); so we conclude that \(\psi(d) = \varphi(d).\)

So it certainly follows that \(\psi(d) \leqslant\varphi(d)\) for every \(d.\) But every element of \(U_n\) must have some order, so \[\sum_{d \mid n} \psi(d) = n = \sum_{d \mid n} \varphi(d).\] It follows that in fact \(\psi(d) = \varphi(d)\) for all \(d,\) and in particular \(\psi(n) = \varphi(n).\) As \(\varphi(n) > 0,\) this shows that elements of order exactly \(n\) exist.