Euler's and Fermat's Little Theorems

Euler's Totient Function and Reduced Residue Systems

Before we can state Euler's theorem, we must first define a crucial component: Euler's totient function, denoted $\varphi (n)$ (phi of n).

Definition: Euler's Totient Function
For a positive integer $n$, $\varphi (n)$ is defined as the number of positive integers less than or equal to $n$ that are relatively prime (coprime) to $n$.

For example:

• $\varphi (10)=4$, because there are four numbers in $\{1,2,...,10\}$ that are coprime to 10: $\{1,3,7,9\}$.
• If $p$ is a prime number, $\varphi (p)=p-1$, because all numbers from 1 to $p-1$ are coprime to $p$.

The set of integers $\{k\in \{1,\dots ,n\}\mid \gcd (k,n)=1\}$ is a foundational concept. A more formal term for a set of integers with these properties is a reduced residue system.

Definition: Reduced Residue System
A set of $\varphi (n)$ integers $\{r_1,r_2,\dots ,r_{\varphi (n)}\}$ is a reduced residue system modulo $n$ if:

1. $\gcd (r_i,n)=1$ for all $i$.
2. $r_i\not\equiv r_j(\mathrm{mod}n)$ for all $i\ne j$.

Essentially, it's a complete set of representatives for the congruence classes of numbers coprime to $n$. The simplest such system is the set of integers from 1 to $n$ that are coprime to $n$. The following video provides a clear introduction to these concepts.

Stating the Theorems

With the totient function defined, we can now state our main results.

Theorem 2.4 (Euler's Theorem):
Let $a$ and $m$ be integers such that $\gcd (a,m)=1$. Then:

A direct and historically significant special case of this theorem occurs when the modulus is a prime number.

Corollary 2.5 (Fermat's Little Theorem):
Let $p$ be a prime number and $a$ be an integer such that $p$ does not divide $a$ (which is equivalent to $\gcd (a,p)=1$). Then:

This follows directly from Euler's theorem because, as we noted, $\varphi (p)=p-1$.

The Proof of Euler's Theorem

The proof is elegant and relies on the properties of the reduced residue system we just defined. The core idea is to show that if we take a reduced residue system and multiply each of its elements by an integer a (where gcd(a, m) = 1), the resulting set is also a reduced residue system modulo m.

Let's break this down.

1. Let $R=\{r_1,r_2,\dots ,r_{\varphi (m)}\}$ be a reduced residue system modulo $m$.
2. Construct a new set $S=\{a{r}_1,a{r}_2,\dots ,a{r}_{\varphi (m)}\}$.
3. The key step is to prove that $S$, when its elements are taken modulo $m$, is just a permutation of $R$.

The video you just started provides a formal and detailed proof of this crucial lemma. The rigor of this proof should align well with your preference for formal arguments.

With this lemma established, the final step of the proof is straightforward. Since the sets $R$ and $S$ are identical modulo $m$ (they are just permutations of each other), the product of their elements must be congruent modulo $m$.

Let $P={\prod }_{i=1}^{\varphi (m)}{r}_i$.
Then, considering the product of the elements in $S$:

We can factor out the a terms:

Since every element $r_i$ in the reduced residue system is coprime to $m$, their product $P$ is also coprime to $m$. As we learned in the previous lesson, this means $P$ has a multiplicative inverse modulo $m$. We can therefore multiply both sides of the congruence by $P^{-1}$, effectively canceling $P$.

This leaves us with:

This completes the proof of Euler's theorem. The final part of the video walks through this last step.

An Alternative Proof of Fermat's Little Theorem

While Fermat's Little Theorem falls out nicely as a corollary, there is a beautiful combinatorial proof that offers a different kind of insight. It's often called the "bracelet proof" or "necklace proof".

Imagine we want to make bracelets of length $p$ (where $p$ is a prime number) using beads of $a$ different colors.

1. First, consider creating fixed, oriented strings of length $p$. There are $a$ choices for each of the $p$ positions, so there are $a^p$ possible strings.

2. Out of these $a^p$ strings, exactly $a$ of them consist of beads of all the same color (e.g., "AAAA...", "BBBB...", etc.). These strings, when made into a bracelet, only have one arrangement under rotation.

3. This leaves $a^p-a$ strings that use at least two colors. What happens when we turn these strings into bracelets? Since $p$ is prime, a string with multiple colors cannot have a rotational symmetry period shorter than $p$. For example, if $p=7$, a string like "AABAAAB" cannot be identical to a rotation by 1, 2, 3, 4, 5, or 6 positions. If it were, its length would have to be a divisor of 7, which is impossible.

4. Therefore, each of these non-monochromatic strings belongs to a group of exactly $p$ distinct strings that can be rotated into one another (e.g., "AABBC", "ABBC A", "BBC AA", "BC AAB", "C AABB"). These $p$ strings all form the same bracelet.

5. This means the $a^p-a$ non-monochromatic strings can be perfectly partitioned into groups of size $p$. Consequently, $p$ must divide $a^p-a$.

   $$a^p-a\equiv 0(\mathrm{mod}p)$$

   or

   $$a^p\equiv a(\mathrm{mod}p)$$

6. If we assume $a$ is not a multiple of $p$ (so $\gcd (a,p)=1$), we can cancel $a$ from both sides, yielding Fermat's Little Theorem:

   $$a^{p-1}\equiv 1(\mathrm{mod}p)$$

Application: Simplifying Modular Exponentiation

Euler's theorem is an indispensable tool for reducing large powers in modular arithmetic. Let's see it in action.

As you can see from the reading, the task of computing $77^{123}(\mathrm{mod}10)$ becomes trivial.

1. We are working modulo 10, and $\gcd (77,10)=\gcd (7,10)=1$.
2. We calculate $\varphi (10)=4$.
3. By Euler's theorem, we know $77^4\equiv 1(\mathrm{mod}10)$.
4. We express the exponent 123 in terms of 4: $123=4\cdot 30+3$.
5. Therefore, $77^{123}=77^{4\cdot 30+3}=(77^4{)}^{30}\cdot 77^3\equiv 1^{30}\cdot 77^3\equiv 7^3(\mathrm{mod}10)$.
6. The final step is easy to compute: $7^3=343\equiv 3(\mathrm{mod}10)$.

This technique of reducing the exponent modulo $\varphi (m)$ is a cornerstone of the RSA algorithm, which we will study in depth later in the course.

Conclusion

In this lesson, we have formally stated and proven two fundamental theorems of number theory. We saw how the concept of a reduced residue system provides the structure needed for a rigorous proof of Euler's theorem, and how Fermat's Little Theorem emerges as a simple yet powerful special case. We also explored an alternative, elegant combinatorial proof for Fermat's theorem that provides a different kind of intuition.

Key Takeaways:

• Euler's totient function, $\varphi (n)$, counts the number of positive integers up to $n$ that are coprime to $n$.
• Euler's Theorem: If $\gcd (a,m)=1$, then $a^{\varphi (m)}\equiv 1(\mathrm{mod}m)$.
• Fermat's Little Theorem: If $p$ is prime and $p\nmid a$, then $a^{p-1}\equiv 1(\mathrm{mod}p)$.
• The proof of Euler's theorem hinges on the fact that multiplying a reduced residue system by a coprime integer a simply permutes the system modulo m.
• These theorems are essential for efficiently computing modular exponentiation.

A key piece of information we've used today is the value of $\varphi (n)$. While we know $\varphi (p)=p-1$ for a prime $p$, how do we compute it for a composite number like $n=100$? In our next lesson, we will derive a general formula for calculating $\varphi (n)$ for any integer $n$, provided we know its prime factorization. This will be another critical step toward understanding the security of modern cryptosystems.