Principes fondamentaux de l'arithmétique

📋 Plan du Cours

1. Divisibilité dans Z
2. Congruence dans Z
3. PGCD et PPCM
4. Nombres premiers
5. Algorithme d’Euclide
6. Nombres premiers entre eux
7. Décomposition en premiers
8. Critère divisibilité par 3
9. Critère divisibilité par 11

📖 1. Divisibilité dans Z

🔑 Notions clés & Définitions

• Théorème de la division euclidienne dans Z (PTSI, 2025) : Pour tout a ∈ Z∗ et b ∈ Z, il existe un couple unique (q, r) ∈ Z × N tel que b = aq + r, avec 0 ≤ r < |a|.
• Définition de quotient et reste de la division euclidienne (PTSI, 2025) : Le quotient q est le nombre entier obtenu lors de la division de b par a, et le reste r est la différence b − aq, vérifiant la condition 0 ≤ r < |a|.
• Définition de divisibilité (PTSI, 2025) : a divise b (noté a|b) si il existe un entier k ∈ Z tel que b = ka.
• Propriétés de la relation de divisibilité (PTSI, 2025) :
  • Si a|b et b ≠ 0, alors |a| ≤ |b|.
  • Si a|b et b|c, alors a|c.
  • Si a|b et b|a, alors a = b ou a = −b.
• Lien entre divisibilité et division euclidienne (PTSI, 2025) : a divise b si et seulement si le reste de la division euclidienne de b par a est nul.

📖 2. Congruence dans Z

🔑 Notions clés & Définitions

• Congruence modulo n : Soit n ∈ Z et (a, b) ∈ Z². On dit que a et b sont congrus modulo n, noté a ≡ b[n], si il existe k ∈ Z tel que b = a + kn. Cela signifie que la différence b − a est divisible par n, c’est-à-dire que n divise b − a.