Question

Wilson's theorem says that a numberis prime if and only if
$\mathbf{(}\mathbf{N}\mathbf{-}\mathbf{1}\mathbf{)}\mathbf{!}\mathbf{=}\mathbf{-}\mathbf{1}\mathbf{(}\mathbf{mod}\mathbf{}\mathbf{N}\mathbf{)}$.

(a) If is prime, then we know every number$\mathbf{1}\mathbf{\le }\mathbf{x}\mathbf{<}\mathbf{p}$ is invertible modulo . Which of thesenumbers is their own inverse?
(b) By pairing up multiplicative inverses, show thatrole="math" localid="1658725109805" $\mathbf{(}\mathbf{p}\mathbf{-}\mathbf{1}\mathbf{)}\mathbf{!}\mathbf{=}\mathbf{-}\mathbf{1}\mathbf{(}\mathbf{mod}\mathbf{}\mathbf{p}\mathbf{)}$ for prime p.
(c) Show that if N is not prime, then$\mathbf{(}\mathbf{N}\mathbf{-}\mathbf{1}\mathbf{)}\mathbf{!}\mathbf{\not\equiv }\mathbf{(}\mathbf{mod}\mathbf{}\mathbf{N}\mathbf{)}$ .(Hint: Consider$\mathbf{d}\mathbf{=}\mathbf{gcd}\mathbf{(}\mathbf{N}\mathbf{,}\mathbf{(}\mathbf{N}\mathbf{-}\mathbf{1}\mathbf{)}\mathbf{!}\mathbf{.}\mathbf{)}$
(d) Unlike Fermat's Little Theorem, Wilson's theorem is an if-and-only-if condition for primality. Why can't we immediately base a primality test on this rule?

Short answer

• p - 1 and 1 are their own modulo inverses.
• (p - 1) ! $\equiv$(p - 1) . 1p - 3/2.1 $\equiv$-1 (mod p) is showed.
• It has been shown that if is not a prime then (N - 1)! $\ne$(mod N).

• This method would require roughly modular multiplications, rendering it impractical; nevertheless, considerations about modular residues and primes set the groundwork for more practical processes. The primality test could not be immediately based on this rule.

Step-by-step solution

Step 1: Introduction to the Concept

In number theory, Wilson's theorem states that any prime p divides (p - 1) ! + 1 , with n! being the factorial notation for $1\times 2\times 3\times 4\times ...\times \mathrm{n}$.

Step 2: Solution Explanation for numbers of their own inverse

a)

When p is prime, $\mathrm{x}\not\equiv \pm 1(\mathrm{mod}\mathrm{p})$, where $1\le \mathrm{x}<\mathrm{p}$, has solutions, is required for a number $1\le \mathrm{n}<\mathrm{p}$to be ${\mathrm{x}}^2\equiv 1(\mathrm{mod}\mathrm{p})$its own inverse modulo p. As a result, p - 1 and 1 are their own modulo p inverses.

Example:

For $\mathrm{p}=5,\mathrm{n}=\{1,2,3,4\};$

2 and 3 are multiplicative inverses, so their value is

2*3 mod 5 = 6 mod 5

= 1

In the same way that 4 is a self-multiplicative inverse, their value is

4*4 mod 5 = 16 mod 5

= 1

Step 3: Solution Explanation for depicting prime p

b)

If p = 2, we're divided into 1 = p - 1 and 1 !$\equiv -1$(mod 2). The other factors in ( p - 1 )! for $\mathrm{p}\ge 3$could $\frac{\mathrm{p}-3}{2}$inverse pairs and ( p - 1 )! $\equiv$( p - 1 ) . 1 ( p - 1) . 1( p - 3) / 2.1$\equiv -1$(mod p)

Example:

Assume p = 5 and n = {1,2,3,4} .

There is only one pair of inverses here, namely 2 and 3. As a result, for p = 5,$\frac{\mathrm{p}-3}{2}=1$

Step 4: Solution Explanation for Prime Test

c)

If N is composite, then there exists k|N and k<N .

So, k | (N-1) and k$\equiv$1 (mod N).

This means k needs to divide 1.

So, N must be prime or 1.

But, N isn't a prime.

Hence, if N isn't prime then (N-1)! $\ne 1(\mathrm{mod}\mathrm{N})$.

Step 5: Solution Explanation for Wilson's theorem's primality test

d)

N is prime if and only if (N - 1)! = -1 (mod N), according to Wilson's theorem.

This approach would require around N modular multiplications, making it unworkable; nonetheless, theories regarding modular residues and primes lay the foundation of more practical procedures.

As a result, this rule could not be used to perform a primality test right away.