Let $m$ be a positive integer. Two polynomials $f(X_1,\,X_2,\,\ldots,\,X_n)$ and $g(X_1,\,X_2,\,\ldots,\,X_n)$ with integer coefficients are said to be formally congruent modulo $m$ , denoted

(1)

Remark 1. The formal congruence of polynomials is an equivalence relation in the set $\mathbb{Z}[X_1,\,X_2,\,\ldots,\,X_n]$ .

Remark 2. The formal congruence (1) implies that all integers substituted for the variables satisfy it, in other words, one can speak of an identical congruence. However, there are identical congruences that are not formal congruences; e.g. $$X^{p} \;\equiv\; X \pmod{p}$$ where $p$ is a positive prime.

Examples

1. $(X\!+\!Y)^p \;\underline{\equiv}\; X^p\!+\!Y^p \pmod{p}$ when $p$ is a positive prime number. This result is easily proved with the binomial theorem (cp. the freshman's dream) and may be by induction generalized to $$(X_1\!+\!X_2\!+\ldots+\!X_n)^p \;\underline{\equiv}\; X_1^p\!+\!X_2^p\!+\ldots+\!X_n^p \pmod{p}.$$ If one substitutes in this formal congruence 1 for all $X_1$ , $X_2$ , ..., $X_n$ , one obtains the congruence $$n^p \;\equiv\; n \pmod p;$$ similar substitution of $-1$ shows that the last congruence is valid also for negative integers $n$ . If it is supposed that $p$ is not factor of $n$ , we have got the Fermat's little theorem.
2. Let $p$ be a positive prime number. It is possible that the $n^\mathrm{th}$ degree congruence $$P(x) \;:=\; a_0x^n\!+\!a_1x^{n-1}\!+\ldots+\!a_n \;\equiv\; 0 \pmod{p},$$ where $a_i \in \mathbb{Z} \,\, \forall i$ and $p \nmid a_0$ , has $n$ modulo $p$ incongruent roots $x = x_1,\,x_2,\,\ldots,\,x_n$ . We then have the formal congruence $$P(x) \;\underline{\equiv}\; a_0(x\!-\!x_1)(x\!-\!x_2)\cdots(x\!-\!x_n) \pmod{p}.$$ Especially, we have $$x^{p-1}\!-\!1 \;\underline{\equiv}\; (x\!-\!1)(x\!-\!2)\cdots(x\!-\!p\!+\!1) \pmod{p},$$ because Fermat's little theorem guarantees the roots $x = 1,\,2,\,\ldots,\,p\!-\!1$ for the congruence $x^{p-1}\!-\!1 \equiv 0 \pmod{p}$ . If the value $x = 0$ is substituted in the previous formal congruence, it gives $$-1 \equiv (-1)^{p-1}(p\!-\!1)! \pmod{p}$$ or $$(p\!-\!1)! \;\equiv\; -1 \pmod{p},$$ which is half of Wilson's theorem. The reverse part of this theorem follows from the last congruence so that if $p$ were not prime, then the number $-1$ would be divisible by any proper divisor of $p$ .