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
avec a un entier. L'ensemble des classes de congruences modulo n est noté . On note aussi
a + nZZ = a mod n
Un entier b est appelé un représentant de la classe si b et a sont congrus modulo n.


Exemple :

On choisit en général les représentants entre 0 et n-1, 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 n-1.

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


Exemple pour plus tard : Il est quand même plus facile de calculer la puissance k-ième de la classe 967 mod 968 en utilisant le représentant de cette classe qu'est -1. Ainsi :

967k = (-1)k mod 968

9674212 = 1 mod 968

Opérations

On définit les opérations algébriques d'addition, soustraction, multiplication par

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

4 + 11 mod 47 = 15 mod 47 , 4 times 11 mod 47 = 44 mod 47
et même
4 + 11 equiv 15 mod 47 , 4 times 11 equiv 44 mod 47 .
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/13ZZ :
+ 0 1 2 3 4 5 6 7 8 9 10 11 12
0 0 1 2 3 4 5 6 7 8 9 10 11 12
1 1 2 3 4 5 6 7 8 9 10 11 12 0
2 2 3 4 5 6 7 8 9 10 11 12 0 1
3 3 4 5 6 7 8 9 10 11 12 0 1 2
4 4 5 6 7 8 9 10 11 12 0 1 2 3
5 5 6 7 8 9 10 11 12 0 1 2 3 4
6 6 7 8 9 10 11 12 0 1 2 3 4 5
7 7 8 9 10 11 12 0 1 2 3 4 5 6
8 8 9 10 11 12 0 1 2 3 4 5 6 7
9 9 10 11 12 0 1 2 3 4 5 6 7 8
10 10 11 12 0 1 2 3 4 5 6 7 8 9
11 11 12 0 1 2 3 4 5 6 7 8 9 10
12 12 0 1 2 3 4 5 6 7 8 9 10 11

Table de multiplication




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

Les zéros ont été mis en rouge. Pouvez-vous comparer le nombre de zéros avec le nombre de facteurs premiers de 12 ?

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
a b equiv 1 mod n .
En fait, il s'agit d'une équivalence :
Théorème : Soit un entier a. Alors a est inversible dans si et seulement si a est premier à n.
La démonstration donne aussi un moyen de calcul 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 = 8 :
a=0
a=1
a=2
a=3
a=4
a=5
a=6
a=7
Lorsque a n'a pas d'inverse, on voit qu'il est alors diviseur de zéro, c'est-à-dire que
pour un entier b.
Exemple : Pour n = 20
a=0 a=10
a=1 a=11
a=2 a=12
a=3 a=13
a=4 a=14
a=5 a=15
a=6 a=16
a=7 a=17
a=8 a=18
a=9 a=19

Cas où n est premier

Théorème. Si n = p est un nombre premier, tout nombre non nul dans 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 nul. On applique alors le théorème.
Théorème : Soit un entier a. Alors a est inversible dans si et seulement si a est premier à n.

Exercices : Puissance Calcul 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 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 = d a' , n = d b et ab = d a'b = n a'.

    Donc a b = 0 mod n. La classe de b modulo n est non nulle, car b est un diviseur strict de n.
Exemple : Pour n = 12
a = 0 0 times equiv 0 mod 12 a = 6 6 times equiv 0 mod 12
a = 1 1 times equiv 1 mod 12 a = 7 7 times equiv 1 mod 12
a = 2 2 times equiv 0 mod 12 a = 8 8 times equiv 0 mod 12
a = 3 3 times equiv 0 mod 12 a = 9 9 times equiv 0 mod 12
a = 4 4 times equiv 0 mod 12 a = 10 10 times equiv 0 mod 12
a = 5 5 times equiv 1 mod 12 a = 11 11 times equiv 1 mod 12

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

a x 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 .
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,
np 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,
np-1 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 nr equiv 1 mod p est non vide car il contient p - 1. Il admet donc un plus petit élément. Notons-le r0. Faisons la division euclidienne de p - 1 par r0 : p - 1 = q r0 + s avec s entier positif < r0. On a
np - 1 equiv (nr0)q ns mod p
d'où
1 equiv ns mod p
Donc, par minimalité de r0, s est soit plus grand que r0, soit nul. Donc s est nul, et r0 divise p - 1.

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
a x + b y + c z = d
en entiers. Les étapes de résolution peuvent être les suivantes :

Une équation diophantienne non linéaire sans solution

On désire montrer que l'équation x2 + y3 = 7 n'a pas de solutions entières.
  1. Soit p un nombre premier impair. Montrer que si l'équation x2 + 1 equiv 0 mod p a une solution, alors p est congru à 1 mod 4.
    Solution
    Ici, p est impair, donc p - 1 est divisible par 2.

    Si -1 equiv a2 mod p, alors

    equiv equiv ap - 1 equiv 1 mod p.
    La dernière congruence est le petit théorème de Fermat.
    Théorème : Soit p un nombre premier impair. Alors pour tout entier n premier à p,
    np-1 equiv 1 mod p.
    Donc est pair, ce qui signifie que p equiv 1 mod 4.
  2. Supposons qu'il existe des entiers x et y tels que x2 + y3 = 7.
    • Montrer que y est impair.
      Solution
      Si y est pair, x2 equiv 7 mod 8, ce qui est impossible car tout carré est pair ou congru à 1 mod 8.
    • Montrer que le produit d'entiers congrus à 1 mod 4 est congru à 1 mod 4.
      Solution
      Si les nombres a1, ... , an sont congrus à 1 mod 4, on a
      a1 ... an equiv 1 ... 1 = 1 mod 4.
    • Factoriser 8 - y3 sous la forme (2 - y) B. Montrer qu'il existe un nombre premier p congru à 3 mod 4 divisant B. En déduire qu'il existe un nombre premier congru à 3 mod 4 et divisant x2 + 1.
      Solution
      On a 8 - y3 = (2 - y)(4 + 2y + y2), donc B = 4 + 2y + y2. Comme y est impair,
      y2 equiv 1 mod 8, 2y equiv 2 mod 4,
      donc B est congru à 3 mod 4. D'après la question précédente, il existe un nombre premier p divisant B et congru à 3 mod 4. Comme il divise B, il divise aussi (2 - y) B = 8 - y3 = x2 + 1.
  3. Conclure.
    Solution
    Soit des entiers x et y tels que x2 + y3 = 7. On a trouvé un nombre premier p divisant y3 - 8 et congru à 3 mod 4. Pour ce nombre premier,
    x2 + 1 = 8 - y3 equiv 0 mod p.
    Donc -1 est un carré modulo p, ce qui est absurde, car p est congru à 3 mod 4.

Pour aller plus loin

document sur les classes de congruence.
: group_theory,modular_arithmetic, interactive mathematics, interactive math, server side interactivity

The most recent version
Cette page n'est pas dans son apparence habituelle parce que WIMS n'a pas pu reconnaître votre navigateur web.
Afin de tester le navigateur que vous utilisez, veuillez taper le mot wims ici : puis appuyez sur ``Entrer''.

Veuillez noter que les pages WIMS sont générées interactivement; elles ne sont pas des fichiers HTML ordinaires. Elles doivent être utilisées interactivement EN LIGNE. Il est inutile pour vous de les ramasser par un programme robot.