Let $n$ be a positive integer and $a$ an integer with $\gcd(a, n) = 1$. We prove that $a^{\phi(n)} \equiv 1 \pmod{n}$.

Let $r_1, r_2, \ldots, r_{\phi(n)}$ be the integers in $\{1, 2, \ldots, n\}$ that are coprime to $n$. These form a reduced residue system modulo $n$.

Claim: The set $\{ar_1, ar_2, \ldots, ar_{\phi(n)}\}$ is also a reduced residue system modulo $n$.

Proof of claim:

• Each $ar_i$ is coprime to $n$ since $\gcd(a, n) = \gcd(r_i, n) = 1$.
• The products are distinct modulo $n$: if $ar_i \equiv ar_j \pmod{n}$, then since $\gcd(a, n) = 1$, we can cancel to get $r_i \equiv r_j \pmod{n}$, so $i = j$.
• There are $\phi(n)$ elements, so they form a complete reduced residue system.

Therefore, the multisets $\{r_1, r_2, \ldots, r_{\phi(n)}\}$ and $\{ar_1, ar_2, \ldots, ar_{\phi(n)}\}$ are the same modulo $n$.

Taking the product of all elements: $ar_1 \cdot ar_2 \cdots ar_{\phi(n)} \equiv r_1 \cdot r_2 \cdots r_{\phi(n)} \pmod{n}$

This simplifies to: $a^{\phi(n)} (r_1 r_2 \cdots r_{\phi(n)}) \equiv r_1 r_2 \cdots r_{\phi(n)} \pmod{n}$

Let $R = r_1 r_2 \cdots r_{\phi(n)}$. Since each $r_i$ is coprime to $n$, their product $R$ is also coprime to $n$. Therefore, we can cancel $R$ from both sides: $a^{\phi(n)} \equiv 1 \pmod{n}$

This completes the proof.

Let $n_1, n_2, \ldots, n_k$ be pairwise coprime positive integers, and let $a_1, a_2, \ldots, a_k$ be any integers. We prove that the system: $x \equiv a_i \pmod{n_i}, \quad i = 1, 2, \ldots, k$ has a solution.

Let $N = n_1 n_2 \cdots n_k$ and define $N_i = N/n_i$ for each $i$.

Key observation: Since the moduli are pairwise coprime, $\gcd(N_i, n_i) = 1$ for each $i$.

By Bézout's identity, there exists an integer $M_i$ such that: $N_i M_i \equiv 1 \pmod{n_i}$

Now consider: $x = a_1 N_1 M_1 + a_2 N_2 M_2 + \cdots + a_k N_k M_k$

For any $j \in \{1, 2, \ldots, k\}$, we have $n_j \mid N_i$ for all $i \neq j$ (since $N_i$ is a multiple of all $n_\ell$ except $n_i$, and when $i \neq j$, this includes $n_j$).

Therefore: $x \equiv a_j N_j M_j \equiv a_j \cdot 1 \equiv a_j \pmod{n_j}$

This shows that $x$ satisfies all the congruences simultaneously.

Uniqueness: Suppose $x$ and $y$ are both solutions. Then $x \equiv y \pmod{n_i}$ for all $i$, which means $n_i \mid (x - y)$ for all $i$.

Since the $n_i$ are pairwise coprime, we have: $N = n_1 n_2 \cdots n_k \mid (x - y)$

Therefore, $x \equiv y \pmod{N}$, proving uniqueness modulo $N$.