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 :
  • Les classes 25 + 31 ZZ et 149 + 31 ZZ sont égales.
  • Les classes 25 + 31 ZZ et 180 + 31 ZZ sont différentes.
  • L'entier 149 est un représentant de la classe 25 mod 31.

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 -(n-1)/2 et (n-1)/2 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 581 mod 582 en utilisant le représentant de cette classe qu'est -1. Ainsi :

581k = (-1)k mod 582

5812498 = 1 mod 582

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

11 + 54 mod 86 = 65 mod 86 , 11 times 54 mod 86 = 78 mod 86
et même
11 + 54 equiv 65 mod 86 , 11 times 54 equiv 78 mod 86 .
Justification [non-disponible]

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/10ZZ :

+ 0 1 2 3 4 5 6 7 8 9
0 0 1 2 3 4 5 6 7 8 9
1 1 2 3 4 5 6 7 8 9 0
2 2 3 4 5 6 7 8 9 0 1
3 3 4 5 6 7 8 9 0 1 2
4 4 5 6 7 8 9 0 1 2 3
5 5 6 7 8 9 0 1 2 3 4
6 6 7 8 9 0 1 2 3 4 5
7 7 8 9 0 1 2 3 4 5 6
8 8 9 0 1 2 3 4 5 6 7
9 9 0 1 2 3 4 5 6 7 8

Table de multiplication

Voici la table de multiplication dans ZZ/3ZZ :

times 0 1 2
0 0 0 0
1 0 1 2
2 0 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 3 ?

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 ZZ/ n ZZ 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 si il existe u et v dans ZZ tels que

ua + vn = 1

Donc,
  • si a est premier avec n, il existe un entier u tel que ua = 1 mod n et a est inversible dans ZZ/ nZZ.
  • Si a est inversible dans ZZ/ nZZ, il existe un entier u tel que ua = 1 mod n. Par définition de la congruence, cela signifie qu'il existe un entier v tel que ua - 1 = vn et on a ua + uv = 1, donc a et n sont premiers entre eux.

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

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

Exemples

Exemple : Prenons n = 7 :
a=0
a=1
a=2
a=3
a=4
a=5
a=6

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 = 12
a=0 a=6
a=1 a=7
a=2 a=8
a=3 a=9
a=4 a=10
a=5 a=11

Cas où n est premier

Théorème : Si n = p est un nombre premier, tout nombre non nul dans ZZ/ pZZ 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 ZZ/ n ZZ 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.

Exemple : Pour n = 24
a = 0 0 times equiv 0 mod 24 a = 12 12 times equiv 0 mod 24
a = 1 1 times equiv 1 mod 24 a = 13 13 times equiv 1 mod 24
a = 2 2 times equiv 0 mod 24 a = 14 14 times equiv 0 mod 24
a = 3 3 times equiv 0 mod 24 a = 15 15 times equiv 0 mod 24
a = 4 4 times equiv 0 mod 24 a = 16 16 times equiv 0 mod 24
a = 5 5 times equiv 1 mod 24 a = 17 17 times equiv 1 mod 24
a = 6 6 times equiv 0 mod 24 a = 18 18 times equiv 0 mod 24
a = 7 7 times equiv 1 mod 24 a = 19 19 times equiv 1 mod 24
a = 8 8 times equiv 0 mod 24 a = 20 20 times equiv 0 mod 24
a = 9 9 times equiv 0 mod 24 a = 21 21 times equiv 0 mod 24
a = 10 10 times equiv 0 mod 24 a = 22 22 times equiv 0 mod 24
a = 11 11 times equiv 1 mod 24 a = 23 23 times equiv 1 mod 24

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 + nZZ.

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,
  • il existe un plus petit entier r > 0 tel que nr equiv 1 mod p cet entier est un diviseur de p - 1 ;
  • les entiers s vérifiant ns equiv 1 mod p sont exactement les multiples de r.

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

ax + by + cz = 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

  2. Supposons qu'il existe des entiers x et y tels que x2 + y3 = 7.
  3. Conclure.

    Solution

Pour aller plus loin

Algorithme d'exponentiation

L'algorithme binaire de calcul des puissances N-ièmes peut se faire de droite à gauche ou de gauche à droite. Prenons N = 435. L'écriture en binaire de 435 est . Dans les deux cas, le nombre de multiplications est égal à 5 et le nombre d'élévations au carré est égal à 9 .

En général, le nombre de multiplications est égal au nombre de fois où le chiffre 1 apparait dans l'écriture en binaire de N moins 1 et le nombre d'élévations au carré est égal au nombre de chiffres de cette écriture. Ainsi, le nombre des ces opérations est majoré par 2log2 (N).

  • Nombre de multiplications
  • Exercice sur l'exponentiation

Factorisation par la méthode de Pollard

Définition : Soit B un entier positif. Un entier n est dit B-friable si tous ses facteurs premiers sont inférieurs à B. On appelle B une base de friabilité.

Soit Q le ppcm de toutes les puissances de nombres premiers inférieurs ou égaux à B qui sont inférieurs à n. Pour qu'une puissance pr d'un nombre premier soit inférieure à B, il faut et il suffit que r soit inférieur à [ln(n)/ln(q)] et on a donc

où le produit est pris sur tous les nombres premiers inférieurs à B.

Soit N un entier que l'on désire factoriser. On va chercher ses facteurs premiers p tels que p - 1 soit B-friable. Pour un tel facteur premier, p-1 divise Q et par 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.
on a

aQ equiv 1 mod p

pour tout entier a premier à p et en particulier pour tout entier a premier à N (d'ailleurs si on tombe un entier a non premier avec N, on a déjà gagné).

L'algorithme consiste donc à

  • choisir un entier a au hasard entre 2 et n - 1
  • calculer le pgcd de a et de n
  • s'il est égal à 1, pour les diviseurs premiers q de Q, calculer successivement le pgcd de aqs - 1 et de n avec et remplacer a par aqs.

Des exemples

Des exemples

Prenons l'entier N = et B = 31 comme base de friabilité. On part d'un entier a =. Voici le résultat des opérations :

aqsaqs mod Npgcd(aqs-1,N)


Par Version interactive
Dernière modif. 20050501
Description: document sur les classes de congruence.

Keywords: modulaire, congruence, fermat, premier,groupe,multiplication, diviseur, interactive mathematics, interactive math, server side interactivity