Salman Ghori Developer Portfolio

(p-1)! ≡ -1 (mod p) iff p is prime. Wilson's Theorem provides a way to characterize prime numbers using factorials and modular arithmetic, stating that for a prime p, the factorial of (p-1) is congruent to -1 modulo p, and vice versa.

Explanation in Simple Terms

Wilson's Theorem is a rule in number theory that helps identify if a number is prime. It says that if you take the factorial of one less than the number (like for 5, 4! = 24), and divide it by the number, the remainder should be one less than the number (for 5, 24 mod 5 = 4, which is -1 mod 5 since 4 ≡ -1 mod 5). This only holds if the number is prime.
In simpler words: For a prime p, (p-1)! leaves a remainder of p-1 when divided by p (which is the same as -1 in mod p). If it's not prime, this doesn't hold.
Real-life example: Think of it like a lock and key in cryptography. Primes are special 'keys' for secure systems (like RSA encryption). Wilson's Theorem is a mathematical test to verify if a number is truly a prime 'key', though it's not used in practice for big numbers because calculating huge factorials is slow.

Formal Statement and Proof Sketch

Statement: A positive integer p > 1 is prime if and only if (p-1)! ≡ -1 (mod p).
Proof Idea (for primes): In the field modulo p, the numbers 1 to p-1 form a group under multiplication. Each number has an inverse, and most pair with their inverses, except 1 and p-1 (which is -1 mod p), whose inverses are themselves. The product of all is thus -1 mod p.
For composites: If p is composite, it has factors a and b where 1 < a,b < p, so (p-1)! includes both, making it ≡ 0 mod p, not -1 (except for p=4, but 4 is composite and theorem holds inversely).

C++ Basics for Wilson's Theorem

In C++, to check Wilson's Theorem, compute (p-1)! mod p. Use long long for large numbers, but note factorials grow fast, so it's impractical for p > 20 or so without big integer libraries (but we can use modular multiplication to avoid overflow).
Key concepts: Use a loop to compute factorial modulo p incrementally (multiply and take mod at each step). Check if result == p-1 (since -1 mod p = p-1).

Simple C++ skeleton:

#include <bits/stdc++.h>
using namespace std;

bool isPrimeWilson(long long p) {
    if (p <= 1) return false;
    long long fact = 1;
    for (long long i = 2; i < p; ++i) {
        fact = (fact * i) % p;
        if (fact == 0) return false;  // Early exit for composites
    }
    return fact == p - 1;
}

Example Problem: Check if a Number is Prime Using Wilson's Theorem

Problem: Given a number p (e.g., 7), verify if it's prime by computing (p-1)! mod p and checking if it's -1 mod p.
This is understandable for beginners: It directly applies the theorem and shows modular arithmetic in code.

C++ Code Example:

#include <bits/stdc++.h>
using namespace std;

bool isPrimeWilson(long long p) {
    if (p <= 1) return false;
    if (p == 2 || p == 3) return true;
    long long fact = 1;
    for (long long i = 2; i < p; ++i) {
        fact = (fact * i) % p;
    }
    return fact == p - 1;
}

int main() {
    vector<long long> tests = {4, 5, 6, 7, 11, 13};
    for (auto p : tests) {
        cout << p << " is " << (isPrimeWilson(p) ? "prime" : "not prime") << endl;
    }
    return 0;
}

Output:
4 is not prime
5 is prime
6 is not prime
7 is prime
11 is prime
13 is prime

Usage

Theoretical primality characterization
Basis for some probabilistic primality tests
Educational tool to understand modular inverses and groups

Note

Not efficient for large p due to factorial computation time (O(p) time, impractical for big primes)

Practice Problems

1. Verify Wilson's Theorem for p=11. Hint: Compute 10! mod 11 step-by-step and check if ==10.
2. Implement a function to find all primes up to n using Wilson's Theorem (inefficient but for small n<20). Hint: Loop from 2 to n, apply the check.
3. Modify the code to early-exit for composites if fact becomes 0 mod p. Hint: If i divides p for some i < p, fact will be 0.

Quiz to Test Understanding

Question 1: What does Wilson's Theorem state for a prime p? (A) p! ≡ 0 mod p (B) (p-1)! ≡ -1 mod p (C) (p+1)! ≡ 1 mod p
Answer: B
Question 2: Why is it inefficient for large p? (A) Modulo is slow (B) Factorial grows too big/fast (C) Primes are rare
Answer: B
Question 3: For p=4 (composite), what is 3! mod 4? Does it satisfy the theorem? (Short answer)
Answer: 6 mod 4 = 2, which is not 3 (or -1 mod 4=3), so no, as expected for composite.