formal congruence

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

$f(X_1,X_2,\mathrm{\dots },X_n)\underset{¯}{\equiv }g(X_1,X_2,\mathrm{\dots },X_n)(modm),$ (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,\mathrm{\dots },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(modp)$$

where $p$ is a positive prime.

Examples

1. ${(X+Y)}^p\underset{¯}{\equiv }{X}^p+Y^p(modp)$  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+\mathrm{\dots }+X_n)}^p\underset{¯}{\equiv }{X}_1^p+X_2^p+\mathrm{\dots }+X_n^p(modp).$$

   If one substitutes in this formal congruence 1 for all $X_1$, $X_2$, …, $X_n$, one obtains the congruence

   $$n^p\equiv n(modp);$$

   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_0{x}^n+a_1{x}^{n-1}+\mathrm{\dots }+a_n\equiv \mathrm{\hspace{0.33em}0}(modp),$$

   where  $a_i\in \mathbb{Z}\forall i$  and  $p\nmid a_0$,  has $n$ modulo $p$ incongruent roots  $x=x_1,x_2,\mathrm{\dots },x_n$.  We then have the formal congruence

   $$P(x)\underset{¯}{\equiv }{a}_0(x-x_1)(x-x_2)\mathrm{\cdots }(x-x_n)(modp).$$

   Especially, we have

   $$x^{p-1}-1\underset{¯}{\equiv }(x-1)(x-2)\mathrm{\cdots }(x-p+1)(modp),$$

   because Fermat’s little theorem guarantees the roots  $x=1,\mathrm{\hspace{0.17em}2},\mathrm{\dots },p-1$  for the congruence  $x^{p-1}-1\equiv 0(modp)$.  If the value  $x=0$  is substituted in the previous formal congruence, it gives

   $$-1\equiv {(-1)}^{p-1}(p-1)!(modp)$$

   or

   $$(p-1)!\equiv -1(modp),$$

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

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