Congruences

DÉFINITION

------Soient a et b deux entiers relatifs et m un entier naturel non nul. Soit Z l'ensemble des entiers relatifs.

On dit que a est congru à b modulo m et on note:   a≡b[m] si et seulement si a-b est multiple de m.

Cela est équivalent à dire qu'il existe k dans Z tel que a=b+km. 

------On a la propriété suivante : si a≡b[m] et c≡d[m], alors  on a:

i) a+c≡b+d[m]

ii) ac≡bd[m].

------la congruence modulo m est une relation d'équivalence car, elle est

--réflexive: a≡a[m]

--symétrique:  a≡b[m] équivaut à b≡a[m]

--transitive: Si  a≡b[m] et b≡c[m], alors a≡c[m]

--L'ensemble quotient est noté Z/mZ.

------La classe d'un entier a noté cl(a), est l'ensemble des b appartenant à Z tels que b soit congru à a modulo m.

cl(a) porte le nom de classe résiduelle modulo m.

------L'ensemble des classes résiduelles modulo m est Z/mZ. Ses éléments sont cl(0), cl(1),..., cl(m-1).

a est un résidu de b modulo m.

------Quand on écrit x≡y [m] avec x et y positifs. Si y est strictement inférieur à m, y est le reste de la division euclidienne de x par m.

CONSIGNE :    Dans la suite, l'écriture:  

a cg b [m]    signifie que :

a est congru à b modulo m