​​Divisibilité et congruences dans $$\Z$$

Définition

On dit que deux entiers relatifs $$a$$​ et $$b$$​ sont congrus modulo $$n$$​ si leur différence $$a-b$$​ est divisible par $$n$$​. Plusieurs notations existent pour cette relation :

$$a≡b[n]$$​

$$a≡b(n)$$​

$$a≡b$$ mod $$n$$​​​​​

Si $$b$$​ est le reste de la division euclidienne de $$a$$​ par $$n$$​, alors $$a$$​ est congru à $$b$$​ modulo $$n$$​ .

Note : On dit aussi « $$a$$​ et $$b$$​ sont égaux modulo $$n$$​ ».

Exemples

·     $$17$$​ et $$8$$​ sont congrus modulo $$3$$​ parce que $$17-8=9$$​ est divisible par $$3$$​ . On écrit : $$17≡8[3].$$

·       La division euclidienne de $$34$$​ par $$9$$​ donne $$34=9×3+7$$​. $$4$$​ est donc congru à $$7$$​ modulo $$9$$​. On écrit : $$34≡7[9].$$

Propriétés

Deux entiers relatifs sont congrus modulo $$n$$​ si et seulement si le reste de leur division euclidienne par $$n$$​ est identique.

Note : Un entier relatif $$a$$​ est congru à $$0$$​ modulo $$n$$​ si et seulement si $$a$$​ est un multiple de $$n$$​ (reste de la division euclidienne de $$a$$​ par $$n$$​ est nul).

Résoudre une équation avec des congruences

On veut résoudre une équation de la forme $$ax≡b[n]$$​.

Méthode

Exemple

Résous l’équation $$3x≡2[5]$$​.

Construis un tableau :

Pour $$x=4$$​ , l’équation est satisfaite. Donc, pour tous les nombres congrus à $$4$$​  modulo $$5$$​ , l’équation est satisfaite. Les solutions sont donc :

$$S={4+5k ;k∈\Z}$$​​

Inverse modulo

L’inverse modulo $$n$$​ d’un nombre $$a$$​ est un nombre $$b$$​ tel que $$a×b≡1[n]$$​. Un tel nombre existe si et seulement si $$a$$​ et $$n$$​ sont premiers entre eux.

Conseil : Pour trouver $$b$$​, résous l’équation $$ax≡1[n]$$​.