Exercices : Equation diophantienne - Arithmétique - Maths Expertes

Correction :

1. Pour qu'une équation diophantienne $ax + by = c$ ait des solutions entières, il faut que $\text{pgcd}(a, b)$ divise $c$. Ici, $\text{pgcd}(15, -9) = 3$. Or, 3 ne divise pas 14. Donc l'équation $15x - 9y = 14$ n'a pas de solution entière.

2. a. $\text{pgcd}(13, 9) = 1$ (algorithme d'Euclide). Comme 1 divise 2, l'équation $(E)$ a au moins une solution entière (théorème de Bézout).

b. On utilise l'algorithme d'Euclide étendu pour trouver $u$ et $v$ tels que $13u + 9v = 1$:
$13 = 1 \times 9 + 4$
$9 = 2 \times 4 + 1$
$1 = 9 - 2 \times 4 = 9 - 2(13 - 9) = 3 \times 9 - 2 \times 13$.
Donc $13(-2) + 9(3) = 1$. Pour avoir 2, on multiplie par 2 : $13(-4) + 9(6) = 2$. Une solution particulière est $(x_0, y_0) = (-4, 6)$.

c. $(E) : 13x + 9y = 2$ et $13x_0 + 9y_0 = 2$. En soustrayant, $13(x - x_0) + 9(y - y_0) = 0$, soit $13(x - x_0) = -9(y - y_0)$.

d. De $(E')$, $13(x - (-4)) = -9(y - 6)$, soit $13(x + 4) = -9(y - 6)$. Donc 13 divise $-9(y - 6)$. Comme $\text{pgcd}(13, -9) = \text{pgcd}(13, 9) = 1$, par le théorème de Gauss, 13 divise $y - 6$. Donc il existe $k \in \mathbb{Z}$ tel que $y - 6 = 13k$, soit $y = 6 + 13k$.
En substituant dans $(E')$ : $13(x + 4) = -9(13k)$. On simplifie par 13 : $x + 4 = -9k$, donc $x = -4 - 9k$.
Attentionau signe de $k$! L'énoncé a une petite erreur, et propose $x = -4+9k$. Montrons que $y = 6-13k$.
Comme $-9$ divise $13(x+4)$, et $\text{pgcd}(-9,13) = 1$, par le théorème de Gauss, il existe un entier relatif $k'$ tel que $x+4=-9k' \implies x = -4-9k'$.
On remplace dans l'equation $13(x-x_0) = -9(y-y_0)$ et on obtient $13(-9k')=-9(y-6) \implies y-6=13k' \implies y = 6+13k'$.
Finalement on pose $k=-k'$ et on obtient : $x = -4+9k$ et $y = 6-13k$.

e. L'ensemble des solutions est $\{(x, y) ~|~ x = -4 + 9k, y = 6 - 13k, k \in \mathbb{Z}\}$. Vérification: $13(-4 + 9k) + 9(6 - 13k) = -52 + 117k + 54 - 117k = 2$.

Conseil : Pour la résolution complète, ne pas oublier de vérifier que les couples trouvés sont bien solutions de l'équation de départ.

Correction :

1. Si 3 et 4 divisent un nombre $n$, et comme $\text{pgcd}(3, 4) = 1$, alors $3 \times 4 = 12$ divise $n$ (corollaire du théorème de Gauss). L'affirmation est contradictoire.

2. Pour $n \ge 2$, $2^n$ est divisible par 4. Donc $2^{33} \equiv 0 \pmod{4}$. Alors $2^{33} - 1 \equiv -1 \equiv 3 \pmod{4}$. Le reste de la division de $2^{33}-1$ par 4 est 3, donc 4 ne divise pas $2^{33}-1$.

3. $2 \equiv -1 \pmod{3}$. Donc $2^{33} \equiv (-1)^{33} \equiv -1 \pmod{3}$. Alors $2^{33} - 1 \equiv -1 - 1 \equiv -2 \equiv 1 \pmod{3}$. Le reste est 1, donc 3 ne divise pas $2^{33}-1$.

4. $2^1 \equiv 2 \pmod{7}$, $2^2 \equiv 4 \pmod{7}$, $2^3 \equiv 8 \equiv 1 \pmod{7}$. $33 = 3 \times 11$, donc $2^{33} = (2^3)^{11} \equiv 1^{11} \equiv 1 \pmod{7}$. Alors $2^{33} - 1 \equiv 1 - 1 \equiv 0 \pmod{7}$. Donc 7 divise $2^{33}-1$.

Conseil : Pour étudier la divisibilité par un nombre, penser à utiliser les congruences et à chercher des motifs répétitifs (comme les puissances de 2 modulo 7).

Correction :

1. Théorème de Bézout : $a$ et $b$ sont premiers entre eux si et seulement s'il existe des entiers relatifs $u$ et $v$ tels que $au + bv = 1$.

2. Comme $a$ et $b$ sont premiers entre eux, d'après le théorème de Bézout, il existe des entiers $u$ et $v$ tels que $au + bv = 1$. En multipliant par $c$, on obtient $c(au + bv) = c$, soit $acu + bcv = c$.

3. On sait que $a$ divise $bc$, donc il existe un entier $k$ tel que $bc = ka$. On substitue dans l'équation : $acu + (ka)v = c$, soit $a(cu + kv) = c$. Comme $cu + kv$ est un entier, cela signifie que $a$ divise $c$.

Conseil : La démonstration du théorème de Gauss repose sur le théorème de Bézout. Il faut savoir multiplier l'identité de Bézout ($au+bv=1$) par un terme approprié (ici, $c$).

Correction :

1. Soient $x, y, z$ les nombres de fléchettes dans les zones à 0, 5, et 12 points, respectivement. On a :
$x + y + z = 25$ (total des fléchettes)
$0x + 5y + 12z = 200$ (total des points)
Soit $5y + 12z = 200$. On veut montrer que $z$ est divisible par 5. On réécrit : $12z = 200 - 5y = 5(40 - y)$. Donc 5 divise $12z$. Comme $\text{pgcd}(5, 12) = 1$, d'après le théorème de Gauss, 5 divise $z$.

2. $z$ est un multiple de 5 et $0 \le z \le 25$. $y = \frac{200 - 12z}{5} = 40 - \frac{12}{5}z$. Comme $y \ge 0$, $40 \ge \frac{12}{5}z$, soit $z \le \frac{200}{12} = \frac{50}{3} \approx 16.66$. Donc $z$ peut être 0, 5, 10, ou 15.
- Si $z = 0$, $y = 40$, $x = 25 - 40 - 0 = -15$, impossible.
- Si $z = 5$, $y = 40 - 12 = 28$, $x = 25 - 28 - 5 = -8$, impossible.
- Si $z = 10$, $y = 40 - 24 = 16$, $x = 25 - 16 - 10 = -1$, impossible.
- Si $z = 15$, $y = 40 - 36 = 4$, $x = 25 - 4 - 15 = 6$. C'est la seule solution possible.
Répartition : 6 fléchettes à 0 points, 4 fléchettes à 5 points, 15 fléchettes à 12 points.

Conseil : Dans ce type de problème, bien poser les équations, puis utiliser le théorème de Gauss et les contraintes (nombres positifs) pour réduire le nombre de solutions possibles.

Correction :

1. Si $x = \frac{p}{q}$ est solution, alors $3\left(\frac{p}{q}\right)^3 + 4\left(\frac{p}{q}\right)^2 + 2\left(\frac{p}{q}\right) - 4 = 0$. On multiplie par $q^3$ : $3p^3 + 4p^2q + 2pq^2 - 4q^3 = 0$.
On isole $3p^3 = -4p^2q - 2pq^2 + 4q^3 = q(-4p^2 - 2pq + 4q^2)$. Donc $q$ divise $3p^3$. Comme $\text{pgcd}(p, q) = 1$, alors $\text{pgcd}(p^3, q) = 1$. Donc, par le théorème de Gauss, $q$ divise 3.
On isole $4q^3 = 3p^3 + 4p^2q + 2pq^2 = p(3p^2 + 4pq + 2q^2)$. Donc $p$ divise $4q^3$. Comme $\text{pgcd}(p, q) = 1$, alors $\text{pgcd}(p, q^3) = 1$. Donc, par le théorème de Gauss, $p$ divise 4.

2. Diviseurs de 4 : $\pm 1, \pm 2, \pm 4$. Diviseurs de 3 : $\pm 1, \pm 3$. Solutions rationnelles possibles : $\pm 1, \pm 2, \pm 4, \pm \frac{1}{3}, \pm \frac{2}{3}, \pm \frac{4}{3}$. En testant, seule $x = \frac{2}{3}$ est solution. Donc (E) admet une unique solution rationnelle, $\frac{2}{3}$.

Conseil : Pour chercher les solutions rationnelles d'une équation polynomiale à coefficients entiers, ce résultat est très utile : le numérateur divise le terme constant, et le dénominateur divise le coefficient dominant.

Correction :

1. $M(x, y)$ est sur $(AB)$ si et seulement si les vecteurs $\overrightarrow{AM}$ et $\overrightarrow{AB}$ sont colinéaires. $\overrightarrow{AM} = (x - 7, y - 2)$ et $\overrightarrow{AB} = (-3 - 7, -4 - 2) = (-10, -6)$. La condition de colinéarité est : $(x - 7)(-6) - (y - 2)(-10) = 0$, soit $-6(x - 7) + 10(y - 2) = 0$. On divise par -2 : $3(x - 7) - 5(y - 2) = 0$, donc $3(x - 7) = 5(y - 2)$.

2. On doit résoudre l'équation diophantienne $3(x - 7) = 5(y - 2)$, soit $3x - 21 = 5y - 10$, ou $3x - 5y = 11$.
$\text{pgcd}(3, -5) = 1$, qui divise 11, donc il existe des solutions.
On cherche une solution particulière. On peut utiliser l'algorithme d'Euclide étendu, mais ici on peut trouver une solution "à vue" : Si $x = -3$, $3(-3) = -9$. Si $y = -4$, $-5(-4) = 20$. $-9 - (-20) = 11$, ça marche ! Donc $(-3, -4)$ est une solution particulière (c'est le point B !).
Solution générale : $x = -3 + 5k$, $y = -4 + 3k$, où $k \in \mathbb{Z}$. On peut aussi l'écrire $x=7+5k$, $y=2+3k$ en changeant de paramètre.
Vérification: Pour $k=0$, on a $(-3,-4)$ : $3(-3-7) = 3(-10) = -30$ et $5(-4-2) = 5(-6)=-30$. Pour $k=2$ on a $(7,2)$.

Conseil : Dans un repère, la condition de colinéarité de deux vecteurs est un outil puissant pour caractériser l'appartenance à une droite.

Correction :

1. Comme $a$ divise $n$, il existe un entier $q$ tel que $n = qa$. Comme $b$ divise $n$, il existe un entier $k'$ tel que $n = k'b$. On pose $k = q$. Alors $ka = qa = n$ et $k'b = n$, donc $ka = k'b = n$.

2. On a $qa = k'b$. Donc $k'b$ est un multiple de $a$, c'est-à-dire $a$ divise $k'b$. Comme $\text{pgcd}(a, b) = 1$, d'après le théorème de Gauss, $a$ divise $k'$.

3. Comme $a$ divise $k'$, il existe un entier $m$ tel que $k' = ma$. On avait $n = k'b$. En substituant $k' = ma$, on obtient $n = (ma)b = m(ab)$. Donc $n$ est un multiple de $ab$, c'est-à-dire $ab$ divise $n$.

Conseil : La démonstration du corollaire repose, comme celle du théorème de Gauss, sur le théorème de Bézout (implicitement, via Gauss).

Correction :

Soit $P = n(n+1)(n+2)(n+3)(n+4)$ le produit de 5 entiers consécutifs. $120 = 2^3 \times 3 \times 5 = 8 \times 3 \times 5$. Il suffit de montrer que $P$ est divisible par 8, 3, et 5, car ces nombres sont premiers entre eux deux à deux.
- Divisibilité par 5 : Parmi 5 entiers consécutifs, il y a toujours un multiple de 5. Donc $P$ est divisible par 5.
- Divisibilité par 3 : Parmi 3 entiers consécutifs, il y a toujours un multiple de 3. Donc parmi 5 entiers consécutifs, il y en a au moins un. Donc $P$ est divisible par 3.
- Divisibilité par 8 : Parmi 4 entiers consécutifs, il y a deux nombres pairs, dont un est multiple de 4. Donc le produit de 4 entiers consécutifs est divisible par $2 \times 4 = 8$. A fortiori, le produit de 5 entiers consécutifs est divisible par 8.
Comme $P$ est divisible par 3, 5, et 8, et que ces nombres sont premiers entre eux deux à deux, $P$ est divisible par $3 \times 5 \times 8 = 120$.

Conseil : Pour montrer qu'un produit d'entiers consécutifs est divisible par un nombre, décomposer ce nombre en facteurs premiers et utiliser le corollaire du théorème de Gauss.

Correction :

1. a) (i) Justification de l'existence de (u, v) :

On cherche un couple $(u, v)$ d'entiers relatifs tel que $17u + 5v = 1$. L'existence d'un tel couple est garantie par le théorème de Bézout, à condition que 17 et 5 soient premiers entre eux. Calculons leur PGCD avec l'algorithme d'Euclide :
$17 = 3 \times 5 + 2$
$5 = 2 \times 2 + 1$
$2 = 2 \times 1 + 0$
Le dernier reste non nul est 1, donc $\text{pgcd}(17, 5) = 1$. 17 et 5 sont premiers entre eux. Donc, d'après le théorème de Bézout, il existe bien un couple $(u, v)$ d'entiers relatifs tel que $17u + 5v = 1$.

(ii) Montrons que $n_0 = 3 \times 17u + 9 \times 5v$ appartient à $\mathscr{S}$ :

Pour que $n_0$ appartienne à $\mathscr{S}$, il faut qu'il vérifie les deux congruences du système : $n_0 \equiv 9 \pmod{17}$ et $n_0 \equiv 3 \pmod{5}$.
Modulo 17 : $n_0 = 3 \times 17u + 9 \times 5v \equiv 3 \times 0 + 9 \times 5v \equiv 45v \pmod{17}$. Or, on sait que $17u + 5v = 1$. Donc, modulo 17, $17u + 5v \equiv 0 + 5v \equiv 1 \pmod{17}$. Ainsi, $5v \equiv 1 \pmod{17}$. En substituant, $n_0 \equiv 9 \times (5v) \equiv 9 \times 1 \equiv 9 \pmod{17}$.
Modulo 5 : $n_0 = 3 \times 17u + 9 \times 5v \equiv 3 \times 17u + 9 \times 0 \equiv 51u \pmod{5}$. Or, $17u + 5v = 1$. Donc, modulo 5, $17u + 5v \equiv 17u + 0 \equiv 1 \pmod{5}$. On a $17 \equiv 2 \pmod{5}$, so $17u \equiv 2u$. On veut $17u \equiv 1 \pmod{5}$. Donc $51 u \equiv 17 \times 3 u$. Comme, $17u \equiv 1 \pmod{5}$, $n_0 \equiv 3 \times 17u \equiv 3 \pmod{5}$ .
$n_0$ vérifie les deux congruences, donc $n_0 \in \mathscr{S}$.

(iii) Exemple d'entier $n_0$ :

On doit trouver un couple $(u, v)$ vérifiant $17u + 5v = 1$. On remonte l'algorithme d'Euclide :
$1 = 5 - 2 \times 2 = 5 - 2(17 - 3 \times 5) = 5 - 2 \times 17 + 6 \times 5 = 7 \times 5 - 2 \times 17$.
Donc $17(-2) + 5(7) = 1$. On peut prendre $u = -2$ et $v = 7$. Alors, $n_0 = 3 \times 17(-2) + 9 \times 5(7) = -102 + 315 = 213$.
On peut vérifier : $213 = 12 \times 17 + 9$, donc $213 \equiv 9 \pmod{17}$. $213 = 42 \times 5 + 3$, donc $213 \equiv 3 \pmod{5}$. Donc $n_0 = 213$ est bien un exemple.
On peut aussi remarquer que $213 = 2 \times 85 + 43$. Donc $43$ est congru à $213$ modulo $85$ (car $85 = 5 \times 17$), et est aussi une solution : $43 = 2 \times 17 + 9$ et $43 = 8 \times 5 + 3$.

b) (i) Montrons que $n - n_0 \equiv 0 \pmod{85}$ :

Soit $n \in \mathscr{S}$. Alors, par définition, $n \equiv 9 \pmod{17}$ et $n \equiv 3 \pmod{5}$. On a montré que $n_0$ vérifie aussi ces congruences. Donc :
$n - n_0 \equiv 9 - 9 \equiv 0 \pmod{17}$, ce qui signifie que $n - n_0$ est divisible par 17.
$n - n_0 \equiv 3 - 3 \equiv 0 \pmod{5}$, ce qui signifie que $n - n_0$ est divisible par 5.
Donc $n - n_0$ est divisible par 17 et par 5. De plus, $\text{pgcd}(17, 5) = 1$. Donc, d'après le corollaire du théorème de Gauss, $n - n_0$ est divisible par le produit $17 \times 5 = 85$. Donc $n - n_0 \equiv 0 \pmod{85}$.

(ii) Montrons que $n \in \mathscr{S} \iff n = 43 + 85k, k \in \mathbb{Z}$ :

Sens direct ($\implies$) : Si $n \in \mathscr{S}$, alors d'après la question précédente, $n - n_0 \equiv 0 \pmod{85}$. On choisit $n_0 = 43$. Donc $n - 43 \equiv 0 \pmod{85}$. Cela signifie qu'il existe un entier relatif $k$ tel que $n - 43 = 85k$, soit $n = 43 + 85k$.
Réciproque ($\impliedby$) : Si $n = 43 + 85k$, avec $k \in \mathbb{Z}$, alors :
$n \equiv 43 \pmod{85}$.
Comme $43 = 2 \times 17 + 9$, $43 \equiv 9 \pmod{17}$. Et comme 85 est un multiple de 17, $85k \equiv 0 \pmod{17}$. Donc $n = 43 + 85k \equiv 43 + 0 \equiv 9 \pmod{17}$.
Comme $43 = 8 \times 5 + 3$, $43 \equiv 3 \pmod{5}$. Et comme 85 est un multiple de 5, $85k \equiv 0 \pmod{5}$. Donc $n = 43 + 85k \equiv 43 + 0 \equiv 3 \pmod{5}$.
Donc $n$ vérifie les deux congruences, et $n \in \mathscr{S}$.
Conclusion : $n \in \mathscr{S} \iff n = 43 + 85k$, où $k \in \mathbb{Z}$.

2. Nombre de jetons de Zoé :

Soit $n$ le nombre de jetons de Zoé. On sait que :
$n \equiv 9 \pmod{17}$ (reste 9 quand on fait des tas de 17)
$n \equiv 3 \pmod{5}$ (reste 3 quand on fait des tas de 5)
$300 \le n \le 400$ (Zoé a entre 300 et 400 jetons)
Donc $n$ vérifie le système de la question 1, et $n \in \mathscr{S}$. D'après la question précédente, $n$ est de la forme $n = 43 + 85k$, avec $k \in \mathbb{Z}$. On cherche $k$ tel que $300 \le 43 + 85k \le 400$.
$300 \le 43 + 85k \le 400$
$300 - 43 \le 85k \le 400 - 43$
$257 \le 85k \le 357$
$\frac{257}{85} \le k \le \frac{357}{85}$
$3.02... \le k \le 4.2...$
Comme $k$ est un entier, la seule valeur possible est $k = 4$. Alors $n = 43 + 85 \times 4 = 43 + 340 = 383$. Zoé a 383 jetons.

Conseil : Ce type de problème où l'on cherche un nombre vérifiant plusieurs congruences simultanées est un exemple classique d'application du théorème des restes chinois (qui, lui, n'est pas au programme de Terminale Spé Maths). La méthode générale consiste à trouver une solution particulière, puis à utiliser le corollaire du théorème de Gauss pour obtenir toutes les solutions.

Correction :

1. Montrons que $q_1$ divise $q_2$ :

On sait que $a + b$ et $ab$ sont des entiers. $a + b = \frac{p_1}{q_1} + \frac{p_2}{q_2} = \frac{p_1q_2 + p_2q_1}{q_1q_2}$. Comme $a + b$ est un entier, cela signifie que $q_1q_2$ divise $p_1q_2 + p_2q_1$. En particulier, $q_1$ divise $p_1q_2 + p_2q_1$.
Or, $q_1$ divise clairement $p_2q_1$ (car il y a $q_1$ en facteur). Donc $q_1$ divise la différence $(p_1q_2 + p_2q_1) - p_2q_1 = p_1q_2$. Donc $q_1$ divise $p_1q_2$.
On sait que $\text{pgcd}(p_1, q_1) = 1$. Donc, d'après le théorème de Gauss, comme $q_1$ divise $p_1q_2$ et que $q_1$ est premier avec $p_1$, alors $q_1$ divise $q_2$.

2. Déduisons que $q_1 = q_2$ :

On peut faire le même raisonnement en échangeant les rôles de $a$ et $b$ (l'énoncé est symétrique en $a$ et $b$). On a $a + b = \frac{p_1q_2 + p_2q_1}{q_1q_2}$, et $q_2$ divise le numérateur. Donc $q_2$ divise $p_1q_2 + p_2q_1$. Comme $q_2$ divise $p_1q_2$, il divise aussi la différence $(p_1q_2 + p_2q_1) - p_1q_2 = p_2q_1$. Donc $q_2$ divise $p_2q_1$.
On sait que $\text{pgcd}(p_2, q_2) = 1$. Donc, d'après le théorème de Gauss, comme $q_2$ divise $p_2q_1$ et que $q_2$ est premier avec $p_2$, alors $q_2$ divise $q_1$.
On a montré que $q_1$ divise $q_2$ et que $q_2$ divise $q_1$. De plus, $q_1$ et $q_2$ sont positifs. Donc $q_1 = q_2$.

3. Montrons que $a$ et $b$ sont des entiers :

On sait que $q_1 = q_2$. Donc $a = \frac{p_1}{q_1}$ et $b = \frac{p_2}{q_1}$.
$ab = \frac{p_1}{q_1} \times \frac{p_2}{q_1} = \frac{p_1p_2}{q_1^2}$. On sait que $ab$ est un entier, donc $q_1^2$ divise $p_1p_2$.
Supposons que $q_1 \ne 1$. Alors $q_1$ a au moins un facteur premier, notons-le $p$. Comme $q_1^2$ divise $p_1p_2$, alors $p$ divise $p_1p_2$. D'après le théorème de Gauss (ou plutôt, une conséquence pour les nombres premiers), comme $p$ est premier, $p$ divise $p_1$ ou $p$ divise $p_2$.
Si $p$ divise $p_1$ : On a $p$ qui divise $p_1$ et $p$ qui divise $q_1$ (car $p$ est un facteur premier de $q_1$). Cela contredit le fait que $\text{pgcd}(p_1, q_1) = 1$.
Si $p$ divise $p_2$ : Comme $q_1 = q_2$, $p$ divise aussi $q_2$. On a $p$ qui divise $p_2$ et $p$ qui divise $q_2$. Cela contredit le fait que $\text{pgcd}(p_2, q_2) = 1$.
Dans les deux cas, on a une contradiction. Donc notre hypothèse $q_1 \ne 1$ est fausse. Donc $q_1 = 1$. Comme $q_1 = q_2$, on a aussi $q_2 = 1$.
Donc $a = \frac{p_1}{1} = p_1$ et $b = \frac{p_2}{1} = p_2$. Donc $a$ et $b$ sont des entiers.

Conseil : Ce problème est un peu plus difficile. L'astuce consiste à utiliser le théorème de Gauss et le fait que les fractions sont irréductibles pour arriver à une contradiction si les dénominateurs ne sont pas égaux à 1.

Correction :

1. Détermination du chiffrement affine :

On observe le tableau :

- A (0) est codé par C (2). Donc $f(0) = a \times 0 + b \equiv 2 \pmod{26}$. Donc $b \equiv 2 \pmod{26}$.

- B (1) est codé par E (4). Donc $f(1) = a \times 1 + b \equiv 4 \pmod{26}$. Donc $a + b \equiv 4 \pmod{26}$.

Comme $b \equiv 2 \pmod{26}$, on a $a + 2 \equiv 4 \pmod{26}$, soit $a \equiv 2 \pmod{26}$.

Le chiffrement affine est donc $f(x) = 2x + 2 \pmod{26}$. On peut vérifier avec d'autres lettres : D(3) donne $2(3)+2 = 8$ qui est I.

2. La clé (4, 7) est-elle satisfaisante ?

Une clé $(a, b)$ est satisfaisante si le chiffrement est injectif, c'est-à-dire si deux lettres différentes sont codées par deux lettres différentes. Cela se produit si et seulement si $a$ et 26 sont premiers entre eux.

Ici, $a = 4$ et $b = 7$. $\text{pgcd}(4, 26) = 2 \ne 1$. Donc 4 et 26 ne sont pas premiers entre eux. La clé $(4, 7)$ n'est pas satisfaisante.

Vérifions :

$f(x) = 4x + 7 \pmod{26}$.

- Pour A (0) : $f(0) = 4 \times 0 + 7 = 7$, lettre H.

- Pour N (13) : $f(13) = 4 \times 13 + 7 = 52 + 7 = 59 \equiv 7 \pmod{26}$, lettre H.

A et N sont codées par la même lettre, H. Donc la clé n'est pas satisfaisante.

Conseil : Pour qu'un chiffrement affine soit satisfaisant (c'est-à-dire injectif), il faut et il suffit que le coefficient $a$ soit premier avec le module (ici, 26).

Correction :

1. H correspond à la position 7 (A=0, B=1, ..., H=7). $f(7) = 3 \times 7 + 9 = 21 + 9 = 30 \equiv 4 \pmod{26}$. 4 correspond à la lettre E. Donc H est codé par E.

2. Pour que la clé $(a, b)$ soit satisfaisante, il faut que $a$ et 26 soient premiers entre eux. Ici, $a = 3$. $\text{pgcd}(3, 26) = 1$ (3 est premier et ne divise pas 26). Donc la clé $(3, 9)$ est satisfaisante.

Conseil : La valeur de bn'a aucune importance pour la validité (l'injectivité) du chiffrement affine. Seule la valeur de acompte.

Correction :

1. Supposons $\text{pgcd}(a, 26) = 1$. Montrons que la clé $(a, b)$ est satisfaisante, c'est-à-dire que la fonction $f(x) = ax + b \pmod{26}$ est injective.
Soient $x_1$ et $x_2$ deux entiers tels que $f(x_1) \equiv f(x_2) \pmod{26}$. Alors $ax_1 + b \equiv ax_2 + b \pmod{26}$. En soustrayant $b$, $ax_1 \equiv ax_2 \pmod{26}$. Donc $a(x_1 - x_2) \equiv 0 \pmod{26}$, ce qui signifie que 26 divise $a(x_1 - x_2)$.
Comme $\text{pgcd}(a, 26) = 1$, d'après le théorème de Gauss, 26 divise $x_1 - x_2$. Donc $x_1 - x_2 \equiv 0 \pmod{26}$, soit $x_1 \equiv x_2 \pmod{26}$.
Si $x_1$ et $x_2$ représentent des lettres (donc sont entre 0 et 25), alors $x_1 \equiv x_2 \pmod{26}$ implique $x_1 = x_2$. Donc la fonction $f$ est injective, et la clé $(a, b)$ est satisfaisante.

2. a) On suppose $\text{pgcd}(a, 26) = 1$. Montrons qu'il existe un entier $u$ tel que $au \equiv 1 \pmod{26}$.
Comme $a$ et 26 sont premiers entre eux, d'après le théorème de Bézout, il existe des entiers relatifs $u$ et $v$ tels que $au + 26v = 1$. En considérant cette égalité modulo 26, on obtient $au + 26v \equiv au + 0 \equiv au \equiv 1 \pmod{26}$. Donc $u$ est un entier tel que $au \equiv 1 \pmod{26}$ ($u$ est l'inverse de $a$ modulo 26).

b) Fonction de décodage :
On a $y \equiv f(x) \equiv ax + b \pmod{26}$. On veut exprimer $x$ en fonction de $y$.
$y - b \equiv ax \pmod{26}$.
On sait qu'il existe $u$ tel que $au \equiv 1 \pmod{26}$. On multiplie par $u$ : $u(y - b) \equiv u(ax) \equiv (ua)x \equiv 1 \times x \equiv x \pmod{26}$.
Donc $x \equiv u(y - b) \pmod{26}$. La fonction de décodage est $g(y) = u(y - b) \pmod{26}$, où $u$ est l'inverse de $a$ modulo 26.

c) Décoder ZSPS avec la clé $(15, 2)$ :
$a = 15$, $b = 2$. Il faut d'abord trouver l'inverse $u$ de 15 modulo 26. On cherche $u$ tel que $15u \equiv 1 \pmod{26}$. On utilise l'algorithme d'Euclide étendu :
$26 = 1 \times 15 + 11$
$15 = 1 \times 11 + 4$
$11 = 2 \times 4 + 3$
$4 = 1 \times 3 + 1$
$1 = 4 - 1 \times 3 = 4 - 1(11 - 2 \times 4) = 4 - 11 + 2 \times 4 = 3 \times 4 - 11 $

=$ 3(15 - 11) - 11 = 3 \times 15 - 3 \times 11 - 11 = 3 \times 15 - 4 \times 11 $

=$ 3 \times 15 - 4(26 - 15) = 3 \times 15 - 4 \times 26 + 4 \times 15 = 7 \times 15 - 4 \times 26$.
Donc $7 \times 15 - 4 \times 26 = 1$. Donc $7 \times 15 \equiv 1 \pmod{26}$. L'inverse de 15 modulo 26 est $u = 7$.
Fonction de décodage : $g(y) = 7(y - 2) \pmod{26}$.
ZSPS : Z(25), S(18), P(15), S(18).
$g(25) = 7(25 - 2) = 7 \times 23 = 161 \equiv 5 \pmod{26}$ (F)
$g(18) = 7(18 - 2) = 7 \times 16 = 112 \equiv 8 \pmod{26}$ (I)
$g(15) = 7(15 - 2) = 7 \times 13 = 91 \equiv 13 \pmod{26}$ (N)
$g(18) = 7(16) \equiv 8 \pmod{26}$ (I)
Message décodé : FINI.

Conseil : Pour décoder un message chiffré avec un chiffrement affine, il est indispensablede calculer l'inverse du coefficient amodulo 26. L'algorithme d'Euclide étendu est l'outil pour cela.

Correction :

1. L'élève applique le théorème de Gauss, mais la justification est incorrecte. Il faut dire : "Comme $3(x - 2) = 10(y + 5)$, 3 divise $10(y + 5)$. Or, $\text{pgcd}(3, 10) = 1$ (3 est premier et ne divise pas 10), donc, d'après le théorème de Gauss, 3 divise $y + 5$. Donc il existe $k \in \mathbb{Z}$ tel que $y + 5 = 3k$." L'erreur est de dire "3 ne divise pas 10" au lieu de "3 et 10 sont premiers entre eux".

2. L'affirmation "Si $a$ divise $bc$ et $a$ ne divise pas $b$, alors $a$ divise $c$" est fausse en général. Il manque la condition que $a$ et $b$ soient premiers entre eux.
Contre-exemple : $a = 6$, $b = 2$, $c = 3$.
$a | bc$ car $6 | (2 \times 3)$, soit $6 | 6$.
$a \nmid b$ car 6 ne divise pas 2.
Mais $a \nmid c$ car 6 ne divise pas 3.
Ici, $\text{pgcd}(a, b) = \text{pgcd}(6, 2) = 2 \ne 1$. La condition "premiers entre eux" est cruciale pour le théorème de Gauss.

Conseil : Le théorème de Gauss est fondamental en arithmétique. Il faut toujours explicitementmentionner et vérifier que les nombres sont premiers entre eux avant de l'appliquer.

Correction :

L'élève applique correctement le théorème de Gauss pour trouver que 14 divise $y + 2$ et que 9 divise $x - 6$. Il en déduit correctement que $y = -2 + 14k$ et $x = 6 + 9k'$.
L'erreur est dans la conclusion : il donne les solutions sous la forme $(6 + 9k', -2 + 14k)$ avec $k$ et $k'$ entiers indépendants. Or, $k$ et $k'$ sont liés par l'équation de départ. Il faut exprimer les solutions avec un seul paramètre.
Reprenons l'équation : $14(x - 6) = 9(y + 2)$.
On sait que $x = 6 + 9k'$. Substituons : $14(6 + 9k' - 6) = 9(y + 2)$, soit $14(9k') = 9(y + 2)$. On simplifie par 9 : $14k' = y + 2$, donc $y = -2 + 14k'$.
On peut renommer $k'$ en $k$ : $y = -2 + 14k$. Donc les solutions sont de la forme $(x, y) = (6 + 9k, -2 + 14k)$, où $k$ est un entier relatif quelconque.
On peut aussi partir de $y = -2 + 14k$ et substituer : $14(x - 6) = 9(-2 + 14k + 2) = 9(14k)$. On simplifie par 14 : $x - 6 = 9k$, donc $x = 6 + 9k$. On retrouve la même forme de solution.
Vérification: $14(6 + 9k - 6) = 14(9k) = 126k$. $9(-2 + 14k + 2) = 9(14k) = 126k$. Les deux membres sont bien égaux.

Conseil : Dans la résolution d'équations diophantiennes, après avoir appliqué le théorème de Gauss, il faut toujoursrevenir à l'équation de départ pour exprimer les solutions avec un seul paramètre.

Correction :

Supposons que l'équation $ax \equiv 2 \pmod{n}$ deux ait solutions $x_1$ et $x_2$ dans l'intervalle $[0; n - 1]$. Alors :
$ax_1 \equiv 2 \pmod{n}$ et $ax_2 \equiv 2 \pmod{n}$.
Donc $ax_1 \equiv ax_2 \pmod{n}$. Cela signifie que $a(x_1 - x_2) \equiv 0 \pmod{n}$, c'est-à-dire que $n$ divise $a(x_1 - x_2)$.
On sait que $\text{pgcd}(a, n) = 1$. Donc, d'après le théorème de Gauss, comme $n$ divise $a(x_1 - x_2)$ et que $a$ est premier avec $n$, alors $n$ divise $x_1 - x_2$. Donc $x_1 - x_2 \equiv 0 \pmod{n}$, soit $x_1 \equiv x_2 \pmod{n}$.
Comme $x_1$ et $x_2$ sont dans l'intervalle $[0; n - 1]$, cela signifie que $0 \le x_1 \le n - 1$ et $0 \le x_2 \le n - 1$. Donc $-(n - 1) \le -x_2 \le 0$. En additionnant, onobtient :
$-(n - 1) \le x_1 - x_2 \le n - 1$.
Or, $x_1 - x_2$ est un multiple de $n$ (car $x_1 \equiv x_2 \pmod{n}$). Le seul multiple de $n$ dans l'intervalle $[-(n - 1); n - 1]$ est 0. Donc $x_1 - x_2 = 0$, soit $x_1 = x_2$.
Conclusion : Si l'équation à deux solutions dans $[0; n - 1]$, alors elles sont égales. Donc l'équation à au plusune solution dans $[0; n - 1]$. (En fait, comme $\text{pgcd}(a, n) = 1$, on peut montrer qu'il ya exactementune solution, grâce au théorème de Bézout).

Conseil : Ce résultat est important pour les fonctions de chiffrement/déchiffrement, car il garantit l'unicité de la solution (et donc la possibilité de déchiffrer).

Correction :

On veut montrer que $n^5 - n$ est divisible par $30 = 2 \times 3 \times 5$. Comme 2, 3, et 5 sont premiers entre eux deux à deux, il suffit de montrer que $n^5 - n$ est divisible par 2, par 3, et par 5.
$n^5 - n = n(n^4 - 1) = n(n^2 - 1)(n^2 + 1) = n(n - 1)(n + 1)(n^2 + 1) = (n - 1)n(n + 1)(n^2 + 1)$.

- Divisibilité par 2 : $(n - 1)n(n + 1)$ est le produit de trois entiers consécutifs. Donc il y a au moins un nombre pair, et le produit est divisible par 2.

- Divisibilité par 3 : $(n - 1)n(n + 1)$ est le produit de trois entiers consécutifs, donc il y a un multiple de 3. Donc le produit est divisible par 3.

- Divisibilité par 5 : On considère les restes possibles de $n$ modulo 5 :

Si $n \equiv 0 \pmod{5}$, alors $n^5 - n \equiv 0 \pmod{5}$.
Si $n \equiv 1 \pmod{5}$, alors $n^5 - n \equiv 1^5 - 1 \equiv 0 \pmod{5}$.
Si $n \equiv 2 \pmod{5}$, alors $n^5 - n \equiv 2^5 - 2 \equiv 32 - 2 \equiv 30 \equiv 0 \pmod{5}$.
Si $n \equiv 3 \pmod{5}$, alors $n^5 - n \equiv 3^5 - 3 \equiv 243 - 3 \equiv 240 \equiv 0 \pmod{5}$.
Si $n \equiv 4 \pmod{5}$, alors $n^5 - n \equiv 4^5 - 4 \equiv 1024 - 4 \equiv 1020 \equiv 0 \pmod{5}$.
Dans tous les cas, $n^5 - n \equiv 0 \pmod{5}$, donc $n^5 - n$ est divisible par 5.
On peut aussi remarquer que si $n \not\equiv 0, 1, -1 \pmod 5$ alors $n \equiv 2,3 \pmod 5$ donc $n^2 \equiv 4 \equiv -1 \pmod{5}$ et $n^2+1 \equiv 0 \pmod 5$.
Conclusion : $n^5 - n$ est divisible par 2, 3, et 5, donc par $2 \times 3 \times 5 = 30$.

Conseil : Pour montrer la divisibilité par un produit de nombres premiers entre eux, on peut étudier les restes possibles modulo chacun de ces nombres premiers.

Correction :

1. a) Soit $d = \text{pgcd}(p, a)$. Alors $d$ divise $p$ et $d$ divise $a$. Comme $p$ est premier, ses seuls diviseurs positifs sont 1 et $p$. Donc $d = 1$ ou $d = p$.
Si $d = p$, alors $p$ divise $a$ (car $d$ divise $a$), ce qui contredit l'hypothèse $p \nmid a$. Donc $d \ne p$. La seule possibilité est $d = 1$. Donc $\text{pgcd}(p, a) = 1$.

b) Si $p$ divise $ab$, sur deux cas :
Si $p$ divise $a$, alors sur un bien "$p$ divise $a$ ou $p$ divise $b$".
Si $p$ ne divise pas $a$, alors, d'après la question 1a, $\text{pgcd}(p, a) = 1$. Comme $p$ divise $ab$ et que $p$ est premier avec $a$, d'après le théorème de Gauss, $p$ divise $b$.
Dans tous les cas, si $p$ divise $ab$, alors $p$ divise $a$ ou $p$ divise $b$.

2. Si $p$ divise $a^2 = a \times a$, alors d'après la question 1b (avec $b = a$), $p$ divise $a$ ou $p$ divise $a$. Donc $p$ divise $a$.

3. Si $p$ divise $ab$, alors d'après 1b, $p$ divise $a$ ou $p$ divise $b$.
Si $p$ divise $a$ : Comme $a$ est premier, ses seuls diviseurs positifs sont 1 et $a$. Donc $p = 1$ ou $p = a$. Comme $p$ est premier, $p \ne 1$. Donc $p = a$.
Si $p$ divise $b$ : Comme $b$ est premier, ses seuls diviseurs positifs sont 1 et $b$. Donc $p = 1$ ou $p = b$. Comme $p$ est premier, $p \ne 1$. Donc $p = b$.
Donc si $p$ diviser $ab$, alors $p = a$ ou $p = b$.

Conseil : Ces propriétés sont fondamentales pour les nombres premiers.Elles découlent du théorème de Gauss et sont souvent utilisées dans des raisonnements plus complexes.

Correction :

1. Testons les entiers de 1 à 9 :
1 est puissant (pas de diviseur premier).
2 n'est pas puissant ($2^2 = 4$ ne divise pas 2).
3 n'est pas puissant.
4 = $2^2$ est puissant (diviseur premier 2, $2^2$ divise 4).
5 n'est pas puissant.
6 = $2 \times 3$ n'est pas puissant ($2^2$ ne divise pas 6).
7 n'est pas puissant.
8 = $2^3$ est puissant (diviseur premier 2, $2^2 = 4$ divise 8).
9 = $3^2$ est puissant (diviseur premier 3, $3^2$ divise 9).
8 et 9 sont deux entiers consécutifs puissants inférieurs à 10.

2. Soit $n = a^2b^3$. Soit $p$ un diviseur premier de $n$. Alors $p$ divise $a^2b^3$. Donc, d'après le théorème de Gauss généralisé (ou l'exercice 18), $p$ divise $a^2$ ou $p$ divise $b^3$.
Si $p$ divise $a^2$, alors d'après l'exercice 18 question 2, $p$ divise $a$. Donc il existe $k$ tel que $a = pk$. Alors $a^2 = (pk)^2 = p^2k^2$, donc $p^2$ divise $a^2$. Comme $a^2$ divise $a^2b^3 = n$, alors $p^2$ divise $n$.
Si $p$ divise $b^3$, on décompose en plusieurs fois. Si $p$ divise $b \times b^2$ alors $p$ divise $b$ ou $p$ divise $b^2$. Si $p$ divise $b^2$ alors $p$ divise $b$. Donc, $p$ divise $b$. Il existe $k$ tel que $b=pk$, alors $b^3 = (pk)^3=p^3k^3$ et $p^2$ divise $p^3$ donc $p^2$ divise $b^3$ . Comme $b^3$ divise $a^2b^3 = n$, alors $p^2$ divise $n$.
Dans tous les cas, si $p$ est un diviseur premier de $n = a^2b^3$, alors $p^2$ divise $n$. Donc $n$ est puissant.

3. $x^2$ : Soit $p$ un diviseur premier de $x^2$. Alors, d'après l'exercice 18 question 2, $p$ divise $x$. Donc il existe $k$ tel que $x = pk$. Alors $x^2 = (pk)^2 = p^2k^2$, donc $p^2$ divise $x^2$. Donc $x^2$ est puissant.
$8x^2 = 2^3x^2$ : Soit $p$ un diviseur premier de $8x^2$. Alors $p$ divise $2^3x^2$. Donc $p$ divise $2^3$ ou $p$ divise $x^2$.
- Si $p$ divise $2^3$, alors $p = 2$ (car 2 est le seul diviseur premier de $2^3$). Alors $p^2 = 2^2 = 4$, qui divise $8x^2$.
- Si $p$ divise $x^2$, alors d'après la question précédente, $p^2$ divise $x^2$. Comme $x^2$ divise $8x^2$, alors $p^2$ divise $8x^2$.
Dans tous les cas, si $p$ est un diviseur premier de $8x^2$, alors $p^2$ divise $8x^2$. Donc $8x^2$ est puissant.

Conseil : La notion de nombre puissant est un bon exemple pour s'entraîner à manipuler les diviseurs premiers et le théorème de Gauss.