Euler's Theorem and the Chinese Remainder Theorem

This notebook introduces some of the finer aspects of modular arithmetic, including Euler's phi function, Euler's theorem, the Chinese Remainder Theorem, and efficient methods for computing large powers.

The Number of Units Modulo $n$

Recall that an element $a \in \mathbb{Z}_n$ is a unit if there exists $b \in \mathbb{Z}_n$ such that $ab \equiv 1 \pmod{n}$. We've seen that $a$ is a unit modulo $n$ if and only if $\gcd(a, n) = 1$.

A natural question arises: How many units are there modulo $n$?

This question leads us to one of the most important functions in number theory.

Definition (Euler's Phi Function)

For a positive integer $n$, Euler's phi function (or totient function), denoted $\varphi(n)$ or $\phi(n)$, is defined as the number of integers in $\{1, 2, 3, \ldots, n\}$ that are relatively prime to $n$.

Examples:

$\varphi(1) = 1$ (only 1 is relatively prime to 1)
$\varphi(6) = 2$ (the numbers 1 and 5 are relatively prime to 6)
$\varphi(7) = 6$ (all of 1, 2, 3, 4, 5, 6 are relatively prime to 7 since 7 is prime)
$\varphi(12) = 4$ (the numbers 1, 5, 7, 11 are relatively prime to 12)

For prime $p$: $\varphi(p) = p - 1$ since every number from 1 to $p-1$ is relatively prime to $p$.

For prime powers: $\varphi(p^k) = p^k - p^{k-1} = p^{k-1}(p - 1)$ since the only numbers not relatively prime to $p^k$ are the multiples of $p$.

One of the most useful properties of Euler's phi function is that it is multiplicative.

Theorem (Multiplicativity of $\varphi$)

If $\gcd(m, n) = 1$, then $\varphi(mn) = \varphi(m) \cdot \varphi(n)$.

We will prove this later. For now, we can observe that it gives an efficient way to compute $\varphi(n)$ when we have a prime factorization of $n$: If $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$ is the prime factorization of $n$, then:

$$\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right) = p_1^{a_1-1}(p_1 - 1) \cdot p_2^{a_2-1}(p_2 - 1) \cdots p_k^{a_k-1}(p_k - 1)$$

Example: $\varphi(12) = \varphi(2^2 \cdot 3) = \varphi(2^2) \cdot \varphi(3) = 2^1(2-1) \cdot (3-1) = 2 \cdot 2 = 4$

Exercise: Give an example to show that $\varphi(nm) \neq \varphi(n)\varphi(m)$ if $\gcd(n,m) \neq 1$.

Euler's Theorem

Euler's phi function leads us to a powerful generalization of Fermat's Little Theorem.

Theorem (Euler's Theorem)

If $\gcd(a, n) = 1$, then $a^{\varphi(n)} \equiv 1 \pmod{n}$.

Remarks:

When $n = p$ is prime, we have $\varphi(p) = p - 1$, so Euler's theorem reduces to Fermat's Little Theorem: $a^{p-1} \equiv 1 \pmod{p}$.
This theorem tells us that raising any unit $a$ modulo $n$ to the power $\varphi(n)$ always gives 1.
This is fundamental to the RSA cryptosystem!

Example: Let $n = 12$ and $a = 5$. Since $\gcd(5, 12) = 1$ and $\varphi(12) = 4$: $$5^4 = 625 = 52 \cdot 12 + 1 \equiv 1 \pmod{12}$$

The Chinese Remainder Theorem

Often in number theory, we need to solve systems of congruence equations. (This will be the case when we want to prove the multiplicativity of Euler's phi function!) The Chinese Remainder Theorem provides a powerful method for doing so.

Example: Solving Simultaneous Congruences

Suppose we want to find all integers $x$ that satisfy: $$\begin{cases} x \equiv 2 \pmod{5} \\ x \equiv 3 \pmod{7} \end{cases}$$

Solution by hand: From the first equation, $x = 5k + 2$ for some integer $k$.

Substituting into the second equation: $$5k + 2 \equiv 3 \pmod{7}$$ $$5k \equiv 1 \pmod{7}$$

Since $5 \cdot 3 = 15 \equiv 1 \pmod{7}$, we have $k \equiv 3 \pmod{7}$, so $k = 7j + 3$.

Therefore: $$x = 5(7j + 3) + 2 = 35j + 17$$

So $x \equiv 17 \pmod{35}$.

Theorem (Chinese Remainder Theorem)

Let $n_1, n_2, \ldots, n_k$ be pairwise relatively prime positive integers (i.e., $\gcd(n_i, n_j) = 1$ for $i \neq j$). Then the system of congruences: $$\begin{cases} x \equiv a_1 \pmod{n_1} \\ x \equiv a_2 \pmod{n_2} \\ \vdots \\ x \equiv a_k \pmod{n_k} \end{cases}$$ has a unique solution modulo $N = n_1 n_2 \cdots n_k$.

Proof:

We prove the theorem for $k = 2$; the general case follows by induction.

Let $n_1$ and $n_2$ be relatively prime, and consider: $$\begin{cases} x \equiv a_1 \pmod{n_1} \\ x \equiv a_2 \pmod{n_2} \end{cases}$$ Existence: Since $\gcd(n_1, n_2) = 1$, by Bézout's identity there exist integers $m_1, m_2$ such that: $$m_1 n_1 + m_2 n_2 = 1$$

Define $x = a_1 m_2 n_2 + a_2 m_1 n_1$. Then:

$x \equiv a_1 m_2 n_2 \equiv a_1 \cdot 1 \equiv a_1 \pmod{n_1}$ (since $m_2 n_2 \equiv 1 \pmod{n_1}$)
$x \equiv a_2 m_1 n_1 \equiv a_2 \cdot 1 \equiv a_2 \pmod{n_2}$ (since $m_1 n_1 \equiv 1 \pmod{n_2}$)

Uniqueness: Suppose $x$ and $y$ are both solutions. Then:

$x \equiv y \pmod{n_1}$, so $n_1 \mid (x - y)$
$x \equiv y \pmod{n_2}$, so $n_2 \mid (x - y)$

Since $\gcd(n_1, n_2) = 1$, we have $n_1 n_2 \mid (x - y)$, thus $x \equiv y \pmod{n_1 n_2}$. □

Notice that the proof of the Chinese Remainder Theorem actually tells you an algorithm to solve simultaneous congruences: Given the congruences equations $$\begin{cases} x \equiv a \pmod{n} \\ x \equiv b \pmod{m} \\ \end{cases}$$ where $\gcd(m,n) = 1$ 1) First solve the linear diophantine equation $m\cdot z + n\cdot y = 1$ using the Euclidean algorithm. 2) Take $x = a \cdot mz + b \cdot ny$ for one solution. 3) Any other solution is $x + k\cdot \text{lcm}(m,n)$.

Proof of Theorem (Multiplicativity of $\varphi$)

Proof: We now have all of the tools needed to sketch the proof of the multiplicativity of $\varphi$. Let $m, n > 2$ be positive integers that are relatively prime. By the Chinese Remainder Theorem, there exists an integer $e \in \mathbb{Z}$ such that $e \equiv 1 \pmod{n}$ and $e \equiv 0 \pmod{m}$. Similarly, there is an integer $f$ such that $e \equiv 0 \pmod{n}$ and $e \equiv 1 \pmod{m}$. Define a function $$ \psi \colon \mathbb{Z}_n \times \mathbb{Z}_m \to \mathbb{Z}_{nm}, \qquad \qquad \psi(a,b) = a\cdot e + b\cdot f \mod mn. $$

Claims: 1) $\psi$ is a bijection. Indeed, the inverse map sends $x \in \mathbb{Z}_{nm}$ to $(a \mod n, a \mod m)$. 2) $\psi(a,b)$ is a unit modulo $nm$ if and only if both $a$ is a unit modulo $n$ and $b$ is a unit modulo $m$.

Thus $$\varphi(mn) = \#\text{Units modulo }mn = (\#\text{Units modulo }n)\cdot(\#\text{Units modulo }m) = \varphi(n)\varphi(m).$$

□

Binary Exponentiation

When computing large powers like $a^n \bmod m$, directly computing $a^n$ and then taking the remainder is inefficient for large $n$. Binary exponentiation (also called exponentiation by squaring) provides a much faster method.

The Idea

The key insight is to use the binary representation of the exponent. For example: $$a^{13} = a^{1101_2} = a^8 \cdot a^4 \cdot a^1$$

We can compute this by:

Starting with 1
For each bit in the binary representation of $n$ (from right to left):

- If the bit is 1, multiply by the current power of $a$ - Square the current power of $a$

This reduces the number of multiplications by quite a bit!

Algorithm

To compute $a^n \bmod m$:

Write $n$ in binary: $n = \sum_{i=0}^k b_i 2^i$ where $b_i \in \{0, 1\}$
Compute $a^{2^0}, a^{2^1}, a^{2^2}, \ldots, a^{2^k}$ modulo $m$ by repeated squaring
Multiply together the terms where $b_i = 1$

Example: Compute $3^{13} \bmod 7$:

$13 = 1101_2 = 8 + 4 + 1$
$3^1 \equiv 3 \pmod{7}$
$3^2 \equiv 2 \pmod{7}$
$3^4 \equiv 4 \pmod{7}$
$3^8 \equiv 2 \pmod{7}$
$3^{13} \equiv 3 \cdot 4 \cdot 2 \equiv 24 \equiv 3 \pmod{7}$

Practice Problems

Try these exercises to practice with Euler's phi function, the Chinese Remainder Theorem, and binary exponentiation!

Random Practice: Euler's Phi Function

Run the cell below to generate a random problem, then compute $\varphi(n)$ in the next cell.

Random Practice: Chinese Remainder Theorem

Run the cell below to generate a random system of congruences.

Random Practice: Euler's Theorem Application

Run the cell below to generate a problem using Euler's theorem.