Exercices corrigés : Arithmétique dans $\mathbb{Z}$ (Prépa, 1re année)

1. On a $-100/7 \approx -14{,}29$, donc $q = \lfloor -100/7 \rfloor = -15$ et $r = -100 - 7 \times (-15) = -100 + 105 = 5$. Comme $0 \leqslant 5 < 7$ : $$-100 = 7 \times (-15) + 5.$$ Le quotient est $-15$, le reste est $5$.

2. $17 \times 120 = 2040$, donc $17 \times 119 = 2023$. Ainsi $2025 = 17 \times 119 + 2$ avec $0 \leqslant 2 < 17$. Le quotient est $119$, le reste est $2$.

3. On part de $a = bq + r$ avec $0 \leqslant r < b$, d'où $-a = b(-q) - r$.

• Si $r = 0$ : $-a = b(-q) + 0$. Le couple $(-q, 0)$ vérifie les conditions de la division euclidienne, donc par unicité le quotient est $-q$ et le reste est $0$.
• Si $r \neq 0$ : on écrit $-a = b(-q) - b + b - r = b(-q-1) + (b - r)$. Comme $1 \leqslant r \leqslant b - 1$, on a $1 \leqslant b - r \leqslant b - 1$, donc $0 \leqslant b - r < b$. Par unicité, le quotient est $-q-1$ et le reste est $b - r$.

Vérification : $17 = 5 \times 3 + 2$, donc la division de $-17$ par $5$ a pour quotient $-3-1 = -4$ et pour reste $5 - 2 = 3$. On retrouve $-17 = 5 \times (-4) + 3$.

1. On applique l'algorithme d'Euclide : $$4199 = 2 \times 1729 + 741, \qquad 1729 = 2 \times 741 + 247, \qquad 741 = 3 \times 247 + 0.$$ Le dernier reste non nul est $247$, donc $4199 \wedge 1729 = 247$.

2. On remonte les divisions : $247 = 1729 - 2 \times 741$ et $741 = 4199 - 2 \times 1729$. Donc $$247 = 1729 - 2(4199 - 2 \times 1729) = 5 \times 1729 - 2 \times 4199.$$ Le couple $(u, v) = (-2, 5)$ convient. Vérification : $5 \times 1729 = 8645$, $2 \times 4199 = 8398$ et $8645 - 8398 = 247$.

3. Comme $(a \wedge b)(a \vee b) = ab$ pour $a, b > 0$ : $$a \vee b = \frac{4199 \times 1729}{247}.$$ Or $1729 = 7 \times 247$, donc $a \vee b = 4199 \times 7 = 29393$.

4. On a $247 = 13 \times 19$, avec $13$ et $19$ premiers. Puis $1729 = 7 \times 247 = 7 \times 13 \times 19$ et $4199 = 17 \times 247 = 13 \times 17 \times 19$ (en effet $17 \times 247 = 4199$). Avec les valuations :

• $a \wedge b = 7^{0} \times 13^{1} \times 17^{0} \times 19^{1} = 247$ (exposants minimaux) ;
• $a \vee b = 7 \times 13 \times 17 \times 19 = 7 \times 4199 = 29393$ (exposants maximaux).

On retrouve les résultats précédents.

1. Pour tout $n \in \mathbb{N}$ : $$5(8n+5) - 8(5n+3) = 40n + 25 - 40n - 24 = 1.$$ Par le théorème de Bézout, $(8n+5) \wedge (5n+3) = 1$. Le dénominateur $5n+3$ est strictement positif et premier avec le numérateur : la fraction est irréductible.

2. Pour tout $n \in \mathbb{Z}$, $(n^2 + n + 1) - n(n+1) = 1$, c'est-à-dire $1 \times (n^2+n+1) + (-n) \times (n+1) = 1$. Par le théorème de Bézout, $(n^2 + n + 1) \wedge (n+1) = 1$.

3. On a $n^2 + 2n + 1 = (n+1)^2$. D'après le cours, si $a \wedge b = 1$, alors $a \wedge b^k = 1$ pour tout $k \in \mathbb{N}$. Avec $a = n^2 + n + 1$ et $b = n + 1$, la question 2 donne $(n^2 + n + 1) \wedge (n+1)^2 = 1$, soit $(n^2+n+1) \wedge (n^2 + 2n + 1) = 1$.

1. Soit $n \in \mathbb{N}$ ; $n + 3 \geqslant 3$, donc $d_n$ est bien défini et $d_n \geqslant 1$. Comme $d_n$ divise $n+3$ et $2n+1$, il divise $$2(n+3) - (2n+1) = 5.$$ Les diviseurs positifs de $5$ sont $1$ et $5$, donc $d_n \in \{1, 5\}$.

Si $d_n = 5$, alors $5 \mid n + 3$, donc $n \equiv -3 \equiv 2 \;[5]$.

Réciproquement, si $n = 5k + 2$ avec $k \in \mathbb{N}$, alors $n + 3 = 5(k+1)$ et $2n + 1 = 10k + 5 = 5(2k+1)$. Donc $5$ divise les deux entiers, puis $5 \mid d_n$ et $d_n = 5$.

Conclusion : $d_n = 5$ si $n \equiv 2 \;[5]$, et $d_n = 1$ sinon.

2. Soit $n \in \mathbb{Z}$ et $\delta = (n^2+1) \wedge (n+1)$ ; comme $n^2 + 1 \geqslant 1$, $\delta \geqslant 1$. L'entier $\delta$ divise $$(n^2 + 1) - (n-1)(n+1) = n^2 + 1 - n^2 + 1 = 2,$$ donc $\delta \in \{1, 2\}$.

• Si $n$ est impair, $n^2 + 1$ et $n + 1$ sont pairs, donc $2 \mid \delta$ et $\delta = 2$.
• Si $n$ est pair, $n + 1$ est impair, donc $2 \nmid n+1$ et $\delta \neq 2$ : $\delta = 1$.

1. Algorithme d'Euclide : $$391 = 1 \times 323 + 68, \quad 323 = 4 \times 68 + 51, \quad 68 = 1 \times 51 + 17, \quad 51 = 3 \times 17 + 0.$$ Donc $323 \wedge 391 = 17$. On a d'ailleurs $323 = 17 \times 19$ et $391 = 17 \times 23$.

2. Pour tous $x, y \in \mathbb{Z}$, $17$ divise $323x + 391y$. Comme $100 = 5 \times 17 + 15$, $17 \nmid 100$ : l'équation n'a aucune solution.

3. On a $85 = 5 \times 17$, donc $(E)$ équivaut à $19x + 23y = 5$, avec $19 \wedge 23 = 1$.

Solution particulière. Euclide sur $23$ et $19$ : $23 = 1 \times 19 + 4$, $19 = 4 \times 4 + 3$, $4 = 1 \times 3 + 1$. En remontant : $$1 = 4 - 3 = 4 - (19 - 4 \times 4) = 5 \times 4 - 19 = 5(23 - 19) - 19 = 5 \times 23 - 6 \times 19.$$ En multipliant par $5$ : $19 \times (-30) + 23 \times 25 = 5$. Le couple $(-30, 25)$ est solution.

Analyse. Si $(x, y)$ est solution, alors $19x + 23y = 19 \times (-30) + 23 \times 25$, d'où $19(x + 30) = 23(25 - y)$. Ainsi $23 \mid 19(x+30)$ et $23 \wedge 19 = 1$, donc $23 \mid x + 30$ par le lemme de Gauss : $x = -30 + 23k$ avec $k \in \mathbb{Z}$. Alors $19 \times 23k = 23(25 - y)$, soit $y = 25 - 19k$.

Synthèse. Pour tout $k \in \mathbb{Z}$, $19(-30 + 23k) + 23(25 - 19k) = -570 + 575 = 5$.

En posant $k = j + 1$, on obtient une écriture plus simple : l'ensemble des solutions de $(E)$ est $$\{(-7 + 23j,\ 6 - 19j),\ j \in \mathbb{Z}\}.$$ Vérification pour $j = 0$ : $323 \times (-7) + 391 \times 6 = -2261 + 2346 = 85$.

4. Une solution vérifie $x \geqslant 0$ si et seulement si $23j \geqslant 7$, soit $j \geqslant 1$, et $y \geqslant 0$ si et seulement si $19j \leqslant 6$, soit $j \leqslant 0$. Ces conditions sont incompatibles : $(E)$ n'a aucune solution dans $\mathbb{N}^2$. On le voit aussi directement : si $y \geqslant 1$, $323x + 391y \geqslant 391 > 85$ ; si $y = 0$, $323x = 85$ est impossible.

1. Euclide : $60 = 3 \times 17 + 9$, $17 = 1 \times 9 + 8$, $9 = 1 \times 8 + 1$. Donc $60 \wedge 17 = 1$ et $17$ est inversible modulo $60$. En remontant : $$1 = 9 - 8 = 9 - (17 - 9) = 2 \times 9 - 17 = 2(60 - 3 \times 17) - 17 = 2 \times 60 - 7 \times 17.$$ Donc $17 \times (-7) \equiv 1 \;[60]$, et l'inverse de $17$ est $-7 \equiv 53 \;[60]$. Vérification : $17 \times 53 = 901 = 15 \times 60 + 1$.

2. Si $17x \equiv 5 \;[60]$, en multipliant par $53$ : $x \equiv 53 \times 5 = 265 \;[60]$. Réciproquement, si $x \equiv 265 \;[60]$, en multipliant par $17$ : $17x \equiv 17 \times 53 \times 5 \equiv 5 \;[60]$. Comme $265 = 4 \times 60 + 25$ : $$17x \equiv 5 \;[60] \iff x \equiv 25 \;[60].$$ Vérification : $17 \times 25 = 425 = 7 \times 60 + 5$. Les solutions sont les $x = 25 + 60k$, $k \in \mathbb{Z}$.

3. On ne peut pas simplifier par $2$ sans précaution, car $2 \wedge 10 \neq 1$. On revient à la définition : $$6x \equiv 4 \;[10] \iff 10 \mid 2(3x - 2) \iff 5 \mid 3x - 2 \iff 3x \equiv 2 \;[5].$$ Or $3 \times 2 = 6 \equiv 1 \;[5]$ : l'inverse de $3$ modulo $5$ est $2$. Comme précédemment, $3x \equiv 2 \;[5] \iff x \equiv 4 \;[5]$. Les solutions sont les $x = 4 + 5k$, $k \in \mathbb{Z}$ ; modulo $10$, ce sont les classes de $4$ et de $9$. Vérification : $6 \times 4 = 24 \equiv 4$ et $6 \times 9 = 54 \equiv 4 \;[10]$.

4. Si $6x \equiv 5 \;[10]$, il existe $k \in \mathbb{Z}$ tel que $6x - 5 = 10k$, soit $5 = 6x - 10k = 2(3x - 5k)$. Le membre de droite est pair et $5$ est impair : contradiction. La congruence n'a aucune solution, ce qui est cohérent avec $6 \wedge 10 = 2 \nmid 5$.

1. Si $q = 0$, $2^0 - 1 = 0$ est divisible par tout entier. Si $q \geqslant 1$, avec $X = 2^n$ : $$X^q - 1 = (X - 1)(1 + X + \dots + X^{q-1}),$$ donc $2^n - 1 \mid 2^{nq} - 1$.

2. On a $2^m - 1 = 2^r \cdot 2^{nq} - 2^r + 2^r - 1 = 2^r(2^{nq} - 1) + (2^r - 1)$. D'après 1, $2^{nq} - 1 = (2^n - 1)Q$ avec $Q \in \mathbb{N}$, donc $$2^m - 1 = (2^n - 1) \cdot 2^r Q + (2^r - 1).$$ Comme $n \geqslant 1$, $2^n - 1 \neq 0$. Le lemme d'Euclide (si $A = BQ' + R$ avec $(A,B) \neq (0,0)$, alors $A \wedge B = B \wedge R$) donne $(2^m - 1) \wedge (2^n - 1) = (2^n - 1) \wedge (2^r - 1)$.

3. On montre par récurrence forte sur $n \in \mathbb{N}$ la propriété $\mathcal{H}(n)$ : pour tout $m \in \mathbb{N}$, $(2^m - 1) \wedge (2^n - 1) = 2^{m \wedge n} - 1$.

• $\mathcal{H}(0)$ : $2^0 - 1 = 0$, donc le membre de gauche vaut $(2^m - 1) \wedge 0 = 2^m - 1$ ; comme $m \wedge 0 = m$, le membre de droite vaut aussi $2^m - 1$ (le cas $m = 0$ est cohérent avec la convention $0 \wedge 0 = 0$).
• Soit $n \geqslant 1$ tel que $\mathcal{H}(r)$ soit vraie pour tout $r < n$. Soit $m \in \mathbb{N}$ et $m = nq + r$ sa division euclidienne par $n$, avec $0 \leqslant r < n$. D'après 2, puis $\mathcal{H}(r)$ appliquée à l'entier $n$ : $$(2^m - 1) \wedge (2^n - 1) = (2^n - 1) \wedge (2^r - 1) = 2^{n \wedge r} - 1.$$ Or $m \wedge n = n \wedge r$ par le lemme d'Euclide appliqué à $m = nq + r$. D'où $\mathcal{H}(n)$.

4. Euclide : $84 = 1 \times 60 + 24$, $60 = 2 \times 24 + 12$, $24 = 2 \times 12$. Donc $60 \wedge 84 = 12$ et $$(2^{60} - 1) \wedge (2^{84} - 1) = 2^{12} - 1 = 4095.$$

5. Raisonnons par contraposée. Soit $n \geqslant 2$ composé : $n = ab$ avec $2 \leqslant a < n$ et $b \in \mathbb{N}^*$. D'après 1, $2^a - 1 \mid 2^{ab} - 1 = 2^n - 1$. Or $2^a - 1 \geqslant 3 > 1$ et $2^a - 1 < 2^n - 1$. Donc $2^n - 1$ possède un diviseur strictement compris entre $1$ et lui-même : il n'est pas premier.

La réciproque est fausse : $11$ est premier, mais $2^{11} - 1 = 2047 = 23 \times 89$.

1. Les multiples positifs de $m$ sont les $km$, $k \in \mathbb{N}^*$. Pour $k$ entier, $km \leqslant n \iff k \leqslant n/m \iff k \leqslant \lfloor n/m \rfloor$. Les multiples de $m$ dans $\{1, \dots, n\}$ correspondent donc aux $k \in \{1, \dots, \lfloor n/m \rfloor\}$ : il y en a $\lfloor n/m \rfloor$.

2. Soit $\alpha = v_p(j)$ et $k \in \mathbb{N}$. Si $k \leqslant \alpha$, alors $p^k \mid p^\alpha \mid j$. Si $k > \alpha$, alors $p^{\alpha+1} \mid p^k$, et $p^k \mid j$ entraînerait $p^{\alpha+1} \mid j$, ce qui contredit la définition de $\alpha$. Donc $p^k \mid j \iff k \leqslant \alpha$, et les entiers $k \geqslant 1$ tels que $p^k \mid j$ sont $1, \dots, \alpha$ : il y en a $\alpha = v_p(j)$.

3. Soit $K$ tel que $p^K > n$. Pour $j \leqslant n$ et $k > K$, $p^k \nmid j$. Notons $\varepsilon_{k,j} = 1$ si $p^k \mid j$ et $0$ sinon. Par la règle $v_p(ab) = v_p(a) + v_p(b)$ puis la question 2 : $$v_p(n!) = \sum_{j=1}^{n} v_p(j) = \sum_{j=1}^{n} \sum_{k=1}^{K} \varepsilon_{k,j} = \sum_{k=1}^{K} \sum_{j=1}^{n} \varepsilon_{k,j}.$$ La somme intérieure compte les multiples de $p^k$ dans $\{1, \dots, n\}$ ; d'après 1, elle vaut $\lfloor n/p^k \rfloor$. Pour $k > K$, $\lfloor n/p^k \rfloor = 0$. D'où la formule.

4. Le nombre de zéros terminaux de $N = 2025!$ est le plus grand $t$ tel que $10^t = 2^t 5^t$ divise $N$, c'est-à-dire $t = \min(v_2(N), v_5(N))$. Pour tout $k$, $2^k \leqslant 5^k$, donc $\lfloor n/2^k \rfloor \geqslant \lfloor n/5^k \rfloor$ et $v_2(n!) \geqslant v_5(n!)$. Ainsi $t = v_5(2025!)$ : $$v_5(2025!) = \left\lfloor \frac{2025}{5} \right\rfloor + \left\lfloor \frac{2025}{25} \right\rfloor + \left\lfloor \frac{2025}{125} \right\rfloor + \left\lfloor \frac{2025}{625} \right\rfloor = 405 + 81 + 16 + 3 = 505,$$ les termes suivants étant nuls car $3125 > 2025$. L'écriture de $2025!$ se termine par $505$ zéros.

5. D'après 4, le nombre de zéros terminaux de $n!$ est $f(n) = v_5(n!)$, fonction croissante de $n$ (chaque terme $\lfloor n/5^k \rfloor$ l'est). On calcule $f(404) = 80 + 16 + 3 = 99$ et $f(405) = 81 + 16 + 3 = 100$. Pour $n \leqslant 404$, $f(n) \leqslant 99$. Le plus petit entier cherché est $405$.

1. Comme $p \neq q$ sont premiers, l'un d'eux vaut au moins $3$ et l'autre au moins $2$, donc $m = (p-1)(q-1) \geqslant 2 \times 1 = 2$.

Comme $e \wedge m = 1$, le théorème de Bézout fournit $u, v \in \mathbb{Z}$ avec $eu + mv = 1$, donc $eu \equiv 1 \;[m]$. Soit $d$ le reste de la division euclidienne de $u$ par $m$ : $d \equiv u \;[m]$, donc $ed \equiv 1 \;[m]$, et $d \in \{0, \dots, m-1\}$. Si $d = 0$, on aurait $0 \equiv 1 \;[m]$, soit $m \mid 1$, impossible car $m \geqslant 2$. Donc $d \in \{1, \dots, m-1\}$.

2. Comme $ed \equiv 1 \;[m]$ et $ed \geqslant 1$, il existe $k \in \mathbb{N}$ tel que $ed = 1 + km$.

• Si $p \mid x$ : $x \equiv 0 \;[p]$ et $x^{ed} \equiv 0 \;[p]$ car $ed \geqslant 1$. Donc $x^{ed} \equiv x \;[p]$.
• Si $p \nmid x$ : par le petit théorème de Fermat, $x^{p-1} \equiv 1 \;[p]$. Alors $$x^{ed} = x \cdot x^{k(p-1)(q-1)} = x \cdot \left(x^{p-1}\right)^{k(q-1)} \equiv x \;[p].$$

3. Le raisonnement de la question 2, en échangeant les rôles de $p$ et $q$, donne $x^{ed} \equiv x \;[q]$. Ainsi $p$ et $q$ divisent $x^{ed} - x$. Comme $p$ et $q$ sont des premiers distincts, $p \wedge q = 1$, et une conséquence du lemme de Gauss donne $pq \mid x^{ed} - x$, c'est-à-dire $x^{ed} \equiv x \;[n]$.

4. a) $n = 11 \times 13 = 143$ et $m = 10 \times 12 = 120$. On a $120 = 17 \times 7 + 1$, donc $7 \times (-17) \equiv 1 \;[120]$. Le reste de $-17$ modulo $120$ est $103$, donc $d = 103$. Vérification : $7 \times 103 = 721 = 6 \times 120 + 1$.

b) $5^3 = 125$ et $5^4 = 625 = 4 \times 143 + 53$, donc $5^4 \equiv 53 \;[143]$. Puis $5^7 = 5^4 \times 5^3 \equiv 53 \times 125 = 6625 \;[143]$. Or $143 \times 46 = 5720 + 858 = 6578$ et $6625 - 6578 = 47$. Donc $y = 47$.

c) Modulo $11$. $47 = 4 \times 11 + 3$, donc $47 \equiv 3 \;[11]$. Or $3^5 = 243 = 22 \times 11 + 1 \equiv 1 \;[11]$ et $103 = 5 \times 20 + 3$, donc $47^{103} \equiv 3^{103} \equiv 3^3 = 27 \equiv 5 \;[11]$.

Modulo $13$. $47 = 3 \times 13 + 8$, donc $47 \equiv 8 \;[13]$. Or $8^2 = 64 = 5 \times 13 - 1 \equiv -1 \;[13]$ et $103 = 2 \times 51 + 1$, donc $47^{103} \equiv (8^2)^{51} \times 8 \equiv (-1)^{51} \times 8 = -8 \equiv 5 \;[13]$.

Conclusion. $11$ et $13$ divisent $47^{103} - 5$ et $11 \wedge 13 = 1$, donc $143 \mid 47^{103} - 5$. Comme $0 \leqslant 5 < 143$, le reste de $47^{103}$ modulo $143$ est $5$.

Interprétation. $47^{103} \equiv (5^7)^{103} = 5^{ed} \;[143]$, et la question 3 donne $5^{ed} \equiv 5 \;[143]$. Le message $5$, chiffré en $y = 47$ par $x \mapsto x^e$, est retrouvé par $y \mapsto y^d$.