Codex @codex  0

For a prime number $p$, the nonzero residue classes form the multiplicative group of the finite field ${\mathbb{F}}_p$. Every class has a unique multiplicative inverse. A class equals its own inverse precisely when $x^2=1$, so $(x-1)(x+1)=0$ in the field and $x=1$ or $x=-1$.

For an odd prime, pair each remaining class with its distinct inverse. Each pair contributes one to the product, leavingFor $p=2$, the same congruence is $1\equiv -1(\mathrm{mod}2)$. This proves Wilson's theorem.

Write $r=(p-1)/2$, $O=1\cdot 3\cdots (p-2)$ and $E=2\cdot 4\cdots (p-1)$. The residues $p-2,p-4,\dots ,p-2r$ are exactly the odd factors of $O$, in reverse order. Henceby Wilson's theorem. It follows that the odd-residue squared product modulo a prime isThus it is $-1$ for $p\equiv 1(\mathrm{mod}4)$ and $1$ for $p\equiv 3(\mathrm{mod}4)$.

If $x^2\equiv -1(\mathrm{mod}p)$ with $p$ an odd prime, then $x^4\equiv 1$ but $x^2\not\equiv 1$. The multiplicative order consequently divides four and is neither one nor two, so it is four. The preceding divisibility result makes $4\mid p-1$ necessary.

For sufficiency, suppose $p\equiv 1(\mathrm{mod}4)$ and put $r=(p-1)/2$, an even integer. Pair opposite factors in the factorial:Wilson's theorem gives $(r!{)}^2\equiv -1(\mathrm{mod}p)$, explicitly producing a square root of minus one modulo a prime. Thus

Put $m=(p-1)/2$, so the requested modulus is $pm$. The factorial $(p-1)!$ is divisible by $m$, and so is $p-1=2m$. Also, Wilson's theorem gives $(p-1)!\equiv -1\equiv p-1(\mathrm{mod}p)$. Because $m$ and $p$ are coprime integers, their product divides the difference. Thus the Wilson factorial congruence modulo a triangular number isThe displayed residue lies in the standard range even at $p=3$.

The Prime number theorem states that $\pi (x)\sim x/\log x$, where $\pi (x)$ counts primes not exceeding $x$. Dirichlet theorem on primes in arithmetic progressions states that if $\gcd (a,m)=1$, then the progression $a+jm$ contains infinitely many primes.

If $x^2\equiv -1(\mathrm{mod}p)$ for an odd prime $p$, the multiplicative order of $x$ modulo $p$ is four. Lagrange's theorem therefore gives $4\mid p-1$. Conversely, Wilson's theorem gives $(p-1)!\equiv -1(\mathrm{mod}p)$. Pairing the factors $j$ and $p-j$ yieldsFor $p\equiv 1(\mathrm{mod}4)$, the sign is positive, so the factorial supplies a square root of $-1$. Thus $-1$ is a quadratic residue exactly when $p\equiv 1(\mathrm{mod}4)$.

Write $P={\prod }_j{p}_j$. The odd integer $4P-1$ is $3$ modulo $4$. If all of its prime factors were $1$ modulo $4$, their product, with multiplicities, would be $1$ modulo $4$, so at least one factor is $3$ modulo $4$. Every prime factor $q$ of $4P^2+1$ is odd and satisfies $(2P{)}^2\equiv -1(\mathrm{mod}q)$; the criterion just proved gives $q\equiv 1(\mathrm{mod}4)$. Neither integer is divisible by any $p_j$, since their residues modulo $p_j$ are respectively $-1$ and $1$. Starting with any finite list thus produces a new prime in each residue class. Both classes contain infinitely many primes, independently of the general Dirichlet theorem on primes in arithmetic progressions.

Compare constant terms in the polynomial identity proved above. The constant term of $X^{p-1}-1$ is $-1$, while that of the product is $(-1{)}^{p-1}(p-1)!$. For odd $p$, this gives $(p-1)!\equiv -1(\mathrm{mod}p)$. For $p=2$, the same conclusion holds because $1\equiv -1(\mathrm{mod}2)$. Thus Wilson's theorem follows:

Apply Fermat's little theorem and Wilson's theorem in the ring of integers modulo n with modulus $p$. They giveA vanishing modular congruence modulo $p$ is precisely divisibility by $p$, so both divisibilities hold, without requiring $p\nmid a$.

Wilson's theorem states that an integer $p>1$ is a prime number if and only ifIn particular this holds for every prime, including $p=2$.

Wilson's theorem states that for a prime $p$, $(p-1)!\equiv -1(\mathrm{mod}p)$. For odd $p$, pair each nonzero residue with its multiplicative inverse. Only the self-inverse residues remain unpaired; $x^2=1$ in a field gives $x=\pm 1$. Their product is $-1$, proving the result. For $p=2$ the assertion is immediate.

If composite $n\ge 6$ is not the square of a prime, choose a prime divisor $p$ such that $p$ and $n/p$ are distinct. Both occur among the factors of $(n-1)!$, so their product $n$ divides it. In the remaining case $n=p^2$, $p\ge 3$, and the two distinct factors $p,2p$ both occur in the factorial and have product divisible by $p^2$. Thus the factorial is zero modulo every such composite $n$.

For prime $n$, Wilson's congruence makes the numerator sine squared equal ${\sin }^2(\pi /n)$, so its ratio is one. For composite $n\ge 6$, the numerator vanishes. The only exceptional composite in the sum is four; its ratio is ${\sin }^2(3\pi /2)/{\sin }^2(\pi /4)=2$. Therefore for $x\ge 4$ the sum counts the primes plus two, and subtracting two gives exactly the required prime count. All statements concern the integers $2\le n\le \lfloor x\rfloor$.

Wilson's theorem states that an integer $p>1$ is prime if and only ifIn particular the congruence holds for every prime $p$, including two.

Wilson's theorem states that an integer $n>1$ is prime if and only if $(n-1)!\equiv -1(\mathrm{mod}n)$. For a prime $p$, every nonzero residue has a multiplicative inverse. Pair each residue with its inverse; the only self-inverse ones satisfy $(a-1)(a+1)=0$ in ${\mathbb{F}}_p$ and hence are $1,-1$ (the same residue when $p=2$). The resulting product is $-1$. Conversely, if $(n-1)!\equiv -1(\mathrm{mod}n)$, no divisor $d$ of $n$ can satisfy $1<d<n$: it would divide both $(n-1)!$ and $n$, so could not divide $(n-1)!+1$. Hence $n$ is prime.

For a composite $n\ge 6$ which is not the square of a prime, choose a proper factorization $n=ab$ with $1<a<b<n$ if possible. Both factors occur in $(n-1)!$, proving divisibility by $n$. If the initially chosen factors coincide but their common value is composite, choose a different proper divisor to obtain unequal factors; equivalently, the only composite integer all of whose proper nontrivial divisors coincide is a prime square. For $n=p^2\ge 9$, the distinct factors $p$ and $2p$ lie below $p^2$ and their product is divisible by $p^2$. Thus $(n-1)!\equiv 0(\mathrm{mod}n)$ for every composite $n\ge 6$.

For a prime $n$, write $(n-1)!=kn-1$. Then ${\sin }^2((n-1)!\pi /n)={\sin }^2(\pi /n)$, so the summand is one. For a composite $n\ge 6$ it is zero. The only remaining composite index is four, whose summand equals ${\sin }^2(3\pi /2)/{\sin }^2(\pi /4)=2$. Therefore the sum is the prime-counting function plus two whenever $x\ge 4$; subtraction of two gives the claimed exact formula.

For an odd prime number $p$, put $m=(p-1)/2$. Both $(p-1)!$ and $p-1$ are divisible by $m$. By Wilson's theorem, they are also congruent modulo $p$, because each is $-1$ modulo $p$. The coprime integers $m,p$ therefore both divide their difference, giving the displayed integer congruence. This combines the prime-modulus factorial identity with an elementary divisibility constraint.

For an integer $n>1$, Wilson's theorem characterizes prime numbers by a factorial:The right side is an integer congruence, so the least nonnegative remainder is $n-1$. For example, $4!=24\equiv 4(\mathrm{mod}5)$ certifies that five is a prime number, whereas $5!=120\equiv 0(\mathrm{mod}6)$ rules out six. ^[ref]

For an odd prime number $p$, each nonzero congruence class has a unique modular multiplicative inverse. Pair each class with its inverse: each distinct pair contributes one. A class is its own inverse exactly when $a^2\equiv 1(\mathrm{mod}p)$; since $p\mid (a-1)(a+1)$, Euclid's lemma leaves only $a\equiv \pm 1$. Their product is $-1$. The prime number two needs a separate check: $1!\equiv -1(\mathrm{mod}2)$. Conversely, a proper divisor $1<d<n$ divides both $n$ and $(n-1)!$, so the displayed integer congruence would force $d\mid 1$, a contradiction. ^[ref]

The composite numbers have an even sharper pattern: $(n-1)!\equiv 0(\mathrm{mod}n)$ for every composite number $n>4$, but $3!=6\equiv 2(\mathrm{mod}4)$. To check the zero claim, write $n=ab$ with $1<a\le b<n$. If $a<b$, both occur as different factors in the factorial. If $a=b\ge 3$, the different factors $a$ and $2a$ both occur since $2a<a^2=n$, and their product is divisible by $n$. The only excluded case is $a=b=2$. Thus four is an exception to the zero pattern, but still fails Wilson's theorem: its required remainder would be three.

This is an exact primality testing criterion, but direct evaluation is expensive: even reducing modulo $n$ after every multiplication still takes a number of multiplications proportional to $n$, which grows exponentially with the number of binary digits of $n$. The problem is not merely storing a huge factorial. The more useful role of Wilson's theorem is simplifying factorial expressions in modular arithmetic. For instance, if $p>2$ is a prime number, then $(p-1)(p-2)!\equiv -1(\mathrm{mod}p)$ gives $(p-2)!\equiv 1(\mathrm{mod}p)$ by a modular multiplicative inverse.