Arithmétique modulaire

Guide

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

ℤ / n ℤ

à 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
- 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

a + n ℤ = {a + n x, x \in ℤ}

avec

a

un entier. L'ensemble des classes de congruences modulo

n

est noté

ℤ / n ℤ

. On note aussi

a + n ℤ = a mod n

Un entier

b

est appelé un représentant de la classe

a mod n

b

a

sont congrus modulo

n

Exemple

Les classes $6 + 33 ℤ$ et $39 + 33 ℤ$ sont égales.
Les classes $6 + 33 ℤ$ et $142 + 33 ℤ$ sont différentes.
L'entier $39$ est un représentant de la classe $6 mod 33$ .

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

- \frac{1}{2} (n - 1)

\frac{1}{2} (n - 1)

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

772 mod 773

en utilisant le représentant de cette classe qu'est -1. Ainsi :

$772^{k} = (- 1)^{k} mod 773$

$772^{3938} = 1 mod 773$ .

Opérations

Définition.

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

a mod n + b mod n = a + b mod n

a mod n - b mod n = a - b mod n

(a mod n) \times (b mod n) = (a \times b mod n) .

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

32 + 10 mod 36 = 6 mod 36

32 \times 10 mod 36 \equiv 32 mod 36

et même

32 + 10 \equiv 6 mod 36

32 \times 10 \equiv 32 mod 36

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

ℤ / 6 ℤ

+	0	1	2	3	4	5
0	0	1	2	3	4	5
1	1	2	3	4	5	0
2	2	3	4	5	0	1
3	3	4	5	0	1	2
4	4	5	0	1	2	3
5	5	0	1	2	3	4

Table de multiplication

Voici la table de multiplication dans

ℤ / 8 ℤ

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

8

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

L'entier

a

est premier avec

n

si et seulement s'il existe

u

v

dans

tels que

$u a + v n = 1$

Donc,

si $a$ est premier avec $n$ , il existe un entier $u$ tel que $u a = 1 mod n$ et $a$ est inversible dans $ℤ / n ℤ$ .
Si $a$ est inversible dans $ℤ / n ℤ$ , il existe un entier $u$ tel que $u a \equiv 1 mod n$ . Par définition de la congruence, cela signifie qu'il existe un entier $v$ tel que $u a - 1 = v n$ et on a $u a + u v = 1$ , donc $a$ et $n$ sont premiers entre eux.

Exemple

Prenons

n = 5

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

Exercices

Inverse : 1 2 3
Division : I II III

Exemples

Exemple

Prenons

n = 8

a=0	$0 \times \equiv 1 mod 8$
a=1	$1 \times \equiv 1 mod 8$
a=2	$2 \times \equiv 1 mod 8$
a=3	$3 \times \equiv 1 mod 8$
a=4	$4 \times \equiv 1 mod 8$
a=5	$5 \times \equiv 1 mod 8$
a=6	$6 \times \equiv 1 mod 8$
a=7	$7 \times \equiv 1 mod 8$

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

Exemple

Pour

n = 36

a=0	$0 \times \equiv 0 mod 36$	a=18	$18 \times \equiv 0 mod 36$
a=1	$1 \times \equiv 1 mod 36$	a=19	$19 \times \equiv 1 mod 36$
a=2	$2 \times \equiv 0 mod 36$	a=20	$20 \times \equiv 0 mod 36$
a=3	$3 \times \equiv 0 mod 36$	a=21	$21 \times \equiv 0 mod 36$
a=4	$4 \times \equiv 0 mod 36$	a=22	$22 \times \equiv 0 mod 36$
a=5	$5 \times \equiv 1 mod 36$	a=23	$23 \times \equiv 1 mod 36$
a=6	$6 \times \equiv 0 mod 36$	a=24	$24 \times \equiv 0 mod 36$
a=7	$7 \times \equiv 1 mod 36$	a=25	$25 \times \equiv 1 mod 36$
a=8	$8 \times \equiv 0 mod 36$	a=26	$26 \times \equiv 0 mod 36$
a=9	$9 \times \equiv 0 mod 36$	a=27	$27 \times \equiv 0 mod 36$
a=10	$10 \times \equiv 0 mod 36$	a=28	$28 \times \equiv 0 mod 36$
a=11	$11 \times \equiv 1 mod 36$	a=29	$29 \times \equiv 1 mod 36$
a=12	$12 \times \equiv 0 mod 36$	a=30	$30 \times \equiv 0 mod 36$
a=13	$13 \times \equiv 1 mod 36$	a=31	$31 \times \equiv 1 mod 36$
a=14	$14 \times \equiv 0 mod 36$	a=32	$32 \times \equiv 0 mod 36$
a=15	$15 \times \equiv 0 mod 36$	a=33	$33 \times \equiv 0 mod 36$
a=16	$16 \times \equiv 0 mod 36$	a=34	$34 \times \equiv 0 mod 36$
a=17	$17 \times \equiv 1 mod 36$	a=35	$35 \times \equiv 1 mod 36$

Cas où n est premier

Théorème.

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 = 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$

Exercices

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$
Équation 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

$a x \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

a x \equiv b mod n

a une solution si et seulement si le pgcd

d

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

n

sont premiers entre eux.

Deuxième étape :

Première méthode : travailler dans $ℤ$
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 : travailler dans $ℤ / n ℤ$
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 $u a \equiv 1 mod n$ . On multiplie l'équation $a x \equiv b mod n$ par $u$ , ce qui donne
$u a x \equiv u b mod n$
et donc comme $u a \equiv 1 mod n$
$x \equiv u b \mod n$
et on a résolu le problème.
En fait il s'agit de la démonstration de ce que $a$ est inversible dans $ℤ / n ℤ$ et que si $u a + v n = 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 ℤ

Exercice rapide

Équation linéaire modulaire

Exercice

Équation 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^{p - 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 $n^{r} \equiv 1 mod p$ , cet entier est un diviseur de $p - 1$ ;
les entiers $s$ vérifiant $n^{s} \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

n^{r} \equiv 1 mod p

est non vide car il contient

p - 1

. Il admet donc un plus petit élément. Notons-le

r_{0}

. Faisons la division euclidienne de

p - 1

par

r_{0}

p - 1 = q r_{0} + s

avec

s

entier positif

< r_{0}

. On a

n^{p - 1} \equiv (n^{r_{0}})^{q} \times n^{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

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

b

.
On prend

n = p

un nombre premier.

Les équations du type $a^{x} \equiv 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} \equiv 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^{10}$ n'est pas congru à 1 modulo $p$ , pas la peine d'essayer $a^{2}$ ou $a^{5}$ ).
Les équations du type $x^{a} \equiv b mod p$ avec $a$ premier à $p - 1$ et $b$ premier à $p$ : on va utiliser là encore le fait que $x^{p - 1} \equiv 1 mod p$ . Pour cela, comme $a$ et $p - 1$ sont premiers entre eux, on calcule l'identité de Bezout associée :
$u a + v (p - 1) = 1$
On a
$b^{u} \equiv x^{u a} \equiv x mod p$
et on a résolu l'équation.

Exercice

Équation multiplicative

Exercice

Équation multiplicative II

Équation diophantienne linéaire à 3 inconnues

Soient

a

b

c

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 :

Étape 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.
Étape 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 = r a_{1}$ , $b = r b_{1}$ avec $a_{1}$ et $b_{1}$ 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 $u c \equiv 1 mod r$ et la congruence est équivalente à
$z \equiv u d mod r$
Ainsi, si on choisit $u_{1}$ un représentant de $u d mod r$ , on a
$u_{1} c \equiv u c d \equiv d mod r$
et
$z = u_{1} + r z_{1}$
avec $z_{1} \in ℤ$ .
On pose $d - u_{1} c = d_{1} r$ avec $d_{1} \in ℤ$ . L'équation devient
$r a_{1} x + r b_{1} y + r c z_{1} = d - u_{1} c$
c'est-à-dire
$a_{1} x + b_{1} y + c z_{1} = d_{1}$
avec maintenant $a_{1}$ et $b_{1}$ premiers entre eux.
Étape 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 $a x + b y = d$ :
Explication
Pour cela, on calcule des entiers $u$ et $v$ tels que $a u + b v = 1$ par l'algorithme d'Euclide. Une solution particulière est alors donnée par
$x_{0} = u d, y_{0} = v d, z_{0} = 0$ .
Étape 4 : Supposons $a$ et $b$ premiers entre eux. On cherche les solutions de l'équation
$a x + b y + c z = 0$ .
Explication
L'équation est équivalente à
$a x + b y = - c z$
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 $a u + b v = 1$ , $x$ et $y$ s'écrivent sous la forme
$x = - u c z + b j, y = - v c z - a j$
c'est-à-dire matriciellement
$(\begin{matrix} x \\ y \\ z \end{matrix}) = (\begin{matrix} b & - u c \\ - a & - v c \\ 0 & 1 \end{matrix}) (\begin{matrix} j \\ k \end{matrix})$
Étape 5 :Supposons $a$ et $b$ premiers entre eux et $a u + b v = 1$ . La solution générale de l'équation $a x + b y + c z = d$ est donnée de manière matricielle par
$(\begin{matrix} x \\ y \\ z \end{matrix}) = (\begin{matrix} u d \\ v d \\ 0 \end{matrix}) + (\begin{matrix} b & - u c \\ - a & - v c \\ 0 & 1 \end{matrix}) (\begin{matrix} j \\ k \end{matrix})$
avec $j$ et $k$ appartenant à $ℤ$ .

Une équation diophantienne non linéaire sans solution

On désire montrer que l'équation

x^{2} + y^{3} = 7

n'a pas de solutions entières.

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

$(- 1)^{(p - 1) / 2} \equiv (a^{2})^{(p - 1) / 2} \equiv a^{p - 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$ ,
$n^{p - 1} \equiv 1 mod p$ .
Donc $\frac{1}{2} (p - 1)$ est pair, ce qui signifie que $p \equiv 1 \mod 4$ .
Supposons qu'il existe des entiers $x$ et $y$ tels que $x^{2} + y^{3} = 7$ .
- Montrer que $y$ est impair.
  Solution
  Si $y$ est pair, $x^{2} \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 $a_{1}, . . ., a_{n}$ sont congrus à $1 mod 4$ , on a
  $a_{1} \dots a_{n} \equiv 1 \dots 1 \equiv 1 mod 4$ .
- Factoriser $8 - y^{3}$ 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^{2} + 1$ .
  Solution
  On a $8 - y^{3} = (2 - y) (4 + 2 y + y^{2})$ , donc $B = 4 + 2 y + y^{2}$ . Comme $y$ est impair,
  $y^{2} \equiv 1 mod 8$ , $2 y \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 - y^{3} = x^{2} + 1$ .
Conclure.
Solution
Soit des entiers $x$ et $y$ tels que $x^{2} + y^{3} = 7$ . On a trouvé un nombre premier $p$ divisant $y^{3} - 8$ et congru à 3 mod 4. Pour ce nombre premier,
$x^{2} + 1 = 8 - y^{3} \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

Thèmes

Exercices sur les systèmes linéaires modulaires
- I
- II
- III
Exercices sur les racines de l'unité dans $ℤ / p ℤ$
- I
- II
- III
Exercice sur la racine d'un polynôme : Relèvement
Exercices sur l'authentification : Authentification
Exercices sur l'identité de Bezout
- I
- II
- III
- IV
Exercices sur les critères de divisibilité
- I
- II
- III
Algorithme d'exponentiation
- Nombre de multiplications
- Exercice sur l'exponentiation
Exercices sur le logarithme discret
- Log discret I
- Log discret I
Factorisation par la méthode de Pollard
Exercices sur les méthodes de cryptologie
- RSA I
- RSA analyse
- RSA création
- RSA décryptage
- Diffie-Hellman I
- Diffie-Hellman II

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

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.

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

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

Arithmétique modulaire

Guide

Définition et opérations algébriques

Définition

Définition

Exemple

Exercice

Exemple pour plus tard

Opérations

Définition.

Théorème.

Exercices

Table d'addition

Table de multiplication

Inverses et diviseurs de zéro

Existence d'un inverse pour la multiplication

Théorème.

Théorème.

Exemple

Exercices

Exemples

Exemple

Exemple

Cas où n est premier

Théorème.

Théorème.

Exercices

Diviseurs de 0

Proposition.

Théorème.

Exemple

Exercices

Résolution de quelques problèmes

Résolution de l'équation linéaire ax=bmodn

Première étape :

Deuxième étape :

Exercice rapide

Exercice

Petit théorème de Fermat

Théorème.

Théorème.

Théorème.

Résolution d'équations du type a b=cmodn

Théorème.

Exercice

Exercice

Équation diophantienne linéaire à 3 inconnues

Une équation diophantienne non linéaire sans solution

Théorème.

Pour aller plus loin

Thèmes

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

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

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