Wilson's Theorem



Wilson's Theorem is a result in number theory that provides a necessary and sufficient condition for a positive integer $n$ to be prime. It states that a positive integer $n$ is prime if and only if:

$$(n−1)! \equiv −1\mod {n}$$

In other words, if $(n−1)!$ leaves a remainder of -1 when divided by $n$, then $n$ is prime. Conversely, if $n$ is prime, then $(n−1)!$ will leave a remainder of -1 when divided by $n$.

Applications of Wilson's Theorem include:

Primality Testing: Wilson's Theorem provides a theoretical basis for a primality test, although it is not practical for large numbers due to the computational complexity of calculating factorials for large integers.

Generating Prime Numbers: While not efficient for generating large prime numbers directly, Wilson's Theorem can be used in combination with other primality tests and algorithms for generating primes in specific ranges or for certain applications.Let's illustrate Wilson's Theorem with an example:

consider the prime number $p=5$. According to Wilson's Theorem, we need to check if 
$$(5−1)!≡−1 \pmod{5}$$

$$(5−1)!=4!=4×3×2×1=24$$

Now, let's find the remainder of 24 when divided by 5:

$24 \pmod{5}=4$

So  $24 \equiv -1 \pmod{5}$
This means that 5 satisfies $(5−1)!≡−1 \pmod{5}$, confirming Wilson's Theorem. So 5 is prime.

Proof:Consider the set of numbers $S=\{1,2,3,…,p−1\}$. This set consists of all positive integers less than $p$.


Now, let's find the product of all elements in $S$, and then take this product modulo $p$:

$$P=1×2×3×…×(p−1)\pmod {p}$$

We can pair each number $a$ in $S$ with its multiplicative inverse modulo $p$, denoted as $a^{−1}$, such that $a⋅a^{−1} \equiv 1 \pmod{p}$. Note that for every $a$ in $S$ (except for 1 and $p-1$; there inverses are the number itself), there exists a unique $a^{−1}$ also in $S$.

So, after pairing all elements in $S$ with their inverses, we get:

$$P=(1) ×(2⋅2^{−1})×(3⋅3^{−1})×…×(p−1) \pmod{p}$$
So we have shown that
$$(p-1)!=p-1=-1\pmod{p}$$

For the converse, suppose that $(n-1)! \equiv -1 \pmod{n}$. We then have $(n-1)! \equiv -1 \pmod{m}$ for any factor $m$ of $n$.If $m<n$, then $m$ appears as a factor of $(n-1)!$, so $(n-1)! \equiv 0 \pmod{m}$ and hence $-1 \equiv 0 \pmod{m}$. This implies that $m=1$, so we conclude that $n$ has no proper factors and is therefore prime.

Comments

Post a Comment

Popular posts from this blog

Number Theory CST 292 KTU IV Semester Honors Course Notes Dr Binu V P 9847390760

About me Syllabus Scheme Teaching Plan Model Question Paper University Question Papers Assignment-1 Module-1  Introduction Well ordering principle Group Ring Fields Group Ring Fields in detail Divisibility Modular Arithmetic GCD- Euclidean Algorithm Bezout's Identity Extended Euclidean Algorithm LCM-Least Common Multiple Linear Diophantine Equations Modular Division Module-II Prime Numbers and Prime-Power Factorisation Fermat and Mersenne Prime Primality Testing and Factorization Miller Rabin Primality Testing Algorithm Fermat  Factorization Congruence Modular Exponentiation Linear Congruences Simultaneous Linear Congruences- Chinese Remainder Theorem Fermat's Little Theorem and Euler's Theorem Wilson's Theorem Module-III Congruence with Prime modulus Congruence with Prime power modulus Pseudoprime and Carmichael Numbers Euler's Totient Function Cryptography The Group of Units - Primitive Roots Module-IV Quadratic Residues-Legendre and Jacobi Symbols Arithmetic Func
Read more

Well Ordering Principle

In mathematics, the well-ordering principle states that every non-empty set of positive integers contains a least element. In other words, the set of positive integers is well-ordered by its "natural" or "magnitude" order in which $x$ precedes $y$ if and only if  $y$ is either $x$ or the sum of $x$ and some positive integer (other orderings include the ordering $2,4,6$; and $1,3,5$). The phrase "well-ordering principle" is sometimes taken to be synonymous with the "well-ordering theorem". On other occasions it is understood to be the proposition that the set of integers $\{…,−2,−1,0,1,2,3,…\}$ contains a well-ordered subset, called the natural numbers, in which every nonempty subset contains a least element. Well-ordering Principle: If $S$ is a non-empty set of non-negative integers, then $S$ has a least element, i.e., there is an integer $c \in S$ such that $c \le x$ for all $ x \in S$. The principle of mathematical induction follows direct
Read more