TD — Arithmétique dans ℤ
Chapitre 09
MPSI (1re année) — TD du Chapitre 09. Divisibilité, division euclidienne, PGCD, PPCM, théorèmes de Bézout et de Gauss, nombres premiers, valuation p-adique, congruences.
Exercice 1
Calculer 1234 \wedge 567 par l’algorithme d’Euclide. En déduire des entiers u, v tels que 1234u + 567v = 1234 \wedge 567. Calculer 1234 \vee 567.
Indications : - 1234 = 2 \times 567 + 100 - 567 = 5 \times 100 + 67 - 100 = 1 \times 67 + 33 - 67 = 2 \times 33 + 1 - Remonter les divisions pour trouver u et v.
Exercice 2
Soient a, b \in \mathbb{Z}^2 \setminus \{(0,0)\}. Montrer que : a\mathbb{Z} + b\mathbb{Z} = (a \wedge b)\mathbb{Z} \quad \text{et} \quad a\mathbb{Z} \cap b\mathbb{Z} = (a \vee b)\mathbb{Z}
Indication : Utiliser le théorème de Bézout pour la première égalité. Pour la seconde, montrer que a\mathbb{Z} \cap b\mathbb{Z} est un sous-groupe de \mathbb{Z} contenant ab.
Exercice 3
Résoudre dans \mathbb{Z} les congruences suivantes :
- 3x \equiv 7 \pmod{11}
- 6x \equiv 4 \pmod{10}
- x^2 \equiv 1 \pmod{8}
Indications : - (1) Chercher l’inverse de 3 modulo 11. - (2) Simplifier en divisant par \gcd(6, 10) = 2. - (3) Tester x = 0, 1, \ldots, 7.
Exercice 4
Résoudre le système de congruences (théorème des restes chinois) : \begin{cases} x \equiv 2 \pmod{3} \\ x \equiv 3 \pmod{5} \\ x \equiv 2 \pmod{7} \end{cases}
Indication : Chercher x = 2 + 3k, puis imposer 2 + 3k \equiv 3 \pmod{5}, etc.
Exercice 5
Montrer que 2^{11} - 1 = 2047 n’est pas premier.
Indication : Vérifier que 2047 = 23 \times 89.
Exercice 6
Montrer qu’il existe une infinité de nombres premiers (raisonnement d’Euclide).
Indication : Supposer p_1, \ldots, p_n premiers. Poser N = p_1 \cdots p_n + 1. Montrer qu’aucun p_i ne divise N.
Exercice 7
Soit p un nombre premier. Montrer que si p \mid ab avec a, b \in \mathbb{Z}, alors p \mid a ou p \mid b (lemme de Gauss).
Indication : Si p \nmid a, alors p \wedge a = 1 (car p premier). Par le théorème de Gauss, p \mid b.
Exercice 8
Déterminer v_2(1000!) et v_5(100!). En déduire le nombre de zéros terminaux de 100!.
Indications : - Formule de Legendre : v_p(n!) = \sum_{k \geq 1} \lfloor n/p^k \rfloor. - Le nombre de zéros terminaux de n! est v_5(n!).
Exercice 9
Montrer que pour tout premier p et tout a \in \mathbb{Z} : a^p \equiv a \pmod{p} (petit théorème de Fermat).
Indications : - Si p \mid a, c’est trivial. - Sinon, utiliser le fait que \{a, 2a, \ldots, (p-1)a\} \equiv \{1, 2, \ldots, p-1\} \pmod{p}.
Exercice 10
Montrer que n^5 - n est divisible par 30 pour tout n \in \mathbb{Z}.
Indication : 30 = 2 \times 3 \times 5. Utiliser le petit théorème de Fermat pour p = 2, 3, 5.
Exercice 11
Soit n \in \mathbb{N}^*. Montrer que n^7 - n est divisible par 42.
Indication : 42 = 2 \times 3 \times 7. Utiliser le petit théorème de Fermat.
Exercice 12
Calculer 2^{1000} \pmod{11}.
Indication : 2^{10} \equiv 1 \pmod{11} par le petit théorème de Fermat. Donc 2^{1000} = (2^{10})^{100} \equiv 1 \pmod{11}.