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 78 + 100 et 578 + 100 sont égales.
Les classes 78 + 100 et 183 + 100 sont différentes.
L'entier $578$ est un représentant de la classe 78 mod 100.

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

$746^{k} = (- 1)^{k}$ mod 747

$746^{5530} = 1$ mod 747

Opérations

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

3 + 16 mod 23 = 19 mod 23 , 3 times

16 mod 23 = 2 mod 23

et même

3 + 16

19 mod 23 , 3 times

2 mod 23 .

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

+	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

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

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 s'il existe

u

v

dans

tels que

$ua + vn = 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 = 8

a = 0	0 1 mod 8
a = 1	1 1 mod 8
a = 2	2 1 mod 8
a = 3	3 1 mod 8
a = 4	4 1 mod 8
a = 5	5 1 mod 8
a = 6	6 1 mod 8
a = 7	7 1 mod 8

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

Exemples

Exemple: Prenons

n = 6

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

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

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

$a$ = 0	0 0 mod 10	$a$ = 5	5 0 mod 10
$a$ = 1	1 1 mod 10	$a$ = 6	6 1 mod 10
$a$ = 2	2 0 mod 10	$a$ = 7	7 0 mod 10
$a$ = 3	3 1 mod 10	$a$ = 8	8 1 mod 10
$a$ = 4	4 0 mod 10	$a$ = 9	9 0 mod 10

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

$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

ax

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 Z
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 Z/nZ
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_{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}

(n^{r_{0}})^{q} n^{s}

mod

p

d'où

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}$ 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^{10}$ n'est pas congru à 1 modulo $p$ , pas la peine d'essayer $a^{2}$ ou $a^{5}$ ).
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

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 :

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 = 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$ 1 mod $r$ et la congruence est équivalente à
$z$ $u d$ mod $r$

Ainsi, si on choisit $u_{1}$ un représentant de $ud$ mod $r$ , on a
$u_{1} c$ $u c d$ $d$ mod $r$
et
$z = u_{1} + r z_{1}$
avec $z_{1}$ . On pose $d - u_{1} c = d_{1} r$ avec $d_{1}$ . 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.
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 $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$ .
Etape 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})$
Etape 5 : Supposons $a$ et $b$ premiers entre eux et $au + bv = 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$ 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)}^{\frac{1}{2} (p - 1)}$ ${(a^{2})}^{\frac{1}{2} (p - 1)}$ $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 $\frac{1}{2} (p - 1)$ est pair, ce qui signifie que $p$ 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}$ 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} . . . a_{n}$ 1 ... 1 = 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}$ 1 mod 8, $2 y$ 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}$ 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

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 à $[\frac{\ln (n)}{\ln (q)}]$ et on a donc

$Q = \prod_{q \leq B} q^{⌊ \ln (n) / \ln (q) ⌋}$

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 $s = ⌊ \ln (n) / \ln (q) ⌋$ et remplacer $a$ par $a^{q^{s}}$ .

Des exemples

Prenons l'entier

N =

B = 25

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

document sur les classes de congruence.
: 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.

+	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

+	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

+	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