Théorie > Théorie des nombres > Arithmétique modulaire


Général

Introduction Chapitre entier

Points théoriques

Définition Propriétés Exemple d'utilisation Critères de divisibilité Théorème de Wilson

Exercices

Exercice 1 Exercice 2 Exercice 3 Exercice 4 Exercice 5 Exercice 6 Exercice 7

Propriétés

On aimerait, lorsque l'on se met à travailler modulo $n$, pouvoir continuer à additionner ou multiplier des nombres comme on le fait d'habitude sur les nombres entiers. Les propriétés élémentaires suivantes nous indiquent que cela nous est généralement permis.

  • Si $a \equiv b \pmod n$ et $c \equiv d \pmod n$, alors $a + c \equiv b + d \pmod n$. En effet, si $n$ divise $a-b$ et $c-d$, il divise automatiquement $a+c-(b+d)$.

  • Si $a \equiv b \pmod n$ et $c \equiv d \pmod n$, alors $a - c \equiv b - d \pmod n$. Le raisonnement est identique.

  • Si $a \equiv b \pmod n$ et $c \equiv d \pmod n$, alors $a c \equiv b d \pmod n$. En effet, si $n$ divise $a-b$ et $c-d$, alors il divise également $ac-bd = (a-b)\cdot c + (c-d)\cdot b$.
Lorsqu'on utilise l'addition, la soustraction ou la multiplication, on peut donc presque oublier que nous travaillons modulo $n$ et manipuler les nombres comme nous le faisions avant.
Cela n'est cependant pas aussi simple si l'on souhaite utiliser la division! Par exemple, pour $n = 10$, on a $6 \equiv 16 \pmod{10}$ mais $3 \not \equiv 8 \pmod{10}$. On ne peut donc dans ce cas pas impunément diviser les deux membres d'une égalité par $2$.

Remarque

Nous disions plus haut que, en travaillant modulo $n$, nous pouvions désormais considérer deux nombres égaux modulo $n$ comme égaux tout court. Il s'agit là d'un raccourci de langage et il faut tout de même faire très attention en manipulant ainsi les nombres.
Pour illustrer ce danger, fixons $n = 5$. Si nous sommes en présence d'un nombre $x$, alors les propriétés précédentes nous indiquent que :

  • ajouter $6$ à $x$ revient à lui ajouter $1$,
  • soustraire $6$ à $x$ revient à lui soustraire $1$,
  • multiplier $x$ par $6$ revient à le multiplier par $1$.
Il existe cependant un cas où nous pourrions être tenté de remplacer $6$ par $1$ alors que cela ne nous est pas permis : celui de la puissance. Modulo $5$, élever $x$ à la puissance $6$ ne revient pas à l'élever à la puissance $1$. La puissance $6$ n'est qu'une simple notation pour écrire $x \cdot x \cdot \ldots \cdot x$, où $x$ apparaît $6$ fois. Il n'y a aucune raison pour laquelle on pourrait remplacer $6$ par $1$ dans ce cas. On constate par exemple que $2^6 \equiv 64 \equiv 4 \pmod 5$ alors que $2^1 \equiv 2 \pmod 5$.
Cela dit, nous verrons dans un prochain chapitre qu'il existe une façon de remplacer une puissance par une autre plus petite correctement, grâce au théorème d'Euler-Fermat.