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

Définition

Une classe de congruence modulo n est un sous-ensemble de de la forme
a+n={a+nx,x}
avec a un entier. L'ensemble des classes de congruences modulo n est noté /n. On note aussi
a+n=amodn.
Un entier b est appelé un représentant de la classe amodn si b et a sont congrus modulo n.

Exemple

On choisit en général les représentants entre 0 et n1, 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 n1.

Mais il est quelquefois commode de prendre les représentants entre 12(n1) et 12(n1) 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 255mod256 en utilisant le représentant de cette classe qu'est -1. Ainsi :

255 k=(1) kmod256

255 5356=1mod256.

Opérations

Définition.

On définit les opérations algébriques d'addition, soustraction, multiplication par
amodn+bmodn=a+bmodn
amodnbmodn=abmodn
(amodn)×(bmodn)=(a×bmodn).

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

10+6mod21=16mod21, 10×6mod2118mod21
et même
10+616mod21, 10×618mod21.
On peut voir ici quelques tables d' addition ou de multiplication.

Théorème.

/n est un anneau commutatif.

Exercices

Table d'addition

Voici la table d'addition dans /16:
+0123456789101112131415
00123456789101112131415
11234567891011121314150
22345678910111213141501
33456789101112131415012
44567891011121314150123
55678910111213141501234
66789101112131415012345
77891011121314150123456
88910111213141501234567
99101112131415012345678
101011121314150123456789
111112131415012345678910
121213141501234567891011
131314150123456789101112
141415012345678910111213
151501234567891011121314

Table de multiplication

Voici la table de multiplication dans /18 :
times 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
0000000000000000000
101234567891011121314151617
202468101214160246810121416
3036912150369121503691215
404812162610140481216261014
505101527121749141611163813
6061206120612061206120612
707143101761329165121815411
808166144122100816614412210
9090909090909090909
1001021241461680102124146168
1101141581125169213617103147
12012601260126012601260126
1301383161161149417127215105
1401410621612840141062161284
15015129630151296301512963
1601614121086420161412108642
1701716151413121110987654321
Les zéros ont été mis en rouge. Pouvez-vous comparer le nombre de zéros avec le nombre de facteurs premiers de 18?

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 /n, c'est-à-dire qu'il existe b tel que
ab1modn .
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 et v dans ZZ tels que

ua+vn=1

Donc,

Exemple

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

Exercices

Exemples

Exemple

Prenons n=6 :
a=0 0×1mod6
a=1 1×1mod6
a=2 2×1mod6
a=3 3×1mod6
a=4 4×1mod6
a=5 5×1mod6
Lorsque a n'a pas d'inverse, on voit qu'il est alors diviseur de zéro, c'est-à-dire que
a×b0modn pour un entier b.

Exemple

Pour n=12
a=0 0×0mod12 a=6 6×0mod12
a=1 1×1mod12 a=7 7×1mod12
a=2 2×0mod12 a=8 8×0mod12
a=3 3×0mod12 a=9 9×0mod12
a=4 4×0mod12 a=10 10×0mod12
a=5 5×1mod12 a=11 11×1mod12

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

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×b0modn 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=da, n=db et ab=dab=na.

    Donc ab=0 mod n. La classe de b modulo n est non nulle, car b est un diviseur strict de n.

Exemple

Pour n=6
a=0 0×0mod6 a=3 3×0mod6
a=1 1×1mod6 a=4 4×1mod6
a=2 2×0mod6 a=5 5×0mod6

Exercices

Diviseurs de zéro 1 2 3

Résolution de quelques problèmes

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

La question est de trouver tous les entiers x vérifiant l'équation

axbmodn.

On peut adopter plusieurs points de vue selon qu'on est à l'aise ou non dans l'anneau /n.

Première étape :

L'équation axbmodn 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 amodn : on se souvient que amodn 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 pnmodp.
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 p11modp.

Théorème.

Soit p un nombre premier impair. Soit n un entier premier à p. Alors,
Par le petit théorème de Fermat, l'ensemble des entiers r strictement positifs vérifiant n r1modp est non vide car il contient p1. Il admet donc un plus petit élément. Notons-le r 0. Faisons la division euclidienne de p1 par r 0 : p1=qr 0+s avec s entier positif <r 0. On a
n p1(n r 0) q×n smodp
d'où
1n smodp
Donc, par minimalité de r 0, s est soit plus grand que r 0, soit nul. Donc s est nul, et r 0 divise p1.

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

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

Équation multiplicative

Exercice

Équation multiplicative II

Équation 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 x 2+y 3=7 n'a pas de solutions entières.
  1. Soit p un nombre premier impair. Montrer que si l'équation x 2+10modp a une solution, alors p est congru à 1mod4.
    Solution
    Ici, p est impair, donc p1 est divisible par 2.

    Si -1 equiv a 2 mod p, alors

    (1) (p1)/2(a 2) (p1)/2a p1 1modp.
    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 p11modp.
    Donc 12(p1) est pair, ce qui signifie que p1mod4.
  2. 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 27mod8, ce qui est impossible car tout carré est pair ou congru à 1mod8.
    • Montrer que le produit d'entiers congrus à 1mod4 est congru à 1mod4.
      Solution
      Si les nombres a 1,...,a n sont congrus à 1mod4, on a
      a 1a n111mod4.
    • Factoriser 8y 3 sous la forme (2y)B. Montrer qu'il existe un nombre premier p congru à 3mod4 divisant B. En déduire qu'il existe un nombre premier congru à 3mod4 et divisant x 2+1.
      Solution
      On a 8y 3=(2y)(4+2y+y 2), donc B=4+2y+y 2. Comme y est impair,
      y 21mod8, 2y2mod4,
      donc B est congru à 3mod4. D'après la question précédente, il existe un nombre premier p divisant B et congru à 3mod4. Comme il divise B, il divise aussi (2y)B=8y 3=x 2+1.
  3. Conclure.
    Solution
    Soit des entiers x et y tels que x 2+y 3=7. On a trouvé un nombre premier p divisant y 38 et congru à 3 mod 4. Pour ce nombre premier,
    x 2+1=8y 30modp.
    Donc 1 est un carré modulo p, ce qui est absurde, car p est congru à 3mod4.

Pour aller plus loin

Thèmes

document sur les classes de congruence.
: group_theory,modular_arithmetic, Exercices interactifs Mathématiques

The most recent version

Cette page n'est pas dans son apparence habituelle parce que WIMS n'a pas pu reconnaître votre navigateur web.
Afin de tester le navigateur que vous utilisez, veuillez taper le mot wims ici : puis appuyez sur ``Entrer''.

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.