# formal congruence

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

 $\displaystyle f(X_{1},\,X_{2},\,\ldots,\,X_{n})\;\underline{\equiv}\;g(X_{1},% \,X_{2},\,\ldots,\,X_{n})\pmod{m},$ (1)

iff all coefficients of the difference polynomial  $f\!-\!g$  are divisible by $m$.

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. 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};$

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. 2.

Let $p$ be a positive prime number.  It is possible that the $n^{\mathrm{th}}$ degree congruence

 $P(x)\;:=\;a_{0}x^{n}\!+\!a_{1}x^{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$.

## References

• 1 F. Stöwener: “Simultanbeweis des Fermatschen und Wilsonschen Satzes”.  – Elemente der Mathematik 30 (1975).
 Title formal congruence Canonical name FormalCongruence Date of creation 2013-03-22 14:23:50 Last modified on 2013-03-22 14:23:50 Owner pahio (2872) Last modified by pahio (2872) Numerical id 32 Author pahio (2872) Entry type Definition Classification msc 11A07 Classification msc 11C08 Synonym polynomial congruence Related topic CongruenceRelationOnAnAlgebraicSystem Related topic APolynomialOfDegreeNOverAFieldHasAtMostNRoots Related topic IdealDecompositionInDedekindDomain Related topic ExampleOfGcd Related topic FermatsLittleTheorem Related topic WilsonsTheorem Related topic FreshmansDream Related topic UsingPrimitiveRootsAndIndexToSolveCongruences Related topic SufficientConditio Defines formally congruent Defines identical congruence