Wilsons Theorem In C++

Wilson's Theorem asserts that a number can be classified as a prime number by examining the characteristics of factorials and modular arithmetic within the realm of mathematical concepts. This theorem was devised by the mathematician John Wilson and later validated by Joseph-Louis Lagrange. The theorem articulates that:

For a positive integer \( p > 1 \): \( (p-1)! \equiv -1 \pmod{p} \). This lemma implies that the modular inverse of \( (p-1)! \) exists for \( p > 1 \) if \( p \) is a prime number. Additionally, if \( p \) is not prime, then \( (p-1)! \equiv -1 \pmod{p} \).

Wilson's theorem serves as a valuable theoretical concept for understanding prime numbers. Calculating the factorial of a large number can be challenging due to the exponential increase in magnitude. Nonetheless, Wilson's theorem continues to be a fundamental principle in number theory, shedding light on the significance of number properties within modular arithmetic.

Alternative techniques are:

• ✅ Sieve of Eratosthenes: Efficient for generating all prime numbers on or below a certain limit.
• ✅ Probabilistic Primality Tests: Techniques like the Miller-Rabin test provide efficient primality-finding for large integers, by common consent.

Theoretical Importance of Wilson's Theorem

In spite of its inefficiency, Wilson's theorem is historically significant from a number theory perspective; it offers the following: Direct connections between factorials and prime numbers and unique modular properties of primes. Insights into modular arithmetic, which is foundational in fields, such as cryptography. On historical background, Wilson's theorem remained one of the earliest results, to put formal, explicit conditions on primality.

• ✅ Factorial Representation: The factorial (p-1)!(p-1)! indicates the product of all integers from 11 to p-1.
• ✅ Prime Condition: The residue 1, 2, ..., p-1 1, 2 ... p-1 under modulo p where p is prime that creates a complete residue system such that each element has a well-defined and unique inverse.
• ✅ Modular Result: The relation (p-1)!≡-1(mod p),(p-1)!≡-1(mod p) basically means that while the product of all numbers from 1 to p-1 is computed and divided by the prime p, then, indeed, the modulo returns -1.

How Does Wilson's Theorem Work?

• ✅ Prime Numbers: The theorem presents a way to check for prime numbers and can provide a faster alternative to brute force trial division.
• ✅ Factorials: Factorials increase rapidly on incrementing the number, and finding large factorials modulo n is computationally expensive. Hence, the theorem works on factorials with modular arithmetic.
• ✅ Computational Complexity: Wilson's Theorem is more complex, as finding the factorial of large numbers is not an easy task. Despite that, the theorem remains a useful tool for understanding mathematical concepts or while working with selected modular applications.

Modulo Operations and Factorials

In this tutorial, we will apply modulo arithmetic in conjunction with factorial operations. When provided with the double factorial of (n-1)(n-1), we will calculate the double factorial modulo n and verify if it equals n-1. The complexity of this computation significantly increases for larger values of n, primarily due to the handling of extremely large numbers.

Advantages of Wilson's Theorem

• ✅ Mathematical Insight: Wilson's Theorem exposes the nature of primes, putting in clarity the relation between factorials and prime numbers.
• ✅ Verifying Primality: The theorem furnishes an explicit condition for testing whether numbers are prime; though expensive for computation, it is trustworthy for certification of smaller primes.
• ✅ Teaching Tool: Wilson's Theorem can be used as a teaching method in a classroom to introduce modular arithmetic and prime properties that provide students insight into number theory and prime behavior.

Disadvantages of Wilson's Theorem

• ✅ Inefficiency for Large Numbers: The computation of factorials for large numbers explodes in complexity.
• ✅ Alternative Methods for Practical Use: There are efficient algorithms, such as Miller-Rabin primality testing and AKS primality test that are created for practical applications concerning primality testing of very large numbers.
• ✅ Computational Limitation: The handling of large factorials during modulus operations tends to overflow in languages like C++ , where the size of int is limited. It creates a limit to Wilson's Theorems' applicability in competitive programming and practice.

Example:

Let's consider an example to demonstrate the Wilson theorem using C++.

#include <iostream>
using namespace std;

// Function to find the factorial
long long factorial_modulas(int num, int p) {
    long long res = 1;
    for (int i = 1; i <= num; i++) {
        res = (res * i) % p;
    }
    return res;
}

// Function to check the num is prime
bool isPrime_WilsonNumber(int p) {
    if (p <= 1) return false;
    if (p == 2) return true; // 2 condition for even prime number
    long long f = factorial_modulas(p - 1, p);
    return (f + 1) % p == 0;
}
//Main function
int main() {
    int number;
    cout << "Please enter the number: ";
    cin >> number;

    if (isPrime_WilsonNumber(number)) {
        cout << number << " is a prime number from the Wilson's Theorem.\n";
    } else {
        cout << number<< " is not a prime number from the  Wilson's Theorem.\n";
    }
    return 0;
}

Output:

Please enter the number: 45
45 is not a prime number from the  Wilson's Theorem.

Explanation:

This program takes a number from the user and checks it using Wilson's Theorem whether its prime or not. Wilson's Theorem states that a number p>1 is prime if and only if (p-1)!≡-1(p)(p-1)!≡-1(mod p).

• ✅ factorial_modulas Function: This function calculates factorial of num (which is p-1) modulo p to make the calculation feasible and avoid overflow. It multiplies numbers from 1 to num using a loop and taking modulo p at each multiplication.
• ✅ isPrime_WilsonNumber Function: This function checks if p is prime using Wilson's theorem. It returns false if p <= 1 because it is not a prime. For p = 2, it returns true (as 2 is the only even number that is prime). For any other value of p, it calculates factorial of p-1 % p and checks if fact(p-1)+1 %p ==0 in this case we can say that the number is prime.
• ✅ Main Function: The main function takes the user input, applies Wilson's Theorem using helper functions , and prints out whether the number is prime or not.

Conclusion:

In summary, Wilson's Theorem presents a straightforward method to verify prime numbers through factorial modular properties. While not the most efficient technique due to the rapid growth of factorial values with larger numbers, it serves as a fascinating demonstration of the deep connection between primes and modular arithmetic. Despite its limited practical utility in prime number identification because of its computational demands, the theorem offers significant educational value in understanding prime number characteristics and modular congruence testing. For more efficient prime number identification on a larger scale, methods like the Sieve of Eratosthenes or probabilistic primality tests such as Miller-Rabin are preferred. Nevertheless, Wilson's Theorem remains relevant for its simplicity and historical significance in defining prime numbers explicitly.