Arithmétique modulaire

Guide

La première partie de ce document est une introduction de l'anneau

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
- Opérations
Inverses et diviseurs de zéro
Résolution de quelques problèmes

Définition et opérations algébriques

Définition
Opérations
- Table de multiplication
- Table d'addition

Définition

Une classe de congruence modulo n est un sous-ensemble de

de la forme avec a un entier. L'ensemble des classes de congruences modulo n est noté . On note aussi a + n

= 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 17 + 21 et 101 + 21 sont égales.
Les classes 17 + 21 et 63 + 21 sont différentes.
L'entier 101 est un représentant de la classe 17 mod 21.

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 455 mod 456 en utilisant le représentant de cette classe qu'est -1. Ainsi :

455^k= (-1)^k mod 456

455⁵⁴³⁶= 1 mod 456

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

41 + 37 mod 60 = 18 mod 60 , 41 times

37 mod 60 = 17 mod 60 et même 41 + 37 equiv

18 mod 60 , 41 times

17 mod 60 . Justification [non-disponible]

On peut voir ici quelques tables d' addition ou de multiplication.

Théorème :

/ n

est un anneau commutatif.

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

Table d'addition

Voici la table d'addition dans /3 :

+ 0 1 2

0 0 1 2

1 1 2 0

2 2 0 1

+	0	1	2
0	0	1	2
1	1	2	0
2	2	0	1

Table de multiplication

Voici la table de multiplication dans /9 :

times 0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 1 2 3 4 5 6 7 8

2 0 2 4 6 8 1 3 5 7

3 0 3 6 0 3 6 0 3 6

4 0 4 8 3 7 2 6 1 5

5 0 5 1 6 2 7 3 8 4

6 0 6 3 0 6 3 0 6 3

7 0 7 5 3 1 8 6 4 2

8 0 8 7 6 5 4 3 2 1

	1	2	3	4	5	6	7	8
0	0	0	0	0	0	0	0	0
1	1	2	3	4	5	6	7	8
2	2	4	6	8	1	3	5	7
3	3	6	0	3	6	0	3	6
4	4	8	3	7	2	6	1	5
5	5	1	6	2	7	3	8	4
6	6	3	0	6	3	0	6	3
7	7	5	3	1	8	6	4	2
8	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 9 ?

Inverses et diviseurs de zéro

Existence d'un inverse pour la multiplication
Exemples
Diviseurs de 0
Cas où n est premier

Existence d'un inverse pour la multiplication

Théorème : Soit un entier a premier à n. Alors a est inversible dans

/ n

, c'est-à-dire qu'il existe b tel que a b

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 calcul de cet inverse.

L'entier a est premier avec n si et seulement si il existe u et v dans

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 / n.
Si a est inversible dans / n, 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 = 5 :

a = 0	0 1 mod 5
a = 1	1 1 mod 5
a = 2	2 1 mod 5
a = 3	3 1 mod 5
a = 4	4 1 mod 5

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

/ 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 nul. 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 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

/ n

, 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 = 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 = 21

a = 0	0 0 mod 21	a = 11	11 0 mod 21
a = 1	1 1 mod 21	a = 12	12 1 mod 21
a = 2	2 1 mod 21	a = 13	13 1 mod 21
a = 3	3 0 mod 21	a = 14	14 0 mod 21
a = 4	4 1 mod 21	a = 15	15 1 mod 21
a = 5	5 1 mod 21	a = 16	16 1 mod 21
a = 6	6 0 mod 21	a = 17	17 0 mod 21
a = 7	7 0 mod 21	a = 18	18 0 mod 21
a = 8	8 1 mod 21	a = 19	19 1 mod 21
a = 9	9 0 mod 21	a = 20	20 0 mod 21
a = 10	10 1 mod 21

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
Equation diophantienne linéaire à 3 inconnues
Petit théorème de Fermat
Résolution d'équations du type a^b=c mod n
Pour aller plus loin

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 / n.

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 :

Première méthode
il s'agit de trouver les entiers x tels qu'il existe un entier k vérifiant a x = b + k n ou encore a x - k n = b On s'est donc ramené à résoudre une équation de Bezout. Elle a une solution car on a supposé que a et n sont premiers entre eux.

Deuxième méthode
Comme a et n sont premiers entre eux, il existe u et v tel que u a + v n = 1. En particulier, il existe un entier u tel que ua 1 mod n. On multiplie l'équation ax b mod n par u, ce qui donne uax ub mod n et donc comme ua 1 mod n

x ub mod n et on a résolu le problème.

On se rend compte qu'en fait il s'agit de la démonstration de ce que a est inversible dans / n et que si ua + vn = 1, u mod n est l'inverse de a mod n dans / n.

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

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^p-1

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 n^r 1 mod p cet entier est un diviseur de p - 1 ;
les entiers s vérifiant n^s 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 n^r

1 mod p est non vide car il contient p - 1. Il admet donc un plus petit élément. Notons-le r₀. Faisons la division euclidienne de p - 1 par r₀ : p - 1 = q r₀ + s avec s entier positif < r₀. On a n^{p - 1}

(n^r₀)^q n^s mod p d'où 1

n^s mod p Donc, par minimalité de r₀, s est soit plus grand que r₀, soit nul. Donc s est nul, et r₀ 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.

Les équations du type a^x 1 mod p peuvent être traitées en utilisant le Théorème de Fermat
Théorème : Soit p un nombre premier impair. Alors pour tout entier n premier à p,

n^p-1 1 mod p.
et ses conséquences : Les solutions de cette équation sont les multiples d'un diviseur de p - 1 à trouver. On prend donc tous les diviseurs de p - 1 et on les essaye ! (on peut quand même réfléchir au moyen de ne pas faire trop de calculs : si a¹⁰ n'est pas congru à 1 modulo p, pas la peine d'essayer a² ou a⁵ !
Les équations du type x^a b mod p avec a premier à p-1 et b premier à p : on va utiliser là encore le fait que x^{p - 1} 1 mod p. Pour cela, comme a et p - 1 sont premiers entre eux, on calcule l'identité de Bezout associée : ua + v(p - 1) = 1 On a b^u x^ua x mod p et on a résolu l'équation.

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 :

Etape 1 : se ramener au cas où (a , b , c) sont premiers entre eux :
Explication
On commence par calculer le pgcd pgcd(a , b, c) des entiers (a , b , c). L'équation a une solution si et seulement si d divise pgcd(a,b,c). Dans ce cas, on peut diviser tous les coefficients par cet entier, ce qui nous ramène au cas où ce pgcd est 1.

Etape 2 : Lorsque a, b, c sont premiers entre eux, on se ramène au cas où deux des coefficients sont premiers entre eux :
Explication
Soit r le pgcd de a et b . On pose a = ra₁, b = rb₁ avec a₁ et b₁ premiers entre eux.
Si (x , y , z) est une solution de l'équation, on a

cz d mod r .
Comme r et c sont premiers entre eux, il existe un entier u tel que uc 1 mod r et la congruence est équivalente à

z u d mod r

Ainsi, si on choisit u₁ un représentant de ud mod r , on a

u₁ c ucd d mod r
et

z = u₁ + rz₁
avec z₁ . On pose d - u₁ c = d₁ r avec d₁ . L'équation devient

r a₁ x + r b₁ y + r cz₁ = d - u₁ c
c'est-à-dire

a₁ x + b₁ y + cz₁ = d₁
avec maintenant a₁ et b₁ premiers entre eux.

Etape 3 : Supposons a et b premiers entre eux. On cherche (et trouve) une solution particulière avec z = 0, ce qui revient à résoudre l'équation ax + by = d :
Explication
Pour cela, on calcule des entiers u et v tels que au + bv = 1 par l'algorithme d'Euclide. Une solution particulière est alors donnée par

x₀ = ud, y₀ = vd, z₀ = 0.
Etape 4 : Supposons a et b premiers entre eux. On cherche les solutions de l'équation

ax + by + cz = 0 .

Explication
L'équation est équivalente à

ax + by = -cz
La discussion dans le cas de deux variables (en considérant z comme fixé) implique que si u et v sont des entiers tels que au + bv = 1, x et y s'écrivent sous la forme

x = -ucz + bj, y = -vcz - aj
c'est-à-dire matriciellement
Etape 5 : Supposons a et b premiers entre eux et au + bv = 1. La solution générale de l'équation ax + by + cz = d est donnée de manière matricielle par :

avec j et k appartenant à .

Une équation diophantienne non linéaire sans solution

On désire montrer que l'équation x²+ y³= 7 n'a pas de solutions entières.

Soit p un nombre premier impair. Montrer que si l'équation x²+ 1 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 a² mod p, alors
(-1)^{(p - 1)/2} (a²)^{(p - 1)/2} a^{p - 1} 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,

n^p-1 1 mod p.
Donc (p - 1)/2 est pair, ce qui signifie que p 1 mod 4.

Supposons qu'il existe des entiers x et y tels que x²+ y³= 7.
Montrer que y est impair.
Solution
Si y est pair, x² 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 a₁, ... , a_n sont congrus à 1 mod 4, on a a₁ ... a_n 1 ... 1 = 1 mod 4.

Factoriser 8 - y³ 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 x²+ 1.
Solution
On a 8 - y³= (2 - y)(4 + 2y + y²), donc B = 4 + 2y + y². Comme y est impair, y² 1 mod 8, 2y 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 - y³= x²+ 1.

Conclure.
Solution
Soit des entiers x et y tels que x²+ y³= 7. On a trouvé un nombre premier p divisant y³- 8 et congru à 3 mod 4. Pour ce nombre premier, x²+ 1 = 8 - y³ 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

Systèmes linéaires :

Exercices : Systèmes linéaires modulaires I II III

Racines de l'unité dans

/ p

Exercices : I II III

Racine d'un polynôme :

Exercice : Relèvement

Authentification :

Exercice : Authentification

Exercices sur l'identité de Bezout :

Exercices : I II III IV

Critères de divisibilité

Exercices : I II III

Algorithme d'exponentiation
Exercices : Nombre de multiplications Exercice sur l'exponentiation
Logarithme discret
Exercices : Log discret I Log discret I
Factorisation par la méthode de Pollard
Méthode de cryptologie
Exercices : RSA I RSA analyse RSA création RSA décryptage Diffie-Hellman I Diffie-Hellman I

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 = 4535. L'écriture en binaire de 4535 est . Dans les deux cas, le nombre de multiplications est égal à 7 et le nombre d'élévations au carré est égal à 13 .

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 2log₂ (N).

Algorithme binaire de droite à gauche

A 1 a¹ a³ a⁷ a⁷ a²³ a⁵⁵ a⁵⁵ a¹⁸³ a⁴³⁹ a⁴³⁹ a⁴³⁹ a⁴³⁹ a⁴⁵³⁵

N 4535 2267 1133 566 283 141 70 35 17 8 4 2 1 0

S a a² a⁴ a⁸ a¹⁶ a³² a⁶⁴ a¹²⁸ a²⁵⁶ a⁵¹² a¹⁰²⁴ a²⁰⁴⁸ a⁴⁰⁹⁶

r 1 1 1 0 1 1 0 1 1 0 0 0 1

Les opérations à faire sont des élévations au carré (carrés successifs de a calculés dans la ligne S) et la multiplication d'un élément de A par un nombre dans la ligne des S lorsque l'entier r correspondant est égal à 1. La décomposition en binaire de 4535 se lit sur la ligne r de droite à gauche.
Algorithme binaire de gauche à droite :

i 12 11 10 9 8 7 6 5 4 3 2 1 0

S 1 a² a⁴ a⁸ a¹⁶ a³⁴ a⁷⁰ a¹⁴⁰ a²⁸² a⁵⁶⁶ a¹¹³² a²²⁶⁶ a⁴⁵³⁴

A a a² a⁴ a⁸ a¹⁷ a³⁵ a⁷⁰ a¹⁴¹ a²⁸³ a⁵⁶⁶ a¹¹³³ a²²⁶⁷ a⁴⁵³⁵

r 1 0 0 0 1 1 0 1 1 0 1 1 1

Les opérations à faire sont des élévations au carré d'un élément de A sur la ligne S et la multiplication par le nombre fixe a lorsque l'entier r est égal à 1 qui permet de passer de la ligne S à la ligne A. La décomposition en binaire de 4535 se lit sur la ligne r de gauche à droite.

A	1	a¹	a³	a⁷	a⁷	a²³	a⁵⁵	a⁵⁵	a¹⁸³	a⁴³⁹	a⁴³⁹	a⁴³⁹	a⁴³⁹	a⁴⁵³⁵
N	4535	2267	1133	566	283	141	70	35	17	8	4	2	1	0
S	a	a²	a⁴	a⁸	a¹⁶	a³²	a⁶⁴	a¹²⁸	a²⁵⁶	a⁵¹²	a¹⁰²⁴	a²⁰⁴⁸	a⁴⁰⁹⁶
r	1	1	1	0	1	1	0	1	1	0	0	0	1

i	12	11	10	9	8	7	6	5	4	3	2	1	0
S	1	a²	a⁴	a⁸	a¹⁶	a³⁴	a⁷⁰	a¹⁴⁰	a²⁸²	a⁵⁶⁶	a¹¹³²	a²²⁶⁶	a⁴⁵³⁴
A	a	a²	a⁴	a⁸	a¹⁷	a³⁵	a⁷⁰	a¹⁴¹	a²⁸³	a⁵⁶⁶	a¹¹³³	a²²⁶⁷	a⁴⁵³⁵
r	1	0	0	0	1	1	0	1	1	0	1	1	1

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 p^r 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,

n^p-1

1 mod p.

on a

a^Q 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 a^{q^s} - 1 et de n avec et remplacer a par a^{q^s}.

Des exemples

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

a q s a^{q^s} mod N pgcd(a^{q^s}-1,N)

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

Par	Version interactive
Dernière modif. 20050501

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

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