Arithmétique modulaire

Guide

La première partie de ce document est une introduction de l'anneau ZZ/ nZZ à partir des congruences.
La deuxième partie met l'accent sur quelques résolutions de problèmes où l'utilisation des congruences est fondamentale ou simplement pratique. Ce document n'a aucune prétention à être complet ni même achevé. On espère qu'il peut être utile ainsi.

Définition et opérations algébriques

Définition

Une classe de congruence modulo n est un sous-ensemble de ZZ de la forme
a+n={a+nx,x}
avec a un entier. L'ensemble des classes de congruences modulo n est noté /n. On note aussi
a+nZZ = a mod n
Un entier b est appelé un représentant de la classe amodn si b et a sont congrus modulo n.


Exemple :

On choisit en général les représentants entre 0 et n1, ce qui est toujours possible.
Le reste de la division euclidienne de a par n est bien un représentant de a mod n qui est compris entre 0 et n1.

Mais il est quelquefois commode de prendre les représentants entre 12(n1) et 12(n1) et même de les prendre quelconques.
Exercice : Classes


Exemple pour plus tard : Il est quand même plus facile de 7alcu loiestpuissance k-ième de la classe 742 mod 743 en utilisant le représentant de cette classe qu'est -1. Ainsi :

742 k=(1) k mod 743

742 4772=1 mod 743

Opérations

On définit les opérations algébriques d'addition, soustraction, multiplication par
(amodn)+(bmodn)=(a+bmodn)
(amodn)(bmodn)=(abmodn)
(amodn)×(bmodn)=(a×bmodn).

Mais nous écrirons souvent a+b mod n, par exemple

22 + 1 mod 24 = 23 mod 24 , 22 times 1 mod 24 = 22 mod 24
et même
22 + 1 equiv 23 mod 24 , 22 times 1 equiv 22 mod 24 .
On peut voir ici quelques tables d' addition ou de multiplication.
Théorème : ZZ/ nZZ est un anneau commutatif.

Exercices : Opérations , Carrés Somme et produit

Table d'addition




Voici la table d'addition dans ZZ/8ZZ :
+ 0 1 2 3 4 5 6 7
0 0 1 2 3 4 5 6 7
1 1 2 3 4 5 6 7 0
2 2 3 4 5 6 7 0 1
3 3 4 5 6 7 0 1 2
4 4 5 6 7 0 1 2 3
5 5 6 7 0 1 2 3 4
6 6 7 0 1 2 3 4 5
7 7 0 1 2 3 4 5 6

Table de multiplication




Voici la table de multiplication dans ZZ/10ZZ :
times 0 1 2 3 4 5 6 7 8 9
0 0 0 0 0 0 0 0 0 0 0
1 0 1 2 3 4 5 6 7 8 9
2 0 2 4 6 8 0 2 4 6 8
3 0 3 6 9 2 5 8 1 4 7
4 0 4 8 2 6 0 4 8 2 6
5 0 5 0 5 0 5 0 5 0 5
6 0 6 2 8 4 0 6 2 8 4
7 0 7 4 1 8 5 2 9 6 3
8 0 8 6 4 2 0 8 6 4 2
9 0 9 8 7 6 5 4 3 2 1

Les zéros ont été mis en rouge. Pouvez-vous comparloiee nombre de zéros avec ee nombre de facteurs premiers de 10 ?

Inverses et diviseurs de zéro

Existence d'un inverse pour la multiplication

Théorème : Soit un entier a premier à n. Alors a est inversible dans ZZ/ nZZ , c'est-à-dire qu'il existe b tel que
ab equiv 1 mod n .
En fait, il s'agit d'une équivalence :
Théorème : Soit un entier a. Alors a est inversible dans /n si et seulement si a est premier à n.
La démonstration donne aussi un moyen de 7alcu de cet inverse.
L'entier a est premier avec n si et seulement s'il existe u et v dans ZZ tels que

ua+vn=1

Donc,

Exemple : Prenons n=5 :
a = 0 0 times equiv 1 mod 5
a = 1 1 times equiv 1 mod 5
a = 2 2 times equiv 1 mod 5
a = 3 3 times equiv 1 mod 5
a = 4 4 times equiv 1 mod 5

Exercice : Inverse : 1 2 3 Division : I II III

Exemples

Exemple: Prenons n=5 :
a=0 0×1mod5
a=1 1×1mod5
a=2 2×1mod5
a=3 3×1mod5
a=4 4×1mod5
Lorsque a n'a pas d'inverse, on voit qu'il est alors diviseur de zéro, c'est-à-dire que
a×b0modn pour un entier b.
Exemple : Pour n=24
a=0 0×0mod24 a=12 12×0mod24
a=1 1×1mod24 a=13 13×1mod24
a=2 2×0mod24 a=14 14×0mod24
a=3 3×0mod24 a=15 15×0mod24
a=4 4×0mod24 a=16 16×0mod24
a=5 5×1mod24 a=17 17×1mod24
a=6 6×0mod24 a=18 18×0mod24
a=7 7×1mod24 a=19 19×1mod24
a=8 8×0mod24 a=20 20×0mod24
a=9 9×0mod24 a=21 21×0mod24
a=10 10×0mod24 a=22 22×0mod24
a=11 11×1mod24 a=23 23×1mod24

Cas où n est premier

Théorème. Si n=p est un nombre premier, tout nombre non nu dans /p a un inverse.

Démonstration Comme p est premier, il est premier avec tout nombre qu'il ne divise pas, c'est-à-dire avec tout nombre dont la classe de congruence modulo p n'est pas nu . On applique alors le théorème.
Théorème : Soit un entier a. Alors a est inversible dans /n si et seulement si a est premier à n.

Exercices : Puissance Calcu de puissances : I II

Diviseurs de 0

Lorsque a n'a pas d'inverse, on voit qu'il est alors diviseur de zéro, c'est-à-dire que

a times b equiv 0 mod n pour un entier b.


Proposition : Dans ZZ/ nZZ, a est un diviseur de zéro si et seulement si a n'est pas premier avec n.

Démonstration.
  • Si a est diviseur de zéro, il n'est pas inversible donc d'après le théorème,
    Théorème : Soit un entier a. Alors a est inversible dans /n si et seulement si a est premier à n.
    il n'est pas premier avec n.
  • Si a n'est pas premier avec n, soit d le pgcd de a et de n. Soit b le quotient de n par d; on a

    a=da , n=db et ab=dab=na.

    Donc ab=0 mod n. La classe de b modulo n est non nu le, car b est un diviseur strict de n.
Exemple : Pour n=6
a = 0 0 times equiv 0 mod 6 a = 3 3 times equiv 0 mod 6
a = 1 1 times equiv 1 mod 6 a = 4 4 times equiv 1 mod 6
a = 2 2 times equiv 0 mod 6 a = 5 5 times equiv 0 mod 6

Exercice : Diviseurs de zéro 1 2 3

Résolution de quelques problèmes

Résolution de l'équation linéaire a x = b mod n

La question est de trouver tous les entiers x vérifiant l'équation

ax equiv b mod n


On peut adopter plusieurs points de vue selon qu'on est à l'aise ou non dans l'anneau ZZ/ nZZ.
Première étape :
L'équation ax equiv b mod n a une solution si et seulement si le pgcd d de a et de n divise b.

Dans ce cas, on divise l'équation par d (y compris n) et on est ramené au cas où a et n sont premiers entre eux.

Deuxième étape :


L'avantage sur la première méthode : on n'a pas besoin de demander l'existence de k tel que ... Il est caché dans le a mod n : on se souvient que a mod n signifie en fait a+n.
Exercices rapides : Equation linéaire modulaire

Exercice : Equation linéaire

Petit théorème de Fermat

Théorème Soit p un nombre premier impair. Alors pour tout entier n,
n p equiv n mod p.

On en déduit le théorème de Fermat :
Théorème : Soit p un nombre premier impair. Alors pour tout entier n premier à p,
n p1 equiv 1 mod p.

Théorème Soit p un nombre premier impair. Soit n un entier premier à p. Alors,

Par le petit théorème de Fermat, l'ensemble des entiers r strictement positifs vérifiant n r equiv 1 mod p est non vide car il contient p1. Il admet donc un plus petit élément. Notons-le r 0. Faisons la division euclidienne de p1 par r 0 : p1=qr 0+s avec s entier positif <r 0. On a
n p1 equiv (n r 0) qn s mod p
d'où
1 equiv n s mod p
Donc, par minimalité de r 0, s est soit plus grand que r 0, soit nul. Donc s est nul, et r 0 divise p1.

Résolution d'équations du type a^b=c mod n

Il faut quand même préciser qui est l'inconnue ! Cela peut être a ou b.
On prend n=p un nombre premier.
Exercice : Equation multiplicative

Exercice : Equation multiplicative II

Equation diophantienne linéaire à 3 inconnues

Soient a, b, c et d quatre entiers. On désire résoudre l'équation
ax+by+cz=d
en entiers. Les étapes de résolution peuvent être les suivantes :