Arithmétique dans Z
L'arithmétique dans Z est un domaine à part du programme algérien : divisibilité, division euclidienne, congruences, pgcd, théorèmes de Bézout et de Gauss, nombres premiers. Les questions y sont courtes mais exigent une rédaction précise, car chaque théorème a une hypothèse indispensable.
Division euclidienne et divisibilité
Pour tout a ∈ Z et b ∈ N*, il existe un unique couple (q, r) avec a = bq + r et 0 ≤ r < b. On dit que b divise a s'il existe k ∈ Z tel que a = bk. La divisibilité se conserve par combinaison linéaire : si d divise a et b, il divise au + bv pour tous entiers u et v.
Congruences
a ≡ b modulo n signifie que n divise a − b. Les congruences sont compatibles avec l'addition, la soustraction, la multiplication et les puissances : on peut réduire à chaque étape. En revanche, on ne divise jamais sans précaution : l'inverse de a modulo n existe si et seulement si pgcd(a, n) = 1.
PGCD, Bézout, Gauss
Le pgcd se calcule par l'algorithme d'Euclide, en enchaînant les divisions euclidiennes. Le théorème de Bézout affirme qu'il existe des entiers u et v tels que au + bv = pgcd(a, b) ; en particulier a et b sont premiers entre eux si et seulement s'il existe u, v avec au + bv = 1. Le théorème de Gauss énonce : si a divise bc et si pgcd(a, b) = 1, alors a divise c.
Exemple rédigé
Résoudre 7x ≡ 3 modulo 10. Comme pgcd(7, 10) = 1, 7 est inversible modulo 10 ; or 7 × 3 = 21 ≡ 1, donc l'inverse de 7 est 3. En multipliant par 3 : x ≡ 9 modulo 10. Les solutions sont les entiers de la forme 10k + 9.
Pièges qui coûtent des points
- Appliquer Gauss sans vérifier pgcd(a, b) = 1.
- Diviser les deux membres d'une congruence par un entier non premier avec le module.
- Donner un reste négatif dans la division euclidienne.
- Oublier que les coefficients de Bézout ne sont pas uniques.
- Vérifier une divisibilité sur quelques exemples au lieu d'une récurrence ou d'une factorisation.