Statement Proof and Solved Examples of Wilsons Theorem
Wilson's Theorem is a classical theorem in Number Theory. It has also an interesting fact associated with it that the theorem is stated by a teacher and student pair, i.e., Ibn al-Hayatam and John Wilson, respectively. However, it was proved later on by Lagrange. Wilson’s Theorem is of great importance in Number Theory. The applications of Wilson’s Theorem, its limitations, and Wilson’s Theorem examples will be discussed here in detail for a clear understanding of the theorem. So, let us discuss the theorem.
History of John Wilson
John Wilson
Name: John Wilson
Born: 6 August 1741
Died: 18 October 1793
Field: Mathematics
Nationality: British
Wilson's Theorem Statement
Wilson Theorem states that if $p$ is any natural number greater than 1, then $p$ is said to be a prime number if and only if the product of all the positive integers less than $p$ is one less than a multiple of number $p$.
Mathematically, according to Wilson's Theorem, let $p>1$. The number $p$ is prime if and only if
$(p-1) !=-1(\bmod p)$
or,
$(p-1) !=(p-1)(\bmod p)$
Wilson's Theorem Proof
A natural number p > 1 is a prime number if and only if the product of all the positive integers less than p is one less than a multiple of p.
Suppose $p$ is prime. If $k \in\{1, \ldots, p-1\}$, then $k$ is relatively prime to $p$. So, there are integers $a$ and $b$ in the way that
$\Rightarrow a k+b p=1, \text { or } a k=1(\bmod p) \text {. }$
Reducing $a \bmod p$,
We may assume $a \in\{1, \ldots, p-1\}$. Thus, every element of $\{1, \ldots, p-1\}$ has a reciprocal $\bmod p$ in this set. We know that only 1 and $p-1$ are their reciprocals. Thus, the elements $2, \ldots, p-2$ must pair up into pairs $\left\{x, x^{-1}\right\}$. It is obvious that their product is 1.
Hence,
\[\Rightarrow 1 \cdot(p-1)=p-1 \]
\[ \Rightarrow-1(\bmod p)\]
$\Rightarrow(p-1) !=1 \cdot 2 \cdots(p-2) \cdot(p-1)$
Now suppose $(p-1) !=-1(\bmod p)$
We want to show that $p$ is prime.
Begin by rewriting the equation as $(p-1) !+1=k p$.
Suppose $p=a b$. We may take $1 \leq a, b \leq p$. If $a=p$, then the factorization is trivial, so suppose $a<p$. Then, $a \mid(p-1)$ ! (since it's one of $\{1, \ldots, p-1\})$ and $a \mid p$,
So,
\[\Rightarrow(p-1) !+1=k p\] shows \[a \mid 1.\]
Therefore, $a=1$.
Limitations of Wilson's Theorem
Wilson's theorem is not applicable in the case of composite number 4 because by applying Wilson's Theorem in the case of 4, we get the remainder 2 instead of 1.
Applications of Wilson's Theorem
Wilson’s Theorem has a wide range of applications in the changing world. As the world is shifting to digitization, security is the key concern.
Wilson’s Theorem is used in cryptography for coding-decoding.
Wilson's Theorem is applicable in the case of both prime and composite numbers. Hence, widens the base of its applications.
Wilson’s Theorem Examples
1. What will be the remainder when 568! is divided by 569?
Ans: According to Wilson's theorem, we have,
For prime number ' $p$ ', we have
$\Rightarrow(p-1) ! \bmod p=(p-1)$
In this case, 569 is a prime number.
Thus,
$\Rightarrow 568 ! \bmod 569=568 \text {. }$
Hence, when 568 ! is divided by 569,
$\Rightarrow$ we get 568 as the remainder.
2. What will be the remainder when 225! is divided by 227?
Ans: We know that for prime number ' $p$ ', we have
$\Rightarrow(p-2) ! \bmod p=1 \text {. }$
In this case, 227 is a prime number.
Thus, $225 ! \bmod 227$ will be equal to 1.
In other words,
when 225! Is divided by 227,
$\Rightarrow$ we get the remainder as 1.
Important Formulas to Remember
For $p>1$ and $p$ is prime number: $(p-1) !=-1(\bmod p)$
Important Points to Remember
Wilson’s Theorem is applicable only in the case of a prime number.
A number is said to be prime if it is divisible by 1 and itself only.
Conclusion
In the article, we have discussed the proof of Classical Wilson's Theorem in detail and its applications in the real world. Wilson’s Theorem forms a fundamental tool of Number Theory. It reduces our calculation work, which would even have taken hours without this theorem. Finally, we can say that Wilson's Theorem is a gem of Mathematics.
FAQs on Wilsons Theorem in Number Theory
1. What is Wilson's Theorem?
Wilson's Theorem states that a positive integer p > 1 is prime if and only if (p − 1)! ≡ −1 (mod p). In other words, a number p is prime exactly when the factorial of (p − 1) leaves a remainder of −1 when divided by p.
- Here, (p − 1)! means 1 × 2 × 3 × ... × (p − 1).
- The notation ≡ −1 (mod p) means the remainder is p − 1.
- This theorem is a fundamental result in number theory and modular arithmetic.
2. What is the formula for Wilson's Theorem?
The formula for Wilson's Theorem is (p − 1)! ≡ −1 (mod p) if and only if p is prime.
- It applies only when p is a prime number greater than 1.
- If p is composite, then (p − 1)! is not congruent to −1 modulo p.
- This formula is often used in proofs and theoretical number theory.
3. How do you prove Wilson's Theorem?
Wilson's Theorem is proved by showing that every number from 1 to p − 1 has a multiplicative inverse modulo p, and they pair up except for 1 and p − 1.
- If p is prime, every integer 1 ≤ a ≤ p − 1 has a unique inverse mod p.
- Each pair a and a⁻¹ multiplies to 1 modulo p.
- The only self-inverses are 1 and p − 1.
- Thus, (p − 1)! ≡ 1 × (p − 1) ≡ −1 (mod p).
4. Can you give an example of Wilson's Theorem?
Yes, for p = 5, Wilson's Theorem gives (5 − 1)! ≡ −1 (mod 5).
- Compute 4! = 24.
- Divide 24 by 5: remainder is 4.
- Since −1 mod 5 equals 4, we get 4! ≡ −1 (mod 5).
5. Why does Wilson's Theorem only work for prime numbers?
Wilson's Theorem works only for prime numbers because only primes guarantee that every nonzero element modulo p has a multiplicative inverse.
- If p is prime, the integers 1 to p − 1 form a multiplicative group mod p.
- If p is composite, some numbers share factors with p and do not have inverses.
- As a result, (p − 1)! will not be congruent to −1 (mod p) for composite p.
6. How do you use Wilson's Theorem to test if a number is prime?
To test if p is prime using Wilson's Theorem, compute (p − 1)! and check whether (p − 1)! ≡ −1 (mod p).
- Step 1: Calculate (p − 1)!.
- Step 2: Find the remainder when divided by p.
- Step 3: If the remainder is p − 1, then p is prime.
7. What is the converse of Wilson's Theorem?
The converse of Wilson's Theorem states that if (p − 1)! ≡ −1 (mod p), then p must be prime.
- This makes the statement an if and only if condition.
- Both directions are true: prime implies the congruence, and the congruence implies prime.
- Therefore, Wilson's Theorem completely characterizes prime numbers.
8. What is the relationship between Wilson's Theorem and factorials?
Wilson's Theorem directly involves the factorial (p − 1)! in modular arithmetic to characterize prime numbers.
- A factorial n! means the product of integers from 1 to n.
- The theorem examines (p − 1)! modulo p.
- The special result (p − 1)! ≡ −1 (mod p) occurs only when p is prime.
9. Is Wilson's Theorem practical for finding large prime numbers?
Wilson's Theorem is not practical for finding large prime numbers because computing (p − 1)! is computationally expensive.
- Factorials grow extremely fast as p increases.
- Modern primality tests like Fermat's test or Miller–Rabin are more efficient.
- Wilson's Theorem is mainly used in theoretical number theory.
10. What are common mistakes when applying Wilson's Theorem?
A common mistake when applying Wilson's Theorem is forgetting that the congruence must equal −1 modulo p.
- Students sometimes check if (p − 1)! ≡ 1 instead of −1 (mod p).
- Another error is applying the theorem to p ≤ 1, which is invalid.
- Incorrect factorial calculations can also lead to wrong conclusions.
