Exercices corrigés : Arithmétique (Terminale)

1. On a $13 \times 76 = 988$ et $13 \times 77 = 1001$. Donc $988 \leqslant 1000 < 1001$ et $$1000 = 13 \times 76 + 12 \quad \text{avec} \quad 0 \leqslant 12 < 13.$$ Le quotient est $76$ et le reste est $12$.

2. Le quotient est le plus grand entier $q$ tel que $7q \leqslant -100$. Or $7 \times (-14) = -98 > -100$ et $7 \times (-15) = -105 \leqslant -100$. Donc $$-100 = 7 \times (-15) + 5 \quad \text{avec} \quad 0 \leqslant 5 < 7.$$ Le quotient est $-15$ et le reste est $5$. L'écriture $-100 = 7 \times (-14) - 2$ est exacte mais ce n'est pas la division euclidienne, car $-2 < 0$.

3. Par hypothèse, $a \equiv 5 \;[7]$. La congruence est compatible avec la multiplication et l'addition, donc $$3a + 4 \equiv 3 \times 5 + 4 = 19 \;[7].$$ Or $19 = 2 \times 7 + 5$, donc $3a + 4 \equiv 5 \;[7]$. Comme $0 \leqslant 5 < 7$, le reste de la division euclidienne de $3a + 4$ par $7$ est $5$.

1. Modulo $13$ : $5^2 = 25 = 13 + 12$, donc $5^2 \equiv 12 \equiv -1 \;[13]$. Par suite $5^4 = (5^2)^2 \equiv (-1)^2 = 1 \;[13]$.

On divise l'exposant par $4$ : $2027 = 4 \times 506 + 3$. Donc $$5^{2027} = \left(5^4\right)^{506} \times 5^3 \equiv 1^{506} \times 125 = 125 \;[13].$$ Or $125 = 13 \times 9 + 8$, donc $5^{2027} \equiv 8 \;[13]$. Comme $0 \leqslant 8 < 13$, le reste cherché est $8$.

2. Le chiffre des unités d'un entier naturel est son reste dans la division par $10$. Modulo $10$ : $$7^2 = 49 \equiv 9, \quad 7^3 \equiv 9 \times 7 = 63 \equiv 3, \quad 7^4 \equiv 3 \times 7 = 21 \equiv 1.$$ On a $2026 = 4 \times 506 + 2$, donc $$7^{2026} = \left(7^4\right)^{506} \times 7^2 \equiv 1 \times 49 \equiv 9 \;[10].$$ Le chiffre des unités de $7^{2026}$ est $9$.

1. Algorithme d'Euclide : $$\begin{aligned} 1386 &= 2 \times 588 + 210 \\ 588 &= 2 \times 210 + 168 \\ 210 &= 1 \times 168 + 42 \\ 168 &= 4 \times 42 + 0 \end{aligned}$$ Le dernier reste non nul est $42$, donc $\mathrm{PGCD}(1386, 588) = 42$.

2. On écrit les restes : $42 = 210 - 168$, $168 = 588 - 2 \times 210$, $210 = 1386 - 2 \times 588$. On remonte : $$\begin{aligned} 42 &= 210 - 168 = 210 - (588 - 2 \times 210) = 3 \times 210 - 588 \\ &= 3(1386 - 2 \times 588) - 588 = 3 \times 1386 - 7 \times 588. \end{aligned}$$ Vérification : $3 \times 1386 = 4158$, $7 \times 588 = 4116$ et $4158 - 4116 = 42$. On peut prendre $u = 3$ et $v = -7$.

3. On a $1386 = 42 \times 33$ et $588 = 42 \times 14$. En divisant la relation $3 \times 1386 - 7 \times 588 = 42$ par $42 \neq 0$ : $$3 \times 33 - 7 \times 14 = 1.$$ Vérification : $99 - 98 = 1$. D'après le théorème de Bézout, $33$ et $14$ sont premiers entre eux.

On a $(n+1)(n-1) = n^2 - 1$, donc pour tout entier $n$ : $$n^2 + 5 = (n+1)(n-1) + 6.$$

• Si $n + 1 \mid n^2 + 5$ : comme $n+1$ divise aussi $(n+1)(n-1)$, il divise la différence $n^2 + 5 - (n+1)(n-1) = 6$.
• Réciproquement, si $n + 1 \mid 6$ : $n+1$ divise $(n+1)(n-1)$ et $6$, donc il divise leur somme $n^2 + 5$.

Ainsi $n + 1 \mid n^2 + 5$ si et seulement si $n + 1 \mid 6$. (Le cas $n = -1$ est exclu dans les deux cas, car $0$ ne divise ni $6$ ni $n^2 + 5 = 6$.)

Les diviseurs de $6$ sont $-6, -3, -2, -1, 1, 2, 3, 6$. Donc $n + 1 \in \{-6 ; -3 ; -2 ; -1 ; 1 ; 2 ; 3 ; 6\}$, c'est-à-dire $$n \in \{-7 ; -4 ; -3 ; -2 ; 0 ; 1 ; 2 ; 5\}.$$

Contrôle sur deux valeurs : pour $n = 5$, $6 \mid 30$ ; pour $n = -7$, $-6 \mid 54$. L'équivalence établie garantit que toutes ces valeurs conviennent.

1. $A_0 = 3^2 + 2^1 = 11$ et $A_1 = 3^4 + 2^7 = 81 + 128 = 209 = 11 \times 19$.

2. Soit $n \in \mathbb{N}$. On a $3^{2n+2} = 9^{n+1} = 9 \times 9^n$ et $2^{6n+1} = 2 \times (2^6)^n = 2 \times 64^n$.

Or $64 = 5 \times 11 + 9$, donc $64 \equiv 9 \;[11]$ et $64^n \equiv 9^n \;[11]$. Ainsi $$A_n \equiv 9 \times 9^n + 2 \times 9^n = 11 \times 9^n \equiv 0 \;[11].$$ Donc $11$ divise $A_n$ pour tout $n \in \mathbb{N}$.

3. Comme $n + 1 \geqslant 1$, $3^{2n+2} = 9^{n+1} = 9 \times 9^n \equiv 0 \;[9]$.

De plus $64 = 7 \times 9 + 1$, donc $64 \equiv 1 \;[9]$ et $2^{6n+1} = 2 \times 64^n \equiv 2 \;[9]$.

Ainsi $A_n \equiv 0 + 2 = 2 \;[9]$. Comme $0 \leqslant 2 < 9$, le reste de la division de $A_n$ par $9$ est $2$ pour tout $n$. Contrôle : $A_0 = 11 = 9 + 2$ et $A_1 = 209 = 9 \times 23 + 2$.

1. Si $n \equiv r \;[8]$, alors $n^2 \equiv r^2 \;[8]$. On calcule : $0^2 = 0$, $1^2 = 1$, $2^2 = 4$, $3^2 = 9 \equiv 1$, $4^2 = 16 \equiv 0$, $5^2 = 25 \equiv 1$, $6^2 = 36 \equiv 4$, $7^2 = 49 \equiv 1$.

Un carré est donc congru à $0$, $1$ ou $4$ modulo $8$.

2. $a^2$, $b^2$, $c^2$ sont chacun congrus à $0$, $1$ ou $4$ modulo $8$. L'ordre ne compte pas dans la somme ; on liste toutes les combinaisons :

• $0+0+0 = 0$ ; $0+0+1 = 1$ ; $0+1+1 = 2$ ; $1+1+1 = 3$ ;
• $0+0+4 = 4$ ; $0+1+4 = 5$ ; $1+1+4 = 6$ ;
• $0+4+4 = 8 \equiv 0$ ; $1+4+4 = 9 \equiv 1$ ; $4+4+4 = 12 \equiv 4$.

Les restes obtenus sont $0, 1, 2, 3, 4, 5, 6$ : jamais $7$. Donc $a^2 + b^2 + c^2 \not\equiv 7 \;[8]$.

3. $2023 = 8 \times 252 + 7$, donc $2023 \equiv 7 \;[8]$. D'après la question 2, $2023$ ne peut pas s'écrire comme somme de trois carrés d'entiers.

1. Si $a = 1$, $M_a = 1$ divise tout entier. Supposons $a \geqslant 2$ ; alors $M_a = 2^a - 1 \geqslant 3$. Comme $M_a$ divise $2^a - 1$, on a $2^a \equiv 1 \;[M_a]$. Par compatibilité avec les puissances : $$2^{ab} = \left(2^a\right)^b \equiv 1^b = 1 \;[M_a].$$ Donc $M_a$ divise $2^{ab} - 1 = M_{ab}$.

2. On raisonne par contraposée. Supposons $n \geqslant 2$ non premier : $n = ab$ avec $2 \leqslant a \leqslant b \leqslant n - 1$. D'après la question 1, $M_a$ divise $M_n$. De plus :

• $a \geqslant 2$, donc $M_a \geqslant 2^2 - 1 = 3 > 1$ ;
• $a < n$, donc $2^a < 2^n$ et $M_a < M_n$.

$M_n$ admet donc un diviseur positif différent de $1$ et de $M_n$ : $M_n$ n'est pas premier. Par contraposée, si $M_n$ est premier, alors $n$ est premier.

3. a) $2^5 = 32 = 23 + 9$, donc $2^5 \equiv 9 \;[23]$. Puis $2^{10} \equiv 81 = 3 \times 23 + 12$, donc $2^{10} \equiv 12 \;[23]$, et $2^{11} \equiv 24 \equiv 1 \;[23]$. Ainsi $23$ divise $2^{11} - 1 = M_{11}$. On a d'ailleurs $M_{11} = 2047 = 23 \times 89$.

b) $11$ est premier, mais $M_{11} = 23 \times 89$ n'est pas premier. La réciproque est fausse.

4. $15 = 3 \times 5$. D'après la question 1, $M_3 = 7$ et $M_5 = 31$ divisent $M_{15}$. Ces deux entiers sont premiers. Donc $7$ et $31$ sont deux diviseurs premiers de $M_{15}$. (On peut contrôler : $M_{15} = 32767 = 7 \times 31 \times 151$.)

1. a) $n \equiv 3 \;[7]$ équivaut à $5k + 2 \equiv 3 \;[7]$, soit $5k \equiv 1 \;[7]$.

• Si $5k \equiv 1 \;[7]$ : on multiplie par $3$ (car $5 \times 3 = 15 \equiv 1 \;[7]$), d'où $15k \equiv 3 \;[7]$, soit $k \equiv 3 \;[7]$.
• Si $k \equiv 3 \;[7]$ : $5k \equiv 15 \equiv 1 \;[7]$.

Donc $n \equiv 3 \;[7]$ si et seulement si $k \equiv 3 \;[7]$.

b) Avec $k = 3$ : $n = 17$. On a $17 = 3 \times 5 + 2$ et $17 = 2 \times 7 + 3$, donc $17$ est solution de $(S)$.

2. Supposons $n$ solution. Alors $n \equiv 2 \equiv 17 \;[5]$ et $n \equiv 3 \equiv 17 \;[7]$, donc $5 \mid n - 17$ et $7 \mid n - 17$. Comme $5$ et $7$ sont premiers entre eux, le corollaire du théorème de Gauss donne $35 \mid n - 17$, soit $n \equiv 17 \;[35]$.

Réciproquement, si $n = 17 + 35j$ avec $j \in \mathbb{Z}$, alors $n = 17 + 5 \times 7j \equiv 17 \equiv 2 \;[5]$ et $n = 17 + 7 \times 5j \equiv 17 \equiv 3 \;[7]$.

Les solutions de $(S)$ sont les entiers $n = 17 + 35j$, $j \in \mathbb{Z}$.

3. Le nombre $N$ de personnes vérifie $(S)$, donc $N = 17 + 35j$ avec $j \in \mathbb{Z}$. La condition $100 \leqslant N \leqslant 200$ équivaut à $83 \leqslant 35j \leqslant 183$. Or $35 \times 2 = 70 < 83$, $35 \times 3 = 105$, $35 \times 5 = 175 \leqslant 183$ et $35 \times 6 = 210 > 183$. Donc $j \in \{3 ; 4 ; 5\}$ et $N \in \{122 ; 157 ; 192\}$.

Division par $4$ : $122 = 4 \times 30 + 2$, $157 = 4 \times 39 + 1$, $192 = 4 \times 48 + 0$. Seul $157$ donne un reste égal à $1$.

Le groupe compte $157$ personnes.

1. C, O, D, E ont pour rangs $2$, $14$, $3$, $4$.

• $9 \times 2 + 4 = 22$, donc $y = 22$ : W.
• $9 \times 14 + 4 = 130 = 5 \times 26$, donc $y = 0$ : A.
• $9 \times 3 + 4 = 31 = 26 + 5$, donc $y = 5$ : F.
• $9 \times 4 + 4 = 40 = 26 + 14$, donc $y = 14$ : O.

CODE est chiffré WAFO.

2. a) Algorithme d'Euclide : $$\begin{aligned} 26 &= 2 \times 9 + 8 \\ 9 &= 1 \times 8 + 1 \\ 8 &= 8 \times 1 + 0 \end{aligned}$$ Donc $\mathrm{PGCD}(26, 9) = 1$. On remonte : $1 = 9 - 8 = 9 - (26 - 2 \times 9) = 3 \times 9 - 26$. Ainsi $u = 3$ et $v = -1$. Vérification : $27 - 26 = 1$.

Par conséquent $9 \times 3 = 27 \equiv 1 \;[26]$ : $3$ est un inverse de $9$ modulo $26$.

b) Supposons $y \equiv 9x + 4 \;[26]$. En multipliant par $3$ : $3y \equiv 27x + 12 \equiv x + 12 \;[26]$, donc $x \equiv 3y - 12 \;[26]$. Comme $-12 = 14 - 26$, $x \equiv 3y + 14 \;[26]$.

Réciproquement, supposons $x \equiv 3y + 14 \;[26]$. En multipliant par $9$ : $9x \equiv 27y + 126 \;[26]$. Or $27 \equiv 1$ et $126 = 4 \times 26 + 22 \equiv 22 \;[26]$, donc $9x \equiv y + 22 \;[26]$, soit $y \equiv 9x - 22 \equiv 9x + 4 \;[26]$.

L'équivalence est démontrée.

c) On calcule le reste de $3y + 14$ modulo $26$ pour chaque lettre :

(En effet $41 = 26 + 15$, $86 = 3 \times 26 + 8$, $38 = 26 + 12$, $56 = 2 \times 26 + 4$.) Le message déchiffré est PRIME.

3. A : $13 \times 0 + 4 = 4$, codé E. C : $13 \times 2 + 4 = 30 = 26 + 4$, codé E aussi. Deux lettres distinctes ont le même code : à la réception de E, on ne peut pas savoir s'il s'agit de A ou de C. Ce chiffrement n'est pas déchiffrable, ce qui est cohérent avec $\mathrm{PGCD}(13, 26) = 13 \neq 1$.

4. D'après le cours, le chiffrement est déchiffrable si et seulement si $\mathrm{PGCD}(a, 26) = 1$. Comme $26 = 2 \times 13$ avec $2$ et $13$ premiers, cela équivaut à : $a$ impair et $a \neq 13$. Les valeurs sont $1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25$ : il y en a $12$.