Fermat, Wilson and Lagrange Theorems

Fermat's Little Theorem

Fermat's Little Theorem is a fundamental result in number theory that deals with modular arithmetic. It provides a way to simplify calculations involving exponents in congruences.

The theorem states that if $p$ is a prime number, then for any integer $a$ not divisible by $p$, we have: $a^{p-1} \equiv 1 \pmod{p}$

An alternative form of the theorem, which holds for any integer $a$ and any prime $p$, is: $a^p \equiv a \pmod{p}$

Let's understand why this is true. Consider the set of integers $\{1, 2, 3, \dots, p-1\}$. When we multiply each of these integers by $a$ and take the result modulo $p$, we get a new set of integers. Since $a$ is not divisible by $p$ and $p$ is prime, none of $a \cdot 1, a \cdot 2, \dots, a \cdot (p-1)$ are divisible by $p$. Also, all these products are distinct modulo $p$.

To see this, suppose $a \cdot i \equiv a \cdot j \pmod{p}$ for $1 \le i, j \le p-1$. Since $p$ is prime and $a$ is not divisible by $p$, we can multiply both sides by the modular inverse of $a$ (which exists because $a$ and $p$ are coprime). This gives $i \equiv j \pmod{p}$. Since $i$ and $j$ are both between 1 and $p-1$, this implies $i=j$.

Therefore, the set $\{a \cdot 1 \pmod{p}, a \cdot 2 \pmod{p}, \dots, a \cdot (p-1) \pmod{p}\}$ is just a permutation of the set $\{1, 2, \dots, p-1\}$.

Now, let's multiply all the elements in both sets: $(a \cdot 1) \cdot (a \cdot 2) \cdot \dots \cdot (a \cdot (p-1)) \equiv 1 \cdot 2 \cdot \dots \cdot (p-1) \pmod{p}$ $a^{p-1} \cdot (1 \cdot 2 \cdot \dots \cdot (p-1)) \equiv (p-1)! \pmod{p}$ $a^{p-1} \cdot (p-1)! \equiv (p-1)! \pmod{p}$

Since $p$ is prime, $(p-1)!$ is not divisible by $p$. Thus, we can divide both sides by $(p-1)!$ (or multiply by its modular inverse). This gives: $a^{p-1} \equiv 1 \pmod{p}$

To get the second form, $a^p \equiv a \pmod{p}$, we can multiply the first form by $a$: $a \cdot a^{p-1} \equiv a \cdot 1 \pmod{p}$ $a^p \equiv a \pmod{p}$ This second form is also true even if $a$ is divisible by $p$. If $a \equiv 0 \pmod{p}$, then $a^p \equiv 0^p \equiv 0 \pmod{p}$ and $a \equiv 0 \pmod{p}$, so $0 \equiv 0 \pmod{p}$.

Applications of Fermat's Little Theorem

Fermat's Little Theorem has numerous applications, particularly in cryptography and primality testing.

• Modular Exponentiation: It simplifies calculating large powers of numbers modulo $p$. For example, to calculate $3^{100} \pmod{7}$: Since 7 is prime, by Fermat's Little Theorem, $3^{7-1} \equiv 3^6 \equiv 1 \pmod{7}$. We can write $100 = 6 \times 16 + 4$. So, $3^{100} = 3^{6 \times 16 + 4} = (3^6)^{16} \cdot 3^4 \equiv 1^{16} \cdot 3^4 \equiv 3^4 \pmod{7}$. $3^4 = 81$, and $81 \equiv 4 \pmod{7}$. Thus, $3^{100} \equiv 4 \pmod{7}$.
• Primality Testing: While not a definitive test, if $a^{n-1} \not\equiv 1 \pmod{n}$ for some $a$ coprime to $n$, then $n$ is composite. However, there are composite numbers (Carmichael numbers) for which $a^{n-1} \equiv 1 \pmod{n}$ for all $a$ coprime to $n$.

Wilson's Theorem

Wilson's Theorem is another elegant result in number theory that provides a condition for a number to be prime. It relates the factorial of a number to its primality.

The theorem states that a natural number $n > 1$ is a prime number if and only if: $(n-1)! \equiv -1 \pmod{n}$

This means that if you take a prime number $p$, multiply all the integers from 1 up to $p-1$, the result will have a remainder of $p-1$ (or $-1$) when divided by $p$. Conversely, if for a number $n$, $(n-1)!$ has a remainder of $n-1$ when divided by $n$, then $n$ must be prime.

Let's look at the proof.

Proof of Wilson's Theorem

Part 1: If $n$ is prime, then $(n-1)! \equiv -1 \pmod{n}$. This is essentially the proof we saw for Fermat's Little Theorem. Consider the set $\{1, 2, \dots, n-1\}$. For each integer $a$ in this set, its modular multiplicative inverse modulo $n$ exists because $n$ is prime and $a < n$. The inverse of $a$, denoted $a^{-1}$, is the unique integer $x$ such that $a \cdot x \equiv 1 \pmod{n}$. In the set $\{1, 2, \dots, n-1\}$, each element is its own inverse if and only if $a^2 \equiv 1 \pmod{n}$. This congruence has solutions $a \equiv 1 \pmod{n}$ and $a \equiv n-1 \pmod{n}$ (which is $a \equiv -1 \pmod{n}$). For all other elements $a$ in the set $\{2, 3, \dots, n-2\}$, their inverses exist and are distinct from $a$ and from each other. So, when we compute $(n-1)! = 1 \cdot 2 \cdot 3 \cdot \dots \cdot (n-2) \cdot (n-1) \pmod{n}$, we can pair up each element $a$ with its inverse $a^{-1}$. The product of each such pair is $a \cdot a^{-1} \equiv 1 \pmod{n}$. Thus, the product of all elements from 2 to $n-2$ modulo $n$ is 1. $(n-1)! \equiv 1 \cdot (2 \cdot \dots \cdot (n-2)) \cdot (n-1) \pmod{n}$ $(n-1)! \equiv 1 \cdot (1) \cdot (n-1) \pmod{n}$ $(n-1)! \equiv n-1 \pmod{n}$ $(n-1)! \equiv -1 \pmod{n}$ This holds for primes $n > 2$. For $n=2$, $(2-1)! = 1! = 1$, and $-1 \equiv 1 \pmod{2}$. So it holds for $n=2$ as well.

Part 2: If $(n-1)! \equiv -1 \pmod{n}$, then $n$ is prime. Assume $(n-1)! \equiv -1 \pmod{n}$. We need to show $n$ is prime. Suppose $n$ is composite. Let $d$ be a divisor of $n$ such that $1 < d < n$. Since $d$ is a divisor of $n$, $d \le n$. Also, since $n$ is composite, there must be such a $d$. If $d < n$, then $d$ is one of the numbers in the product $(n-1)! = 1 \cdot 2 \cdot \dots \cdot d \cdot \dots \cdot (n-1)$. Therefore, $d$ must divide $(n-1)!$. If $n$ is composite and $n > 4$, then $n$ has a divisor $d$ such that $1 < d < n$. If $d$ is a divisor of $n$, then $n/d$ is also a divisor. Case 1: $d \ne n/d$. Then both $d$ and $n/d$ are distinct factors in $(n-1)!$, and their product $d \cdot (n/d) = n$. So, $n$ divides $(n-1)!$. This implies $(n-1)! \equiv 0 \pmod{n}$. But we are given $(n-1)! \equiv -1 \pmod{n}$. So $0 \equiv -1 \pmod{n}$, which means $n$ divides 1. This is impossible for $n > 1$. Case 2: $d = n/d$. This means $d^2 = n$. So $n$ is a perfect square, and $d = \sqrt{n}$. If $n > 4$ is a perfect square, then $\sqrt{n} < n$. If $n=p^2$, then $p < p^2$ for $p>1$. The factors in $(n-1)!$ include $p$ and $2p$ (if $2p < n$). If $n=p^2$ and $p>2$, then $p$ and $2p$ are distinct factors in $(n-1)!$, and their product is $2p^2$. So $p^2$ divides $(n-1)!$. If $n=4$, $(4-1)! = 3! = 6$. $6 \equiv 2 \pmod{4}$. This is not $-1 \pmod{4}$. The only composite number $n$ for which $(n-1)! \not\equiv 0 \pmod{n}$ is $n=4$. For $n=4$, $(4-1)! = 3! = 6$. $6 \equiv 2 \pmod{4}$. Since $2 \not\equiv -1 \pmod{4}$, Wilson's Theorem holds for $n=4$ as well (it correctly identifies 4 as composite). For any composite $n > 4$, $n$ has a divisor $d$ with $1 < d < n$. If $d \ne n/d$, then $d$ and $n/d$ are distinct factors in $(n-1)!$. Their product is $n$, so $n$ divides $(n-1)!$, leading to $(n-1)! \equiv 0 \pmod{n}$. If $n=p^2$ for a prime $p > 2$, then $p$ and $2p$ are factors in $(n-1)!$ since $2p < p^2$ for $p>2$. Their product is $2p^2$, so $p^2$ divides $(n-1)!$. In all cases where $n$ is composite and $n>4$, $(n-1)! \equiv 0 \pmod{n}$. Since we are given $(n-1)! \equiv -1 \pmod{n}$, and $-1 \not\equiv 0 \pmod{n}$ for $n>1$, $n$ cannot be composite. Therefore, $n$ must be prime.

Applications of Wilson's Theorem

Wilson's Theorem is primarily of theoretical importance. It offers a direct test for primality, but it is computationally impractical for large numbers because calculating factorials is very intensive.

• Primality Test: For a number $n$, calculate $(n-1)! \pmod{n}$. If the result is $n-1$, then $n$ is prime. Otherwise, it is composite.

Lagrange's Theorem (in Group Theory)

Lagrange's Theorem is a cornerstone of group theory. It establishes a fundamental relationship between the order of a finite group and the order of its subgroups.

First, let's define some terms:

• Group: A set $G$ with a binary operation (often denoted by multiplication) that satisfies four properties: closure, associativity, existence of an identity element, and existence of an inverse for each element.
• Finite Group: A group with a finite number of elements.
• Order of a Group ($|G|$): The number of elements in a finite group $G$.
• Subgroup: A subset of a group $G$ that is itself a group under the same operation.
• Order of a Subgroup ($|H|$): The number of elements in a finite subgroup $H$.
• Coset: For a subgroup $H$ of a group $G$, and an element $g \in G$, the left coset of $H$ with respect to $g$ is the set $gH = \{gh \mid h \in H\}$. The right coset is $Hg = \{hg \mid h \in H\}$.

Lagrange's Theorem states: If $G$ is a finite group and $H$ is a subgroup of $G$, then the order of $H$ divides the order of $G$. That is, $|H|$ divides $|G|$.

This theorem also implies that the number of distinct left cosets (or right cosets) of $H$ in $G$, denoted by $|G:H|$, is equal to $|G|/|H|$. This number $|G:H|$ is called the index of $H$ in $G$.

Proof of Lagrange's Theorem

Let $G$ be a finite group and $H$ be a subgroup of $G$.

The key idea is to partition the group $G$ into disjoint cosets of $H$.

Consider the left cosets of $H$ in $G$: $g_1H, g_2H, \dots, g_kH$.

1. Every element of $G$ belongs to some coset. This is true because for any $g \in G$, $g$ is in the coset $gH$ (since $g = g \cdot e$, where $e$ is the identity in $H$). 2. Any two left cosets are either identical or disjoint. Suppose two cosets $aH$ and $bH$ have an element in common. Let $x \in aH \cap bH$. Then $x = ah_1$ for some $h_1 \in H$, and $x = bh_2$ for some $h_2 \in H$. So, $ah_1 = bh_2$. This implies $a = bh_2h_1^{-1}$. Since $h_1^{-1} \in H$ and $h_2 \in H$, their product $h_2h_1^{-1}$ is also in $H$. Let $h_3 = h_2h_1^{-1} \in H$. Then $a = bh_3$. Now consider any element $y \in aH$. Then $y = ah_4$ for some $h_4 \in H$. Substituting $a = bh_3$, we get $y = (bh_3)h_4 = b(h_3h_4)$. Since $h_3, h_4 \in H$, $h_3h_4 \in H$. Thus, $y \in bH$. This shows $aH \subseteq bH$. Similarly, we can show $bH \subseteq aH$. Therefore, $aH = bH$. This means if two cosets intersect, they must be the same coset. 3. Each coset has the same number of elements as $H$. For any $g \in G$, the map $\phi: H \to gH$ defined by $\phi(h) = gh$ is a bijection. It is surjective by definition of $gH$. It is injective because if $\phi(h_1) = \phi(h_2)$, then $gh_1 = gh_2$, which implies $h_1 = h_2$ by multiplying by $g^{-1}$ on the left. Thus, $|gH| = |H|$.

Since $G$ is partitioned into disjoint cosets, and each coset has $|H|$ elements, if $k$ is the number of distinct cosets, then the total number of elements in $G$ is the sum of the sizes of these disjoint cosets: $|G| = |H| + |H| + \dots + |H|$ ($k$ times) $|G| = k \cdot |H|$

This equation shows that $|H|$ divides $|G|$, and $k = |G|/|H|$ is the number of distinct cosets (the index of $H$ in $G$).

Corollaries and Implications of Lagrange's Theorem

Lagrange's Theorem has several important consequences for finite groups:

• Order of an element: The order of an element $g$ in a group $G$ is the smallest positive integer $m$ such that $g^m = e$ (the identity element). Let $H = \langle g \rangle$ be the cyclic subgroup generated by $g$. The order of $H$ is the same as the order of the element $g$. By Lagrange's Theorem, $|H|$ must divide $|G|$. Therefore, the order of any element $g$ in a finite group $G$ must divide the order of the group $G$.
• Fermat's Little Theorem as a consequence: Let $G$ be the multiplicative group of integers modulo $p$, denoted by $(\mathbb{Z}/p\mathbb{Z})^\times$. This group consists of the integers $\{1, 2, \dots, p-1\}$ under multiplication modulo $p$. The order of this group is $p-1$. If $a$ is an integer not divisible by $p$, then $a \pmod{p}$ is an element of this group. By Lagrange's Theorem, the order of $a$ must divide the order of the group, $p-1$. So, if $k$ is the order of $a$, then $k | (p-1)$. This means $p-1 = mk$ for some integer $m$. Then $a^{p-1} = a^{mk} = (a^k)^m$. Since $a^k \equiv 1 \pmod{p}$ (by definition of order), we have $a^{p-1} \equiv 1^m \equiv 1 \pmod{p}$. This proves Fermat's Little Theorem.
• Euler's Totient Theorem: A generalization of Fermat's Little Theorem. If $n$ is a positive integer and $a$ is an integer coprime to $n$, then $a^{\phi(n)} \equiv 1 \pmod{n}$, where $\phi(n)$ is Euler's totient function (the number of positive integers less than or equal to $n$ that are coprime to $n$). The group $(\mathbb{Z}/n\mathbb{Z})^\times$ has order $\phi(n)$. For any $a$ coprime to $n$, $a$ is an element of this group. By Lagrange's theorem, the order of $a$ divides $\phi(n)$. Thus $a^{\phi(n)} \equiv 1 \pmod{n}$.
• Lagrange's theorem implies that a group of prime order $p$ is cyclic. If $G$ has order $p$ (prime), and we take any element $g \ne e$, its order must divide $p$. Since $p$ is prime, the only divisors are 1 and $p$. The order of $g$ cannot be 1 (as $g \ne e$). So, the order of $g$ must be $p$. This means $g$ generates the entire group $G$, so $G$ is cyclic.

Summary Table of Theorems

Interconnections and Significance

These theorems, while from different branches of number theory and abstract algebra, highlight deep structural properties. Fermat's Little Theorem is a direct application of group theory principles (via Euler's Totient Theorem and Lagrange's Theorem), showing how abstract algebraic structures underpin number theoretic results. Wilson's Theorem provides a specific criterion for primality that is rooted in the properties of factorials and modular arithmetic. Lagrange's Theorem, as a fundamental result in group theory, provides a framework for understanding the structure of finite groups and has far-reaching implications, including the proof of Fermat's Little Theorem. Together, they form essential tools for anyone studying number theory and abstract algebra.