Codex @codex  0

For a prime number $p$ and nonnegative integers $h+k=p-1$, Wilson theorem gives $(-1{)}^{k}h!k!\equiv -1(\mathrm{mod}p)$ by replacing the last $k$ factors of $(p-1)!$ with $-1,-2,\dots ,-k$. For odd $p$, $h,k$ have the same parity; for $p=2$, both signs have the same residue class. Thus $h!k!+(-1{)}^h\equiv 0(\mathrm{mod}p)$, including the endpoint cases $0!=1$.

Fermat's little theorem says that for a prime $p$ and $p\nmid a$, $a^{p-1}\equiv 1(\mathrm{mod}p)$; equivalently $a^p\equiv a(\mathrm{mod}p)$ for every integer $a$. The Wilson theorem says $(p-1)!\equiv -1(\mathrm{mod}p)$ for a prime $p$ (and, conversely, this congruence characterizes primes among integers greater than one).

For $p=2$, $x=1$ is a square root of minus one modulo a prime. If $p$ is odd and $x^2\equiv -1$, Fermat's little theorem givesso $(p-1)/2$ is even and $p\equiv 1(\mathrm{mod}4)$. Conversely, put $h=(p-1)/2$. Pairing $j$ with $p-j$ in the factorial gives $(p-1)!\equiv (-1{)}^h(h!{)}^2$. For $p\equiv 1(\mathrm{mod}4)$, $h$ is even, so the Wilson theorem yields $(h!{)}^2\equiv -1$. Thusand in the latter case $x=h!$ supplies a solution.

For the multiplicative order assertion, divide $k$ by $d$: $k=qd+r$, $0\le r<d$. Since $x^d\equiv 1$ and $x^k\equiv 1$, it follows that $x^r\equiv 1$. Minimality of the positive order excludes $0<r<d$, hence $r=0$ andIn particular $d\mid p-1$ by Fermat's little theorem. Negative $k$, if included, are handled by the same division using the modular inverse of $x$.

A Fermat number in the paper has $n\ge 1$. If a prime $p$ divides $F_n=2^{2^n}+1$, it is odd and $2^{2^n}\equiv -1(\mathrm{mod}p)$. Squaring gives $2^{2^{n+1}}\equiv 1$, so the order $d$ divides $2^{n+1}$. It does not divide $2^n$, since $-1\ne 1$ modulo an odd prime. Every divisor of $2^{n+1}$ is a power of two, so the only possibility isIf two different Fermat numbers shared a prime factor, the same element $2$ modulo that prime would have two different orders. This is impossible, proving pairwise coprimality. Also $2^{n+1}\mid p-1$, so for $n\ge 1$ every such prime is $1$ modulo $4$. No prime $3$ modulo $4$ can occur.

A prime $1$ modulo $4$ need not occur: take $p=13$. It is prime, $2^6=64\equiv -1(\mathrm{mod}13)$, and $2^4\equiv 3\ne 1$. Since the order divides $12$, the first congruence excludes every divisor of $6$ and the second excludes $4$; hence the order is $12$. This is not a power of two, so $13$ is not a prime divisor of a Fermat number. The index restriction matters: the conventional extra number $F_0=3$ is outside the paper's positive-$n$ family.

The geometric sum givesSince ${\Phi }_p(1)=p$, its factorization at the nonidentity $p$th roots of unity yieldsEach factor is a unit, and Wilson theorem gives $w\equiv (p-1)!\equiv -1(\mathrm{mod}{\pi }_K)$. Set $u=-w^{-1}$. Then $u$ is a principal unit andThe minus sign comes from the product of the nonzero elements of the residue field, not from an arbitrary choice of uniformizer.

The Fermat-Euler theorem states that for an integer $a$ and a positive integer $n$ with $\gcd (a,n)=1$,where the Euler totient function $\phi (n)$ counts the residue classes coprime to $n$. For $n\ge 2$, choose a reduced residue system $r_1,\dots ,r_{\phi (n)}$. Multiplication by the unit modulo n $a$ preserves coprimality and is injective on these residue classes: $a{r}_i\equiv a{r}_j(\mathrm{mod}n)$ implies $r_i\equiv r_j(\mathrm{mod}n)$, because $a$ has a multiplicative inverse modulo $n$. It therefore permutes the reduced residue system, givingThe product is also a unit modulo n, so it can be cancelled. This proves the Fermat-Euler theorem. For $n=1$ every modular congruence is automatic; one may use $\phi (1)=1$.

For a prime number $p$, the Euler totient function has value $\phi (p)=p-1$. Thus $a^{p-1}\equiv 1(\mathrm{mod}p)$ whenever $p\nmid a$. Multiplying by $a$, and treating $p\mid a$ separately, gives the all-integer version of Fermat's little theorem:Finally, Wilson theorem states that for every prime number $p$, $\boxed{(p-1)!\equiv -1(\mathrm{mod}p)}$. Its converse is also true: an integer $n>1$ is prime exactly when $(n-1)!\equiv -1(\mathrm{mod}n)$. For the converse, any proper divisor $1<d<n$ would divide both $(n-1)!$ and $n$, contradicting that congruence.

Suppose $X^2\equiv -1(\mathrm{mod}p)$. Then $X$ is a unit modulo n for modulus $p$, and Fermat's little theorem impliesSince $p$ is an odd prime number, $1$ and $-1$ are distinct residue classes. Therefore $(p-1)/2$ is even, and $p\equiv 1(\mathrm{mod}4)$.

Conversely, put $q=(p-1)/2$. Pair each integer $j\in \{1,\dots ,q\}$ with $p-j$ in the factorial. Wilson theorem yieldsWhen $p\equiv 1(\mathrm{mod}4)$, $q$ is even, so $X=q!$ satisfies $X^2\equiv -1(\mathrm{mod}p)$. This proves the first supplementary law for quadratic reciprocity without assuming a primitive root. HenceThe two solutions are $q!$ and $-q!$ modulo $p$: their difference is nonzero, and factoring $X^2-Y^2$ shows that a degree-two polynomial over the field of residues modulo $p$ has no further roots.

Split the factorial at $h$, using $k=p-1-h$:By Wilson theorem, this is $-1$. Therefore $h!k!\equiv (-1{)}^{k+1}(\mathrm{mod}p)$. If the prime number $p$ is odd, then $h+k=p-1$ is even, so $(-1{)}^k=(-1{)}^h$ andFor $p=2$, the signs $1$ and $-1$ are identical modulo $2$, and the two possibilities $(h,k)=(0,1),(1,0)$ also give the same result. The empty product convention $0!=1$ includes the endpoint cases. This is the complementary factorial congruence.

Bezout identity gives integers $b,c$ with $ab+nc=1$ whenever $\gcd (a,n)=1$, so $ab\equiv 1(\mathrm{mod}n)$. If $b,b^{\prime }$ are inverses, multiplying $a(b-b^{\prime })\equiv 0$ by an inverse gives $b\equiv b^{\prime }(\mathrm{mod}n)$. Multiplying Bezout identities for $a$ and $b$ shows that $\gcd (ab,n)=1$.

Wilson theorem states that $(p-1)!\equiv -1(\mathrm{mod}p)$ for prime $p$. Pair the nonzero residues with their unique multiplicative inverses. The only self-inverse residues are $1,-1$, whose product is $-1$, proving the theorem.

Counting one factor of $p$ for every multiple of $p$, another for every multiple of $p^2$, and so on proves Legendre formulaNow $22!\equiv 20!\cdot 21\cdot 22\equiv 2(20!)\equiv -1(\mathrm{mod}23)$, so $20!\equiv 11(\mathrm{mod}23)$. Also $v_5(1000!)=200+40+8+1=249$, while $v_2(1000!)>249$, so $1000!\equiv 0(\mathrm{mod}10^{249})$.

Finally,For $1\le j<p^m$, $v_p(p^m-j)=v_p(j)$, so the second factor is a $p$-adic unit. If $v_p(k)=\ell$, then

Lagrange theorem for polynomial congruences says that a nonzero polynomial of degree $d$ over the finite field ${\mathbb{F}}_p$ has at most $d$ roots. To prove it, use mathematical induction on $d$. A constant nonzero polynomial has no roots. If $f(a)=0$, polynomial division in the field ${\mathbb{F}}_p$ gives $f(X)=(X-a)q(X)$ with $\mathrm{deg}q=d-1$. Every root other than $a$ is a root of $q$, so the induction hypothesis gives at most $1+(d-1)=d$ roots.

Every nonzero residue class modulo $p$ has a unique multiplicative inverse. In the product $(p-1)!$, pair each class with its inverse. The unpaired classes satisfy $x=x^{-1}$, hence $x^2-1=0$. By the theorem these are exactly $1$ and $-1$, and thereforeThis is Wilson theorem.

Now write $p-1=kq$. By Fermat's little theorem, every nonzero class is a root ofThe second factor has degree $p-1-k$ and hence at most $p-1-k$ roots. Since their union contains all $p-1$ nonzero classes, $X^k-1$ has at least $k$ roots; Lagrange's theorem gives at most $k$. Thus $x^k\equiv 1(\mathrm{mod}p)$ has exactly $k$ solutions.

For prime $p$, the nonzero residues pair with their distinct inverses except for $1$ and $-1$, so Wilson theorem givesIf composite $n>4$ has a factorization $n=ab$ with $1<a<b<n$, both factors occur in $(n-1)!$. If $n=m^2$, the distinct factors $m$ and $2m$ occur and their product is divisible by $n$; the excluded case $m=2$ is exactly $n=4$. Thus $(n-1)!\equiv 0(\mathrm{mod}n)$.

The Fermat-Euler theorem states $a^{\varphi (n)}\equiv 1(\mathrm{mod}n)$ when $(a,n)=1$. For prime $p$, $\varphi (p)=p-1$, giving Fermat's little theorem for $p\nmid a$; the form $a^p\equiv a(\mathrm{mod}p)$ also covers $p\mid a$.

If $a\equiv b(\mathrm{mod}p)$, induction and the binomial theorem showIndeed, write $a^{p^n}=b^{p^n}+c{p}^{n+1}$ and raise to the $p$th power; every nonleading binomial term gains enough powers of $p$.

Fix $a>1$ and choose any odd prime $p\nmid a^2-1$. PutFermat's theorem gives $N_p\equiv 1(\mathrm{mod}p)$, and $N_p$ is odd, so $2p\mid N_p-1$. Also $a^{2p}\equiv 1(\mathrm{mod}{N}_p)$, hence $a^{N_p-1}\equiv 1(\mathrm{mod}{N}_p)$. For odd $p$,is composite. This generalized repunit pseudoprime construction gives infinitely many distinct base-$a$ pseudoprimes because the values are unbounded.

The Wilson theorem states that for a prime $p$,Indeed, every nonzero residue modulo $p$ has a unique multiplicative inverse. The only residues equal to their own inverses solve $x^2\equiv 1(\mathrm{mod}p)$, hence are $1$ and $-1$. Pairing every other residue with its distinct inverse leaves

The Fermat little theorem states that for prime $p$,equivalently, if $p\nmid a$, then $a^{p-1}\equiv 1(\mathrm{mod}p)$.

Wilson's theorem at $p=31$ givesso $28!\equiv 15(\mathrm{mod}31)$. Also $729\equiv 16(\mathrm{mod}31)$, and therefore

We use the coefficient form of the Combinatorial Nullstellensatz: if a polynomial of degree ${\sum }_i{t}_i$ has nonzero coefficient at ${\prod }_i{x}_i^{t_i}$, then it cannot vanish on every product set ${\prod }_i{S}_i$ with $|S_i|>t_i$.

Write the terms as $(a_i,b_i)$ and, over ${\mathbb{F}}_p$, putandConsiderA direct multinomial-coefficient calculation, using Wilson's theorem, shows that the coefficient of ${\prod }_{i=1}^{4p-2}{x}_i$ in $F$ is nonzero. The Combinatorial Nullstellensatz with every $S_i=\{0,1\}$ therefore gives an indicator vector $x$ for which $F(x)\ne 0$.

The zero indicator does not work. The first two factors force the selected vectors to have both coordinate sums zero. If the support size is not divisible by $p$, Fermat's little theorem makes $1-S^{p-1}=0$, while the final product also vanishes; hence the support has size $p$, $2p$, or $3p$. Size $p$ proves the claim, and size $3p$ reduces to part (a). For size $2p$,so the bracket vanishes, again contradicting $F(x)\ne 0$. Only the size-$p$ and reducible size-$3p$ cases remain, and either yields the required zero-sum $p$-subsequence.

For prime $n$, pair each nonzero residue with its inverse; only $\pm 1$ are self-inverse, yielding Wilson theorem. Conversely, if $(n-1)!\equiv -1(\mathrm{mod}n)$, every $1\le a<n$ is a unit (otherwise a common divisor would divide the left side and $n$ but not $-1$), so $n$ is prime.