Arithmétique

Exercice 1 — Division euclidienne et divisibilité
Corrigé :
1. $523 = 17 \times 30 + 13$ : quotient $30$, reste $13$.
2. $523 - 13 = 510 = 17 \times 30$, donc $17 \mid 510$.
3. $n(n+1)(n+2)$ est le produit de trois entiers consécutifs. Parmi tout trois consécutifs, l'un est divisible par $2$ et l'un (possiblement différent) est divisible par $3$, donc le produit est divisible par $2 \times 3 = 6$.

Exercice 2 — PGCD et algorithme d'Euclide
Corrigé :
1. $357 = 119 \times 3 + 0$ → $\text{PGCD}(357,119) = 119$.
2. Puisque le reste est $0$, $119 \mid 357$ par définition de la division euclidienne.
3. On cherche $357u + 119v = 119$. Puisque $357 = 3 \times 119$, on peut prendre $u = 0$ et $v = 1$ : $0 + 119 \times 1 = 119$ ✓. (Ou $u = 1, v = -2$ : $357 - 238 = 119$ ✓.)

Exercice 3 — Nombres premiers et décomposition
Corrigé :
1. $1260 = 2^2 \times 3^2 \times 5 \times 7$ ; $756 = 2^2 \times 3^3 \times 7$.
2. $\text{PGCD}(1260, 756) = 2^{\min(2,2)} \times 3^{\min(2,3)} \times 5^{\min(1,0)} \times 7^{\min(1,1)} = 2^2 \times 3^2 \times 7 = 4 \times 9 \times 7 = 252$.
3. $\frac{1260}{756} = \frac{1260/252}{756/252} = \frac{5}{3}$.

Exercice 4 — Congruences
Corrigé :
1. $3^6 \equiv 1 \pmod 7$ (ordre $6$). $200 = 6 \times 33 + 2$, donc $3^{200} \equiv 3^2 = 9 \equiv 2 \pmod 7$.
2. Les chiffres des unités de $9^n$ : $9^1 \to 9$, $9^2 \to 1$, $9^3 \to 9$, $9^4 \to 1$… Période $2$. $2025$ est impair, donc le chiffre des unités est $9$.
3. On cherche l'inverse de $5$ modulo $11$ : $5 \times 9 = 45 = 11 \times 4 + 1 \equiv 1 \pmod{11}$, donc $5^{-1} \equiv 9$. Solution : $x \equiv 9 \times 3 = 27 \equiv 5 \pmod{11}$.

Exercice 5 — Problème de synthèse — Théorème de Gauss
Corrigé :
1. $\text{PGCD}(a,6)=1$ et $6 \mid 5a$. Puisque $\text{PGCD}(6, 5)=1$ (car $5$ et $6$ sont premiers entre eux), le théorème de Gauss donne $6 \mid a$.
2. Soit $d = \text{PGCD}(n, n+2)$. Alors $d \mid n$ et $d \mid (n+2)$, donc $d \mid (n+2) - n = 2$. Ainsi $d \mid 2$, c'est-à-dire $d \in \{1, 2\}$.
3. Si $n$ est impair, $n+2$ est aussi impair. $d = \text{PGCD}(n, n+2)$ divise $n$ (impair), donc $d$ est impair. Comme $d \mid 2$ et $d$ est impair, $d = 1$.