Condition for a Prime Number

Question

Let there be any prime number $p$. Does it hold that for every $p$
$$(p-1)!=(p-1) \pmod p $$ I came across this condition through trial and error while coding for a function which looks for prime numbers in between two given numbers and applies a condition to every natural number in between to check if its a prime number. It listed every single prime number in the interval (1,1000). I'm unsure whether this holds true for every prime number, and if so, I'm curious how does it work.

Answer 1

Yes, for all prime p,

$$(p-1)!=(p-1) \ (mod p)$$

To understand this we will need some preliminary information.

1 Bézout's identity

It states that if the greatest common divisor (GCD) of $a$ and $b$ is $d$, then there exist integers x and y such that

$$ax+by=d$$

2 Concept of Coprime

If $a$ and $b$ are coprime, then the greatest common divisor of $a$ and $b$ is $1$.

A prime number p is coprime with every integer smaller than itself. So, for any positive integer $a$ less than $p$, we have:

$$ax+py=1$$ $$ax = 1-py$$ $$ax \equiv 1 \ (mod \ p)$$

Thus, for any $a<p$, there must be an $x$ such that $ax \equiv 1 \ (mod \ p)$.

3 Modular Multiplicative Inverse

If $ax \equiv 1 \ (mod \ m)$, a is called the modular multiplicative inverse of x with respect to modulus m. There are some properties we need to know about this concept.

• There is at most one integer x, which is modular multiplicative inverse of $a$ in the range $0<x<m$, with respect to modulus $m$.
• Modular multiplicative inverses of $m-1$ and $1$ are themselves with respect to modulus m.
• If m is a prime, there is no $a$ such that $a^2 \equiv 1 \ (mod \ m)$ except $a=1$ or $a=m-1$

We now have the information to prove the conjecture,

$$(p-1)! = (p-1)(p-2)!$$

$$(p-1)! \equiv (p-1) . (p-2)! \ (mod \ p)$$

For $p=2$ or $p=3$, the congruence is trivially true. If $p>3$, $(p-2)!$ has an even number of terms, each of which can be paired with its modular inverse. (We do not include 1 because the modular inverse of 1 is itself). Because we know that for an arbitrary integer $a$ that satisfies $1<a<p-1$, there is an $x$ in the range $1<x<p-1$ such that $ax=1 \ (mod \ p)$ and $a\neq x$, and these $x$'s are unique for every value of $a$. In fact, this $(p-2)!$ product consists of $(a_{1}.x_{1}).(a_{2}.x_{2})... (a_{n}.x_{n})$. Since the value of each $a_i.x_i$ product in modulo p will be $1$, we can say $(p-2)! = 1 \ (mod \ p)$, finally we get the result:

$$(p-1)!=(p-1) \ (mod p)$$