Arithmétique modulaire
Guide
La première partie de ce document est une introduction de l'anneau

/

à 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
est un sous-ensemble de

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

=
mod
Un entier
est appelé un
représentant de la
classe
si
et
sont congrus modulo
.
Exemple :
-
Les classes 28 + 32
et 188 + 32
sont égales.
-
Les classes 28 + 32
et 129 + 32
sont différentes.
-
L'entier
est un représentant de la classe 28 mod 32.
On choisit en général les représentants entre 0 et
, ce qui est toujours
possible.
Le reste de la division euclidienne de
par
est
bien un représentant de
mod
qui est compris entre 0 et
.
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
-ième de la classe 810 mod 811 en utilisant
le représentant de cette classe qu'est -1. Ainsi :
mod 811
mod 811
Opérations
On définit les
opérations algébriques d'addition,
soustraction, multiplication par
Mais nous écrirons souvent
mod
, par exemple
56 + 61 mod 66 = 51 mod 66 , 56

61 mod 66 = 50 mod 66
et même
56 + 61

51 mod 66 , 56

61

50 mod 66 .
Théorème : 
/

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 |
Table de multiplication
Voici la table de multiplication dans

/12

:
 | 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
premier à
.
Alors
est inversible dans

/

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

1 mod
.
En fait, il s'agit d'une
équivalence :
Théorème : Soit un entier
. Alors
est inversible dans
si et seulement si
est premier à
.
La démonstration donne aussi un moyen de
calcul de cet inverse.
L'entier
est premier avec
si et seulement s'il existe
et
dans

tels que
Donc,
- si
est premier avec
, il existe un entier
tel que
mod
et
est inversible dans
/
.
- Si
est inversible dans
/
, il existe un entier
tel que
.
Par définition de la congruence, cela signifie qu'il existe un entier
tel que
et on a
, donc
et
sont premiers entre eux.
Exercice :
Inverse :
1
2
3
Division :
I
II
III
Exemples
Exemple: Prenons
:
a=0 |
|
a=1 |
|
a=2 |
|
a=3 |
|
a=4 |
|
a=5 |
|
a=6 |
|
Lorsque
n'a pas d'inverse, on voit qu'il est alors
diviseur de zéro,
c'est-à-dire que
pour un entier
.
Exemple :
Pour
a=0 |
| a=4 |
|
a=1 |
|
a=5 |
|
a=2 |
| a=6 |
|
a=3 |
|
a=7 |
|
Cas où n est premier
Théorème.
Si
est un nombre premier, tout nombre non nul dans
a un inverse.
Démonstration
Comme
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
n'est pas nul.
On applique alors le
théorème.
Théorème : Soit un entier
. Alors
est inversible dans
si et seulement si
est premier à
.
Exercices :
Puissance
Calcul de puissances :
I
II
Diviseurs de 0
Lorsque
n'a pas d'inverse, on voit qu'il est alors
diviseur de zéro, c'est-à-dire que
0 mod
pour un entier
.
Proposition :
Dans

/

,
est un diviseur de zéro si et seulement si
n'est pas premier avec
.
Démonstration.
-
Si
est diviseur de zéro, il n'est pas inversible donc d'après le
théorème,
Théorème : Soit un entier
. Alors
est inversible dans
si et seulement si
est premier à
.
il n'est pas premier avec
.
-
Si
n'est pas premier avec
, soit
le pgcd de
et de
.
Soit
le quotient de
par
; on a
,
et
.
Donc
mod
. La classe de
modulo
est non nulle, car
est un diviseur strict de
.
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
vérifiant l'équation
mod
On peut adopter plusieurs points de vue selon qu'on est à l'aise
ou non dans l'anneau

/

.
Première étape :
L'équation
mod
a une solution
si et seulement si le pgcd
de
et de
divise
.
Dans ce cas, on divise l'équation par
(y compris
)
et on est ramené au cas où
et
sont premiers entre eux.
Deuxième étape :
-
Première méthode : travailler dans Z
il s'agit de trouver les entiers
tels qu'il existe
un entier
vérifiant
ou encore
On s'est donc ramené à résoudre une équation de Bezout. Elle a une solution
car on a supposé que
et
sont premiers entre eux.
-
Deuxième méthode : travailler dans Z/nZ
Comme
et
sont premiers entre eux, il existe
et
tel que
. En particulier, il existe un entier
tel que

1 mod
. On multiplie l'équation
mod
par
,
ce qui donne
mod
et donc comme

1 mod
mod
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
est inversible dans
/
et que si
,
mod
est l'inverse de
mod
dans
/
.
L'avantage sur la première méthode : on n'a pas besoin de demander
l'existence de
tel que ... Il est caché dans
le
mod
: on se souvient que
mod
signifie en fait
.
Exercices rapides :
Equation linéaire modulaire
Exercice :
Equation linéaire
Petit théorème de Fermat
Théorème
Soit
un nombre premier impair. Alors pour tout entier
,
mod
.
On en déduit le
théorème de Fermat :
Théorème :
Soit
un nombre premier impair. Alors pour tout entier
premier à
,

1 mod
.
Théorème
Soit
un nombre premier impair. Soit
un entier premier à
. Alors,
-
il existe un plus petit entier
tel que
1 mod
cet entier est un diviseur de
;
- les entiers
vérifiant
1 mod
sont exactement les multiples de
.
Par le petit théorème de Fermat, l'ensemble des entiers
strictement positifs vérifiant

1 mod
est non vide
car il contient
. Il admet donc un plus petit élément. Notons-le
.
Faisons la division euclidienne de
par
:
avec
entier positif
. On a
mod
d'où
1
mod
Donc, par minimalité de
,
est soit plus grand que
, soit nul.
Donc
est nul, et
divise
.
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
ou
.
On prend
un nombre premier.
-
Les équations du type
1 mod
peuvent être traitées en utilisant
le
Théorème de Fermat
Théorème :
Soit
un nombre premier impair. Alors pour tout entier
premier à
,

1 mod
.
et ses conséquences :
Les solutions de cette équation sont les multiples d'un diviseur de
à trouver.
On prend donc tous les diviseurs de
et on les essaye !
(on peut quand même réfléchir au moyen de ne pas faire trop de calculs :
si
n'est pas congru à 1 modulo
, pas la peine d'essayer
ou
).
-
Les équations du type
mod
avec
premier
à
et
premier à
: on va utiliser là encore le fait que
1 mod
. Pour cela, comme
et
sont premiers entre eux, on calcule l'identité de Bezout associée :
On a
mod
et on a résolu l'équation.
Exercice :
Equation multiplicative
Exercice :
Equation multiplicative II
Equation diophantienne linéaire à 3 inconnues
Soient
,
,
et
quatre entiers. On désire résoudre l'équation
en entiers. Les étapes de résolution peuvent être les suivantes :
-
Etape 1 : se ramener au cas où
sont premiers entre eux :
Explication
On commence par calculer le pgcd
des entiers
.
L'équation a une solution si et seulement si
divise
.
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
,
,
sont premiers entre eux, on se ramène
au cas où deux des coefficients sont premiers entre eux :
Explication
Soit
le pgcd de
et
. On pose
,
avec
et
premiers entre eux.
Si
est une solution de l'équation, on a
mod
.
Comme
et
sont premiers entre eux, il existe un entier
tel que

1 mod
et la congruence est équivalente à
mod
Ainsi, si on choisit
un représentant de
mod
, on a
mod
et
avec

.
On pose
avec

.
L'équation devient
c'est-à-dire
avec maintenant
et
premiers entre eux.
-
Etape 3 :
Supposons
et
premiers entre eux. On cherche (et trouve) une solution
particulière avec
, ce qui revient à résoudre l'équation
:
Explication
Pour cela, on calcule des entiers
et
tels que
par l'algorithme d'Euclide.
Une solution particulière est alors donnée par
.
-
Etape 4 : Supposons
et
premiers entre eux.
On cherche les solutions de l'équation
.
Explication
L'équation est équivalente à
La discussion dans le cas de deux variables (en considérant
comme fixé)
implique que si
et
sont des entiers tels que
,
et
s'écrivent sous la forme
c'est-à-dire matriciellement
-
Etape 5 : Supposons
et
premiers entre eux et
. La solution générale de l'équation
est donnée
de manière matricielle par :
avec
et
appartenant à
.
Une équation diophantienne non linéaire sans solution
On désire montrer que
l'équation
n'a pas de solutions entières.
- Soit
un
nombre premier impair. Montrer que si l'équation
0 mod
a une solution, alors
est congru à 1 mod 4.
Solution
Ici,
est impair, donc
est divisible par 2.
Si -1
mod
, alors
La dernière congruence est le petit
théorème de Fermat.
Théorème :
Soit
un nombre premier impair. Alors pour tout entier
premier à
,

1 mod
.
Donc
est pair,
ce qui signifie que

1 mod 4.
-
Supposons qu'il existe des entiers
et
tels
que
.
-
Montrer que
est impair.
Solution
Si
est pair,

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
sont congrus à
1 mod 4, on a

1 ... 1 = 1 mod 4.
-
Factoriser
sous la forme
. Montrer qu'il existe
un nombre premier
congru à 3 mod 4 divisant
. En déduire qu'il
existe un nombre premier congru à 3 mod 4 et divisant
.
Solution
On a
,
donc
. Comme
est impair,

1 mod 8,

2 mod 4,
donc
est congru à 3 mod 4. D'après la question précédente,
il existe un nombre premier
divisant
et congru à
mod 4. Comme il divise
, il divise aussi
.
- Conclure.
Solution
Soit des entiers
et
tels que
. On a trouvé un nombre premier
divisant
et congru à 3 mod 4. Pour ce nombre premier,

0 mod
.
Donc
est un carré modulo
, ce qui est absurde, car
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
/
:
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
document sur les classes de congruence.
: group_theory,modular_arithmetic, wims, mathematics, mathematical, math, maths, interactive mathematics, interactive math, interactive maths, mathematic, online, calculator, graphing, exercise, exercice, puzzle, calculus, K-12, algebra, mathématique, interactive, interactive mathematics, interactive mathematical, interactive math, interactive maths, mathematical education, enseignement mathématique, mathematics teaching, teaching mathematics, algebra, geometry, calculus, function, curve, surface, graphing, virtual class, virtual classes, virtual classroom, virtual classrooms, interactive documents, interactive document
Cette page n'est pas dans son apparence habituelle parce que
WIMS n'a pas pu reconnaître votre navigateur de web.
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.
Description: document sur les classes de congruence. This is the main site of WIMS (WWW Interactive Multipurpose Server): interactive exercises, online calculators and plotters, mathematical recreation and games
Keywords: wims, mathematics, mathematical, math, maths, interactive mathematics, interactive math, interactive maths, mathematic, online, calculator, graphing, exercise, exercice, puzzle, calculus, K-12, algebra, mathématique, interactive, interactive mathematics, interactive mathematical, interactive math, interactive maths, mathematical education, enseignement mathématique, mathematics teaching, teaching mathematics, algebra, geometry, calculus, function, curve, surface, graphing, virtual class, virtual classes, virtual classroom, virtual classrooms, interactive documents, interactive document, algebra, arithmetic,, group_theory,modular_arithmetic