6.4: Wilson, Fermat, Euler's theorem

 Wilson's Theorem

Theorem \(\PageIndex{1}\)

Let \(p\) be a prime number. Then \((p - 1)! + 1\) is divisible by \(p\).

Proof:

Consider the product \(P = 1 \cdot 2 \cdot 3 \cdots (p-1)\). Now, let's pair each number \(k\) from \(1\) to \(p-1\) with its modular inverse \(k^{-1}\) modulo \(p\). 

We know that for every \(k\) such that \(1 \leq k \leq p-1\), there exists a unique \(k^{-1}\) such that \(kk^{-1} \equiv 1 \pmod{p}\). Moreover, these pairs will be distinct because if \(kk^{-1} \equiv 1 \pmod{p}\) and \(jj^{-1} \equiv 1 \pmod{p}\) for \(k \neq j\), then \(k = kj^{-1}\) and \(j = jk^{-1}\), implying \(k = j\), which contradicts the distinctness of the pairs. 

Thus, we can pair each \(k\) with \(k^{-1}\) such that the product of these pairs is congruent to \(1 \pmod{p}\). Therefore, \(P \equiv (p-1)! \equiv -1 \pmod{p}\). Adding \(1\) to both sides gives \((p-1)! + 1 \equiv 0 \pmod{p}\), which means \((p-1)! + 1\) is divisible by \(p\).

 

 

Fermat's Little Theorem

Theorem \(\PageIndex{2}\)

 For any prime number \( p \) and any positive integer \( a \) such that \( p \) does not divide \( a \), we have \( a^{p-1} \equiv 1 \pmod{p} \).

 

Definition:  

For \(n \in \mathbb{N}\), the Euler's totient function \(\phi(n)\) is defined to be the number of positive integers less than \(n\) that are relatively prime to \(n\).

 

Euler's totient function has numerous applications in number theory, cryptography, and other branches of mathematics. It plays a vital role in RSA encryption, where it is used to compute the encryption and decryption keys.

Example \(\PageIndex{1}\)

Determine the value \(\phi(n)\) for each integer \(n \le  30\).  

Number of \(n \in \mathbb{N}\), Relatively Prime to \(n\)
\(n\)	\(\phi (n)\)	Set  of \(n \in \mathbb{N}\) that are relatively Prime to \(n\).
1	0	{}
2	1	{1}
3	2	{1,2}
4	2	{1,3}
5	4	{1,2,3,4}
6	2	{1,5}
7	6	{1,2,3,4,5,6}
8	4	{1,3,5,7}
9	6	{1,2,4,5,7,8}
10	4	{1,3,7,9}
11	10	{1,2,3, … ,8,9,10}
12	4	{1,5,7,11}
13	12	{1,2,3, … ,10,11,12}
14	6	{1,3,5,9,11,13}
15	8	{1,2,4,7,8,11,13,14}
16	8	{1,3,5,7,9,11,13,15}
17	16	{1,2,3, … ,14,15,16}
18	6	{1,5,7,11,13,17}
19	18	{1,2,3, … ,16,17,18}
20	8	{1,3,7,9,11,13,17,19}
21	12	{1,2,4,5,8,10,11,13,16,17,19,20}
22	10	{1,3,5,7,9,13,15,17,19,21}
23	22	{1,2,3, … ,20,21,22}
24	8	{1,5,7,11,13,17,19,23}
25	20	{1,2,3,4,6,7,8,9,11,12,13,14,16,17,18,19,21,22,23,24}
26	12	{1,3,5,7,9,11,15,17,19,21,23,25}
27	18	{1,2,4,5,7,8,10,11,13,14,16,17,19,20,22,23,25,26}
28	12	{1,3,5,9,11,13,15,17,19,23,25,27}
29	28	{1,2,3, … ,26,27,28}
30	8	{1,7,11,13,17,19,23,29}

Euler's Theorem

Theorem \(\PageIndex{3}\)

If \(a\) and \(n\) are relatively prime (i.e., \(\gcd(a, n) = 1\)), then \[ a^{\phi(n)} \equiv 1 \pmod{n} \]

The following results will help us finding \(\phi(n)\) for \(n\in \mathbb{N}\).

Theorem \(\PageIndex{4}\)

 

1.  If \(p\) is prime then \(\phi(p)=p-1.\)

2. If \(p\) is prime and \(k\) is a positive integer then \(\phi(p^k)=p^k-p^{k-1}.\)

3. If \(m\) and \(n\) are relatively prime, then \(\phi(mn)=\phi(m)\phi(n).\)

4. \[ \phi(n) = n \times \prod_{p|n} \left(1 - \frac{1}{p}\right) \] where the product is taken over distinct prime factors \(p\) of \(n.\)