Congruences dans ℤ et résolution d'équations modulaires
L'essentiel du cours (3 notions)
Relation de congruence et opérations
Définition : Soit $n \in \mathbb{N}^*$. Deux entiers $a$ et $b$ sont congrus modulo $n$, noté $a \equiv b [n]$, si $n$ divise $a - b$.
Propriété : Si $a \equiv b [n]$ et $c \equiv d [n]$, alors $a+c \equiv b+d [n]$, $ac \equiv bd [n]$ et $a^k \equiv b^k [n]$ ($k \in \mathbb{N}$). La division est en général interdite.
Exemple : $17 \equiv 3 [7]$ et $10 \equiv 3 [7]$. Alors $17+10 \equiv 6 [7]$ et $17 \times 10 \equiv 9 \equiv 2 [7]$.
Inverse modulo $n$ et équations
Propriété : $a$ admet un inverse modulo $n$ si et seulement si $\text{pgcd}(a, n) = 1$. Il existe alors un entier $u$ tel que $au \equiv 1 [n]$.
Méthode : Pour résoudre $ax \equiv b [n]$ avec $\text{pgcd}(a,n)=1$ : 1. Déterminer un inverse $u$ de $a$ modulo $n$. 2. Multiplier par $u$ pour obtenir $x \equiv ub [n]$.
Exemple : Pour $3x \equiv 2 [5]$ : comme $3 \times 2 \equiv 1 [5]$, l'inverse de $3$ est $2$. D'où $x \equiv 2 \times 2 \equiv 4 [5]$.
Systèmes et Lemme chinois
Propriété : Si $n_1$ et $n_2$ sont premiers entre eux, le système $\begin{cases} x \equiv a_1 [n_1] \\ x \equiv a_2 [n_2] \end{cases}$ admet une unique solution modulo $n_1 n_2$.
Méthode : 1. Poser $x = a_1 + k n_1$ avec $k \in \mathbb{Z}$. 2. Injecter dans la seconde congruence : $a_1 + k n_1 \equiv a_2 [n_2]$. 3. Isoler $k$ modulo $n_2$ via l'inverse de $n_1$.
Exemple : $\begin{cases} x \equiv 1 [3] \\ x \equiv 2 [5] \end{cases} \Rightarrow 1+3k \equiv 2 [5] \Rightarrow 3k \equiv 1 [5] \Rightarrow k \equiv 2 [5] \Rightarrow x \equiv 7 [15]$.
On s'intéresse aux puissances de $3$ modulo $5$.
En utilisant la compatibilité de la congruence avec la multiplication, déterminer les restes successifs de $3^n$ dans la division euclidienne par $5$ pour les entiers naturels non nuls $n$.
Quel est le plus petit entier naturel $n \ge 1$ vérifiant la relation $3^n \equiv 1 \pmod 5$ ?
Soit $x$ un entier relatif vérifiant la relation de congruence suivante :
$$8x \equiv 5 \pmod{23}$$Déterminer l'unique entier $r \in \{0, 1, 2, \dots, 22\}$ tel que $x \equiv r \pmod{23}$.
Saisir la valeur de $r$.
On souhaite résoudre dans $\mathbb{Z}$ l'équation de congruence $7x \equiv 12 \pmod{17}$.
- Déterminer l'inverse de $7$ modulo $17$ appartenant à l'ensemble $\{0, 1, \dots, 16\}$.
- En déduire l'unique entier $x$ tel que $0 \le x \le 16$ vérifiant $7x \equiv 12 \pmod{17}$.
Saisir la valeur de $x$.
On considère la congruence d'inconnue $x \in \mathbb{Z}$ suivante :
$$7x \equiv 6 \pmod{23}$$
En déterminant un inverse de $7$ modulo $23$, déterminer l'unique entier $x$ vérifiant $0 \le x < 23$ solution de cette équation.
Saisir cet entier $x$.
Un procédé de chiffrement utilise un nombre entier $x$, compris entre $0$ et $52$, tel que :
$$19x \equiv 7 \pmod{53}$$On cherche à retrouver la valeur initiale de l'entier $x$.
Saisir la valeur de l'entier $x$.
Soit $a$ un entier naturel tel que $0 \le a \le 12$.
On considère le nombre entier $N$ défini par :
$$N = 3^{2026} + 5^{2025} + a$$Déterminer la valeur de l'entier $a$ pour que $N$ soit divisible par $13$.
Saisir la valeur de $a$.
On considère l'affirmation suivante :
« Pour tout entier naturel $n$, le nombre $2^{3n+1} + 3 \times 5^n$ n'est pas divisible par $11$. »
Cette affirmation est fausse. On cherche le plus petit entier naturel $n$ qui constitue un contre-exemple, c'est-à-dire le plus petit entier naturel $n$ tel que $2^{3n+1} + 3 \times 5^n$ soit divisible par $11$.
Saisir la valeur de l'entier $n$.
On considère, pour tout entier $k$ vérifiant $0 \le k \le 28$, le système de congruences d'inconnue $x \in \mathbb{Z}$ suivant :
$$\begin{cases} 17x \equiv 4 \pmod{29} \\ 5x \equiv k \pmod{29} \end{cases}$$
Déterminer l'unique valeur de $k$ pour laquelle ce système admet au moins une solution entière $x$.
Saisir la valeur de $k$.