# Euler's Theorem

:::info
**Recall (Euler $\varphi$-Function)** The Euler $\varphi$-function (or Euler's totient function) is defined for a positive integer $n$ as: $$\varphi(n) := \#\{1 \le a \le n \mid \text{gcd}(a,n)=1\}$$ This function counts the number of positive integers less than or equal to $n$ that are relatively prime to $n$.
:::

:::info
**Definition (Reduced Residue System (RRS) Modulo $n$)**
A *reduced residue system modulo $n$* is a set of $\varphi(n)$ integers such that:

* Each element is relatively prime to $n$.
* No two distinct elements are congruent modulo $n$.
:::

:::warning
**Example** For $n=8$, $\varphi(8) = 4$.
* The set $\{1, 3, 5, 7\}$ is an RRS modulo 8.
* The set $\{1, 3, -3, -1\}$ is also an RRS modulo 8, since $-3 \equiv 5 \pmod{8}$ and $-1 \equiv 7 \pmod{8}$.
:::

## Key Theorems
:::danger
**Theorem (Scaling a Reduced Residue System)**
If $\{r_1, r_2, \ldots, r_{\varphi(n)}\}$ is a reduced residue system modulo $n$, and $a$ is an integer such that $\text{gcd}(a,n)=1$, then the set $\{a r_1, a r_2, \ldots, a r_{\varphi(n)}\}$ is also a reduced residue system modulo $n$.
:::

:::warning
**Example** $\{1, 3, 5, 7\}$ is an RRS modulo 8.
* Multiplying by $a=3$ gives $\{3, 9, 15, 21\}$.
* Since $9 \equiv 1$, $15 \equiv 7$, and $21 \equiv 5$ (all modulo 8), the new set is $\{3, 1, 7, 5\}$, which is also an RRS.
:::

:::danger
**Theorem (Euler's Theorem)** If $m$ is a positive integer and $a$ is an integer such that $\text{gcd}(a,m)=1$, then:
$$
a^{\varphi(m)} \equiv 1 \pmod{m}
$$
:::

:::danger
**Corollary (Fermat's Little Theorem)** If $p$ is a prime number and $a$ is an integer such that $\text{gcd}(a,m)=1$, then:
$$
a^{p-1} \equiv 1 \pmod{p}
$$
:::

## Applications: Finding Modular Inverses
A direct consequence of Euler's Theorem is a formula for the modular inverse.

* If $\text{gcd}(a,m)=1$, then $$a^{\varphi(m)} = a \cdot a^{\varphi(m)-1} \equiv 1 \pmod{m}$$
* Therefore, $a^{\varphi(m)-1}$ is an *inverse* of $a$ modulo $m$.

:::warning
**Example (Finding an Inverse)**
Let $m = 9$ and $a = 2$. Since $\varphi(9) = 6$ and $\text{gcd}(2,9)=1$, the inverse is $2^{\varphi(9)-1}$:
$$
2^5 = 32 \equiv 5 \pmod{9}
$$

We check the inverse: $2 \cdot 5 = 10 \equiv 1 \pmod{9}$.
:::

:::warning
**Example (Solving a Linear Congruence)**
Solve $3x \equiv 7 \pmod{10}$.

* Since $\text{gcd}(3, 10)=1$ and $\varphi(10)=4$, the inverse of 3 is $3^{\varphi(10)-1} = 3^3$: $$3^3 = 27 \equiv 7 \pmod{10}$$
* We multiply both sides of the congruence by the inverse $7$: $$x \equiv 7 \cdot 3x \equiv 7 \cdot 7 = 49 \pmod{10}$$
* Since $49 \equiv 9 \pmod{10}$, the unique solution is $x \equiv 9 \pmod{10}$.
:::

:::success
**Exercises**
1. Find a reduced residue system modulo each of the following integers. a) 6 b) 9 c) 10 d) 14 e) 16 f) 17
2. Show that if $\{c_1, c_2, \ldots, c_{\varphi(m)}\}$ is a reduced residue system modulo $m$, where $m$ is a positive integer with $m \ne 2$, then $c_1 + c_2 + \cdots + c_{\varphi(m)} \equiv 0 \pmod{m}$.
3. Find the last digit of the decimal expansion of $3^{1000}$.
4. Use Euler’s theorem to find the least positive residue of $3^{100,000}$ modulo $35$.
5. Show that if $a$ is an integer relatively prime to $32,760$, then $a^{12}\equiv 1 \pmod{32,760}$.
6. Solve each of the following linear congruences using Euler’s theorem.
a) $5x \equiv 3 \pmod{14}$
b) $4x \equiv 7 \pmod{15}$
c) $3x \equiv 5 \pmod{16}$
7. Suppose that $n = p_1 p_2 \cdots p_k$, where $p_1, p_2, \ldots, p_k$ are distinct odd primes. Show that $a^{\varphi(n) + 1} \equiv a \pmod{n}$.
8. Show that the solutions to the simultaneous system of congruences $x \equiv a_j \pmod{m_j}$ (where $m_j$ are pairwise relatively prime) are given by: $$x \equiv a_1 M_1^{\varphi(m_1)} + a_2 M_2^{\varphi(m_2)} + \cdots + a_r M_r^{\varphi(m_r)} \pmod{M}$$ where $M = m_1 m_2 \cdots m_r$ and $M_j = M / m_j$ for $j = 1, 2, \ldots, r$.
9. Use Euler’s theorem to find the last digit in the decimal expansion of $7^{1000}$.
10. Find $\varphi(n)$ for the integers $n$ with $13 \le n \le 20$.
:::