Retour au programme
L'arithmétique étudie les propriétés des entiers. Division euclidienne : a = bq + r, 0 ≤ r < b. PGCD : algorithme d'Euclide : pgcd(a, b) = pgcd(b, r) où r = a mod b. Identité de Bézout : si d = pgcd(a, b), il existe u, v ∈ ℤ tels que au + bv = d. Théorème de Gauss : si a|bc et pgcd(a, b) = 1, alors a|c. Nombres premiers entre eux : pgcd = 1. Congruences : a ≡ b (mod n) signifie n | (a − b). Propriétés : réflexivité, symétrie, transitivité, compatibilité avec + et ×. Résolution de congruences : ax ≡ b (mod n) a une solution si pgcd(a, n) | b. Petit théorème de Fermat : si p est premier et pgcd(a, p) = 1, alors aᵖ⁻¹ ≡ 1 (mod p). Applications : cryptographie RSA, calcul de restes, tests de primalité.
Exercice 1 : Algorithme d'Euclide.
Calculez pgcd(252, 105) et trouvez u, v tels que 252u + 105v = pgcd.
Exercice 2 : Congruences.
1. Calculez 7¹⁰⁰ mod 3.
2. Résolvez 5x ≡ 3 (mod 7).
Exercice 3 : Montrez que si n est pair, alors n² ≡ 0 (mod 4).
Comment appliquer l'algorithme d'Euclide pour trouver le PGCD ?
Correction
pgcd(a, b) avec a > b : diviser a par b, obtenir reste r. Alors pgcd(a,b) = pgcd(b,r). Répéter jusqu'à r = 0 ; le dernier reste non nul est le pgcd. Ex : pgcd(252, 105) : 252 = 2×105 + 42 ; 105 = 2×42 + 21 ; 42 = 2×21 + 0. Donc pgcd = 21.
Comment calculer une grande puissance modulo n ?
Correction
Utiliser les propriétés des congruences et l'exponentiation rapide. Ex : 7¹⁰⁰ mod 3. 7 ≡ 1 (mod 3) car 7 = 2×3 + 1. Donc 7¹⁰⁰ ≡ 1¹⁰⁰ ≡ 1 (mod 3).
Énoncer le théorème de Gauss et donner un exemple.
Correction
Si a divise le produit bc et si pgcd(a, b) = 1 (a et b premiers entre eux), alors a divise c. Exemple : 6 | 4×9 = 36. pgcd(6, 4) = 2 ≠ 1, donc le théorème ne s'applique pas directement. Mais 3 | 4×9 et pgcd(3, 4) = 1, donc 3 | 9 — ce qui est vrai.