Arithmétique : Congruences & Théorème Chinois

Correction :

La définition de $a \equiv b \pmod{n}$ est que $n$ divise $a-b$, c'est-à-dire qu'il existe un entier $k$ tel que $a-b = nk$.

a) Si $a \equiv b \pmod{n}$, alors $a-b = nk$ pour un entier $k$.

On veut montrer $a+c \equiv b+c \pmod{n}$, ce qui équivaut à montrer que $n$ divise $(a+c) - (b+c)$.

$(a+c) - (b+c) = a+c-b-c = a-b = nk$. Puisque $nk$ est un multiple de $n$, $n$ divise $(a+c) - (b+c)$. Donc $a+c \equiv b+c \pmod{n}$.

b) Si $a \equiv b \pmod{n}$, alors $a-b = nk$ pour un entier $k$.

On veut montrer $ac \equiv bc \pmod{n}$, ce qui équivaut à montrer que $n$ divise $ac - bc$.

$ac - bc = c(a-b) = c(nk) = n(ck)$. Puisque $ck$ est un entier, $n(ck)$ est un multiple de $n$. Donc $ac \equiv bc \pmod{n}$.

c) Si $a \equiv b \pmod{n}$ et $c \equiv d \pmod{n}$ :

Pour la somme : $a-b = n k_1$ et $c-d = n k_2$ pour des entiers $k_1, k_2$.

$(a+c) - (b+d) = (a-b) + (c-d) = n k_1 + n k_2 = n(k_1+k_2)$. Donc $a+c \equiv b+d \pmod{n}$.

Pour le produit : $a-b = n k_1$ et $c-d = n k_2$. On a $a = b + n k_1$ et $c = d + n k_2$.

$ac = (b+n k_1)(d+n k_2) = bd + b n k_2 + d n k_1 + n^2 k_1 k_2 = bd + n(b k_2 + d k_1 + n k_1 k_2)$.

$ac - bd = n(b k_2 + d k_1 + n k_1 k_2)$. Puisque $b k_2 + d k_1 + n k_1 k_2$ est un entier, $ac - bd$ est un multiple de $n$. Donc $ac \equiv bd \pmod{n}$.

Correction :

Nous cherchons un entier $x$ tel que $5x - 3$ soit un multiple de 7.

Pour résoudre $ax \equiv b \pmod{n}$, on peut chercher l'inverse multiplicatif de $a$ modulo $n$. Ici, on cherche l'inverse de 5 modulo 7.

On utilise l'algorithme d'Euclide étendu pour trouver des entiers $u, v$ tels que $5u + 7v = \text{pgcd}(5, 7)$.

On sait que $\text{pgcd}(5, 7) = 1$.

$7 = 1 \cdot 5 + 2$

$5 = 2 \cdot 2 + 1$

En remontant : $1 = 5 - 2 \cdot 2 = 5 - 2 \cdot (7 - 1 \cdot 5) = 5 - 2 \cdot 7 + 2 \cdot 5 = 3 \cdot 5 - 2 \cdot 7$.

Donc, on a $3 \cdot 5 - 2 \cdot 7 = 1$. En regardant modulo 7, on obtient $3 \cdot 5 \equiv 1 \pmod{7}$.

L'inverse de 5 modulo 7 est 3.

Maintenant, on multiplie les deux membres de la congruence $5x \equiv 3 \pmod{7}$ par 3 :

$3 \cdot (5x) \equiv 3 \cdot 3 \pmod{7}$

$(3 \cdot 5) x \equiv 9 \pmod{7}$

$1 \cdot x \equiv 9 \pmod{7}$

$x \equiv 9 \pmod{7}$.

Comme $9 = 1 \cdot 7 + 2$, $9 \equiv 2 \pmod{7}$.

Donc, $x \equiv 2 \pmod{7}$.

La solution est l'ensemble des entiers de la forme $x = 7k + 2$, pour tout entier $k$. On peut vérifier : $5(2) = 10 \equiv 3 \pmod{7}$.

Correction :

Nous avons deux congruences :

1) $x \equiv 1 \pmod{3}$, ce qui signifie que $x = 3k + 1$ pour un entier $k$.

2) $x \equiv 2 \pmod{5}$.

Substituons la première équation dans la seconde :

$3k + 1 \equiv 2 \pmod{5}$

$3k \equiv 2 - 1 \pmod{5}$

$3k \equiv 1 \pmod{5}$.

Pour résoudre $3k \equiv 1 \pmod{5}$, cherchons l'inverse de 3 modulo 5. On peut tester : $3 \cdot 1 = 3$, $3 \cdot 2 = 6 \equiv 1 \pmod{5}$. L'inverse de 3 modulo 5 est 2.

Multiplions la congruence par 2 :

$2 \cdot (3k) \equiv 2 \cdot 1 \pmod{5}$

$6k \equiv 2 \pmod{5}$

$1k \equiv 2 \pmod{5}$, donc $k \equiv 2 \pmod{5}$.

Ceci signifie que $k$ peut s'écrire sous la forme $k = 5j + 2$ pour un entier $j$.

Maintenant, substituons cette expression de $k$ dans l'équation de la première congruence :

$x = 3k + 1 = 3(5j + 2) + 1 = 15j + 6 + 1 = 15j + 7$.

Donc, $x \equiv 7 \pmod{15}$.

Le module du système est $3 \times 5 = 15$, car 3 et 5 sont premiers entre eux.

Vérification :

Pour $x=7$: $7 \equiv 1 \pmod{3}$ (car $7-1=6$, divisible par 3) et $7 \equiv 2 \pmod{5}$ (car $7-2=5$, divisible par 5). La solution est correcte.

Correction :

Les modules 3, 5, et 7 sont premiers entre eux deux à deux. Donc, par le Théorème des Restes Chinois (TRC), il existe une solution unique modulo $N = 3 \times 5 \times 7 = 105$.

Résolvons par substitution :

1) $x \equiv 2 \pmod{3} \implies x = 3k + 2$ pour un entier $k$.

Substituons dans la deuxième congruence :

$3k + 2 \equiv 3 \pmod{5}$

$3k \equiv 1 \pmod{5}$.

Comme vu précédemment, l'inverse de 3 modulo 5 est 2.

$2 \cdot (3k) \equiv 2 \cdot 1 \pmod{5} \implies 6k \equiv 2 \pmod{5} \implies k \equiv 2 \pmod{5}$.

Donc, $k = 5j + 2$ pour un entier $j$.

Substituons cette expression de $k$ dans l'expression de $x$ :

$x = 3k + 2 = 3(5j + 2) + 2 = 15j + 6 + 2 = 15j + 8$.

Maintenant, substituons cette nouvelle expression de $x$ dans la troisième congruence :

$15j + 8 \equiv 2 \pmod{7}$.

Calculons $15 \pmod{7}$ et $8 \pmod{7}$.

$15 = 2 \cdot 7 + 1$, donc $15 \equiv 1 \pmod{7}$.

$8 = 1 \cdot 7 + 1$, donc $8 \equiv 1 \pmod{7}$.

La congruence devient :

$1j + 1 \equiv 2 \pmod{7}$

$j \equiv 2 - 1 \pmod{7}$

$j \equiv 1 \pmod{7}$.

Donc, $j = 7m + 1$ pour un entier $m$.

Substituons cette expression de $j$ dans l'expression de $x$ :

$x = 15j + 8 = 15(7m + 1) + 8 = 105m + 15 + 8 = 105m + 23$.

La solution est $x \equiv 23 \pmod{105}$.

Vérification :

$23 \equiv 2 \pmod{3}$ (car $23-2=21$ divisible par 3).

$23 \equiv 3 \pmod{5}$ (car $23-3=20$ divisible par 5).

$23 \equiv 2 \pmod{7}$ (car $23-2=21$ divisible par 7).

La solution est correcte.

Correction :

a) Existence et unicité :

Le Théorème des Restes Chinois stipule que si les modules $n_1, n_2, \dots, n_k$ sont premiers entre eux deux à deux, alors pour tout système de congruences $x \equiv a_i \pmod{n_i}$ pour $i=1, \dots, k$, il existe une solution unique modulo $N = n_1 n_2 \dots n_k$.

Dans notre cas, $n_1$ et $n_2$ sont premiers entre eux, donc il existe une solution unique modulo $n_1 n_2$.

b) Formule de la solution :

Soit $N = n_1 n_2$. Définissons $N_1 = N/n_1 = n_2$ et $N_2 = N/n_2 = n_1$.

Comme $n_1$ et $n_2$ sont premiers entre eux, $\text{pgcd}(N_1, n_1) = \text{pgcd}(n_2, n_1) = 1$, et $\text{pgcd}(N_2, n_2) = \text{pgcd}(n_1, n_2) = 1$.

Par conséquent, $N_1$ admet un inverse multiplicatif modulo $n_1$, que nous noterons $y_1$ (tel que $N_1 y_1 \equiv 1 \pmod{n_1}$).

De même, $N_2$ admet un inverse multiplicatif modulo $n_2$, que nous noterons $y_2$ (tel que $N_2 y_2 \equiv 1 \pmod{n_2}$).

Considérons la solution proposée : $x = a_1 N_1 y_1 + a_2 N_2 y_2$.

Regardons cette expression modulo $n_1$ :

$x \equiv a_1 N_1 y_1 + a_2 N_2 y_2 \pmod{n_1}$.

On sait que $N_1 y_1 \equiv 1 \pmod{n_1}$.

De plus, $N_2 = n_1$. Donc $N_2 \equiv 0 \pmod{n_1}$. Par conséquent, $a_2 N_2 y_2 \equiv a_2 \cdot 0 \cdot y_2 \equiv 0 \pmod{n_1}$.

Donc, $x \equiv a_1 \cdot 1 + 0 \pmod{n_1}$, ce qui donne $x \equiv a_1 \pmod{n_1}$. La première congruence est satisfaite.

Maintenant, regardons l'expression modulo $n_2$ :

$x \equiv a_1 N_1 y_1 + a_2 N_2 y_2 \pmod{n_2}$.

On sait que $N_2 y_2 \equiv 1 \pmod{n_2}$.

De plus, $N_1 = n_2$. Donc $N_1 \equiv 0 \pmod{n_2}$. Par conséquent, $a_1 N_1 y_1 \equiv a_1 \cdot 0 \cdot y_1 \equiv 0 \pmod{n_2}$.

Donc, $x \equiv 0 + a_2 \cdot 1 \pmod{n_2}$, ce qui donne $x \equiv a_2 \pmod{n_2}$. La seconde congruence est satisfaite.

Ainsi, $x = a_1 N_1 y_1 + a_2 N_2 y_2$ est bien une solution. Par le TRC, elle est unique modulo $n_1 n_2$.

Correction :

Les modules $n_1=3, n_2=5, n_3=7$ sont premiers entre eux. Le produit $N = 3 \times 5 \times 7 = 105$. La solution sera unique modulo 105.

On a $a_1=1, a_2=2, a_3=3$.

Calculons $N_i = N/n_i$ :

$N_1 = 105/3 = 35$.

$N_2 = 105/5 = 21$.

$N_3 = 105/7 = 15$.

Maintenant, trouvons les inverses $y_i$ tels que $N_i y_i \equiv 1 \pmod{n_i}$ :

Pour $i=1$: $N_1 y_1 \equiv 1 \pmod{3} \implies 35 y_1 \equiv 1 \pmod{3}$.

$35 = 11 \cdot 3 + 2$, donc $35 \equiv 2 \pmod{3}$. La congruence est $2 y_1 \equiv 1 \pmod{3}$.

L'inverse de 2 modulo 3 est 2, car $2 \cdot 2 = 4 \equiv 1 \pmod{3}$. Donc $y_1 = 2$.

Pour $i=2$: $N_2 y_2 \equiv 1 \pmod{5} \implies 21 y_2 \equiv 1 \pmod{5}$.

$21 = 4 \cdot 5 + 1$, donc $21 \equiv 1 \pmod{5}$. La congruence est $1 y_2 \equiv 1 \pmod{5}$.

Donc $y_2 = 1$.

Pour $i=3$: $N_3 y_3 \equiv 1 \pmod{7} \implies 15 y_3 \equiv 1 \pmod{7}$.

$15 = 2 \cdot 7 + 1$, donc $15 \equiv 1 \pmod{7}$. La congruence est $1 y_3 \equiv 1 \pmod{7}$.

Donc $y_3 = 1$.

Maintenant, appliquons la formule de la solution :

$x \equiv a_1 N_1 y_1 + a_2 N_2 y_2 + a_3 N_3 y_3 \pmod{N}$

$x \equiv (1)(35)(2) + (2)(21)(1) + (3)(15)(1) \pmod{105}$

$x \equiv 70 + 42 + 45 \pmod{105}$

$x \equiv 157 \pmod{105}$.

Réduisons modulo 105 :

$157 = 1 \cdot 105 + 52$.

$x \equiv 52 \pmod{105}$.

Vérification :

$52 \equiv 1 \pmod{3}$ (car $52-1=51$, $51=17 \cdot 3$).

$52 \equiv 2 \pmod{5}$ (car $52-2=50$, $50=10 \cdot 5$).

$52 \equiv 3 \pmod{7}$ (car $52-3=49$, $49=7 \cdot 7$).

La solution $x \equiv 52 \pmod{105}$ est correcte.

Correction :

Les modules 10 et 6 ne sont pas premiers entre eux ($\text{pgcd}(10, 6) = 2$). Le Théorème des Restes Chinois ne s'applique pas directement.

On va utiliser la méthode de substitution.

1) $x \equiv 7 \pmod{10} \implies x = 10k + 7$ pour un entier $k$.

Substituons dans la deuxième congruence :

$10k + 7 \equiv 3 \pmod{6}$.

Réduisons les coefficients modulo 6 :

$10 \equiv 4 \pmod{6}$

$7 \equiv 1 \pmod{6}$

La congruence devient :

$4k + 1 \equiv 3 \pmod{6}$

$4k \equiv 2 \pmod{6}$.

Pour résoudre $ak \equiv b \pmod{n}$, on regarde $\text{pgcd}(a, n)$. Ici, $\text{pgcd}(4, 6) = 2$.

Puisque 2 divise 2 (le $b$), il y a des solutions. Le nombre de solutions modulo 6 est égal à $\text{pgcd}(4, 6) = 2$.

Pour trouver les solutions, on divise toute la congruence par $\text{pgcd}(a, n)$ et le module par $\text{pgcd}(a, n)$ :

Divisons par 2 : $2k \equiv 1 \pmod{3}$.

Maintenant, 2 et 3 sont premiers entre eux. L'inverse de 2 modulo 3 est 2.

$2 \cdot (2k) \equiv 2 \cdot 1 \pmod{3}$

$4k \equiv 2 \pmod{3}$

$k \equiv 2 \pmod{3}$.

Ceci signifie que $k$ peut s'écrire sous la forme $k = 3j + 2$ pour un entier $j$.

Cependant, nous avons vu qu'il y avait deux solutions pour $k$ modulo 6. Les solutions de $k \equiv 2 \pmod{3}$ sont $k \equiv 2 \pmod{6}$ et $k \equiv 2+3 \equiv 5 \pmod{6}$.

Prenons $k = 3j + 2$ et substituons dans l'expression de $x$ :

$x = 10k + 7 = 10(3j + 2) + 7 = 30j + 20 + 7 = 30j + 27$.

Donc, $x \equiv 27 \pmod{30}$.

Le module de la solution est 30. Remarquons que $30 = \text{ppcm}(10, 6)$.

Vérification :

$27 \equiv 7 \pmod{10}$ (car $27-7=20$, divisible par 10).

$27 \equiv 3 \pmod{6}$ (car $27-3=24$, divisible par 6).

La solution est correcte. Le module est bien le plus petit commun multiple des modules initiaux (si une solution existe).

Correction :

Les modules $n_1=8$ et $n_2=6$ ne sont pas premiers entre eux. $\text{pgcd}(8, 6) = 2$.

Pour qu'une solution existe, il faut que la condition de compatibilité soit vérifiée : $a_1 \equiv a_2 \pmod{\text{pgcd}(n_1, n_2)}$.

Ici, $a_1=5$ et $a_2=2$. On doit vérifier si $5 \equiv 2 \pmod{2}$.

$5 - 2 = 3$. Est-ce que 2 divise 3 ? Non.

Donc, $5 \not\equiv 2 \pmod{2}$. La condition de compatibilité n'est pas satisfaite.

Ce système n'admet pas de solution.

Expliquons pourquoi :

De $x \equiv 5 \pmod{8}$, on déduit que $x$ est impair (car $5$ est impair et $8$ est pair). $x = 8k+5$.

De $x \equiv 2 \pmod{6}$, on déduit que $x$ est pair (car $2$ est pair et $6$ est pair). $x = 6j+2$.

Un nombre ne peut pas être à la fois pair et impair. Donc, il ne peut pas y avoir de solution.

Correction :

Nous devons calculer $c \equiv 5^3 \pmod{14}$.

D'abord, calculons $5^3$ : $5^3 = 5 \times 5 \times 5 = 25 \times 5 = 125$.

Maintenant, nous calculons le reste de la division de 125 par 14 :

$125 \div 14$.

On peut estimer : $14 \times 10 = 140$. C'est trop grand.

$14 \times 9 = (10+4) \times 9 = 90 + 36 = 126$. C'est juste au-dessus.

$14 \times 8 = 126 - 14 = 112$.

Donc, $125 = 8 \times 14 + 13$.

Le reste est 13.

Donc, $c \equiv 13 \pmod{14}$.

Le message chiffré est $c=13$.

Correction :

Ce problème peut être reformulé en termes de congruences. On cherche un nombre de jours $x$ tel que :

{ $x \equiv 0 \pmod{4}$ (la machine A redémarre)

{ $x \equiv 0 \pmod{6}$ (la machine B redémarre)

{ $x \equiv 0 \pmod{10}$ (la machine C redémarre)

Nous cherchons le plus petit entier positif $x$ qui est un multiple commun de 4, 6 et 10.

Ceci correspond à trouver le Plus Petit Commun Multiple (PPCM) de 4, 6 et 10.

Décomposons chaque nombre en facteurs premiers :

$4 = 2^2$

$6 = 2 \times 3$

$10 = 2 \times 5$

Pour trouver le PPCM, on prend la puissance la plus élevée de chaque facteur premier présent dans les décompositions :

PPCM(4, 6, 10) = $2^2 \times 3^1 \times 5^1 = 4 \times 3 \times 5 = 60$.

Donc, les trois machines redémarreront le même jour pour la première fois dans 60 jours.

Dans le contexte des congruences, on cherche $x$ tel que $x \equiv 0 \pmod{\text{ppcm}(4, 6, 10)}$, ce qui donne $x \equiv 0 \pmod{60}$. Le plus petit entier positif est 60.