Arithmétique : congruences et résidus

Légende de la leçon

Vert : définitions

I. Introduction aux congruences

1) Définition et origine

Les congruences ont été introduites par Carl Friedrich Gauss dans son œuvre Disquisitiones Arithmeticae. Une congruence est une relation qui indique que deux nombres ont le même reste lorsqu'ils sont divisés par un même nombre non nul.

2) Notation et interprétation

La notation $a \equiv b\,(\text{mod}\,n)$, où $n$ est un entier positif, signifie que $a$ et $b$ laissent le même reste quand divisés par $n$. C'est équivalent à dire que $n$ divise la différence $a - b$.

3) Exemple introductif

Considérons l'équation $17 \equiv 5\,(\text{mod}\,6)$. Elle est vraie car $17$ et $5$ laissent tous deux un reste de $5$ lorsqu'ils sont divisés par $6$.

II. Propriétés des congruences

1) Propriétés de base

Les congruences respectent les propriétés de transitivité, symétrie et réflexivité, similaires à l'égalité dans les nombres entiers.

2) Opérations avec les congruences

• Addition : Si $a \equiv b\,(\text{mod}\,n)$ et $c \equiv d\,(\text{mod}\,n)$, alors $a + c \equiv b + d\,(\text{mod}\,n)$.
• Soustraction : Si $a \equiv b\,(\text{mod}\,n)$ et $c \equiv d\,(\text{mod}\,n)$, alors $a - c \equiv b - d\,(\text{mod}\,n)$.
• Multiplication : Si $a \equiv b\,(\text{mod}\,n)$, alors $ac \equiv bc\,(\text{mod}\,n)$ pour tout entier $c$.
• Puissance : Si $a \equiv b\,(\text{mod}\,n)$, alors $a^k \equiv b^k\,(\text{mod}\,n)$ pour tout entier positif $k$.

3) Exemple

Pour vérifier $2^3 \equiv 8\,(\text{mod}\,6)$, nous calculons $2^3 = 8$ et observons que $8$ laisse un reste de $2$ quand il est divisé par $6$.

III. Systèmes de congruences

1) Systèmes linéaires de congruences

Un système de congruences est un ensemble de congruences qui doivent être satisfaites simultanément. La résolution peut impliquer plusieurs méthodes, dont l'utilisation du théorème des restes chinois.

2) Théorème des restes chinois

Ce théorème fournit une méthode pour résoudre des systèmes de congruences linéaires. Il énonce que si nous avons un système de congruences où les moduli sont deux à deux premiers entre eux, alors il existe une solution unique modulo le produit de ces moduli.

3) Exemple

Trouver un entier $x$ tel que $x \equiv 2\,(\text{mod}\,3)$ et $x \equiv 3\,(\text{mod}\,5)$. La solution est $x \equiv 8\,(\text{mod}\,15)$.

IV. Résidus quadratiques

1) Définition

Un entier $a$ est un résidu quadratique modulo $n$ si il existe un entier $x$ tel que $x^2 \equiv a\,(\text{mod}\,n)$. Sinon, $a$ est un non-résidu quadratique.

2) Loi de réciprocité quadratique

Cette loi est un résultat important qui établit une relation entre les résidus quadratiques de deux nombres premiers impairs différents. Elle permet de déterminer si un nombre est un résidu quadratique modulo un autre.

3) Exemple

1 est un résidu quadratique modulo 4, mais 3 n'en est pas un.

V. Applications Pratiques des Congruences

1) Cryptographie

Les congruences sont au cœur de nombreux algorithmes de cryptographie, comme l'algorithme RSA qui repose sur la difficulté de factoriser de grands nombres et les propriétés des congruences.

2) Informatique

Les congruences sont utilisées dans les algorithmes de génération de nombres pseudo-aléatoires et dans d'autres applications nécessitant des calculs modulaires.

Je retiens

Congruences : un concept clé en arithmétique pour comparer des entiers dans le cadre modulaire.

Propriétés et opérations : règles fondamentales pour la manipulation des congruences.

Applications : de la cryptographie à la résolution de problèmes complexes, les congruences sont un outil puissant en mathématiques et informatique.