Proving Euler's Theorem

Let \((a, m) = 1\) and let the set \(\{ar_1 \ldots ar_k \}\) be a reduced residue system mod \(m\) where \(k = \phi(m)\). To prove Euler's theorem, we first need to show that \(ar_i\) are all coprime to \(m\) and distinct mod \(m\). If \((r, m) = 1\) and \((a, m) = 1\) then \((ar, m) = 1\), this shows \(ar\) is coprime to \(m\). Also, if we had \(ar_i ≡ ar_j \mod m\), then:

$$ m|ar_i - ar_j = a(r_i - r_j ) $$

If (a, m) = 1 then \(m|r_i - r_j\) (using this lemma):

$$ m|r_i - r_j ⇒ r_i ≡ r_j \mod m $$

which cannot happen unless i = j. This shows all \(ar\) are distinct, therefore \(\{ar_1 \ldots ar_k \}\) is also a reduced residue system mod \(m\). If \(\gcd(r_1, m) = 1\) and \(\gcd(r_2, m) = 1\), then \(\gcd(r_1r_2, m) = 1\), which means:

$$\begin{align} r_1r_2 \ldots r_k &≡ 1 \mod m \\ ar_1ar_2 \ldots ar_k &≡ 1 \mod m \\ a^{\phi(m)}(r_1r_2 \ldots r_k) &≡ 1 \mod m \end{align}$$

If \( [(1)*(r_1r_2 \ldots r_k)] ≡ [(a^{\phi(m)}) * (r_1r_2 \ldots r_k)]\) and \((r_1r_2 \ldots r_k, m) = 1\), then \(a^{\phi(m)} ≡ 1\) (using this lemma).

Let \((a, m) = 1\) and let the set \(\{ar_1 \ldots ar_k \}\) be a reduced residue system mod \(m\) where \(k = \phi(m)\). To prove Euler's theorem, we first need to show that \(ar_i\) are all coprime to \(m\) and distinct mod \(m\). If \((r, m) = 1\) and \((a, m) = 1\) then \((ar, m) = 1\), this shows \(ar\) is coprime to \(m\). Also, if we had \(ar_i ≡ ar_j \mod m\), then:

$$ m|ar_i - ar_j = a(r_i - r_j ) $$

If (a, m) = 1 then \(m|r_i - r_j\) (using this lemma):

$$ m|r_i - r_j ⇒ r_i ≡ r_j \mod m $$

which cannot happen unless i = j. This shows all \(ar\) are distinct, therefore \(\{ar_1 \ldots ar_k \}\) is also a reduced residue system mod \(m\). If \(\gcd(r_1, m) = 1\) and \(\gcd(r_2, m) = 1\), then \(\gcd(r_1r_2, m) = 1\), which means:

$$\begin{align} r_1r_2 \ldots r_k &≡ 1 \mod m \\ ar_1ar_2 \ldots ar_k &≡ 1 \mod m \\ a^{\phi(m)}(r_1r_2 \ldots r_k) &≡ 1 \mod m \end{align}$$

If \( [(1)*(r_1r_2 \ldots r_k)] ≡ [(a^{\phi(m)}) * (r_1r_2 \ldots r_k)]\) and \((r_1r_2 \ldots r_k, m) = 1\), then \(a^{\phi(m)} ≡ 1\) (using this lemma).