Arithmétique : divisibilité, PGCD, nombres premiers

L'arithmétique étudie les propriétés des nombres entiers. On dit que a divise b (a | b) si b = ka pour un entier k. La division euclidienne de a par b (b > 0) donne a = bq + r avec 0 ≤ r < b. Le PGCD de deux entiers a et b est le plus grand entier qui divise les deux. L'algorithme d'Euclide le calcule efficacement par divisions successives : pgcd(a, b) = pgcd(b, r) où r est le reste de a ÷ b. Par exemple, pgcd(252, 198) : 252 = 1×198 + 54, 198 = 3×54 + 36, 54 = 1×36 + 18, 36 = 2×18, donc pgcd = 18. Un nombre premier p ≥ 2 n'est divisible que par 1 et p. Le théorème fondamental de l'arithmétique affirme que tout entier ≥ 2 se décompose de façon unique en produit de facteurs premiers : par exemple 360 = 2³ × 3² × 5.