Arithmétique
Divisibilité et nombres premiers
L'arithmétique étudie les propriétés des entiers : divisibilité, nombres premiers, PGCD. Elle est fondamentale en cryptographie.
Prérequis
Calcul avec les entiersDivision euclidienne
📖Notions essentielles
Divisibilité : a divise b si ∃k∈ℤ, b = ka
Nombre premier : Entier > 1 ayant exactement 2 diviseurs : 1 et lui-même
PGCD : Plus Grand Commun Diviseur de a et b
Nombres premiers entre eux : PGCD(a,b) = 1
📐Formules à connaître
Théorème de Bézout
PGCD(a,b)=1 ⟺ ∃u,v : au+bv=1
Caractérisation des nombres premiers entre eux
Lemme de Gauss
Si a|bc et PGCD(a,b)=1 alors a|c
Fondamental pour les preuves
✅Méthodes
Algorithme d'Euclide
- 1Effectuer les divisions euclidiennes successives
- 2a = bq + r
- 3Répéter avec b et r
- 4Le dernier reste non nul est le PGCD
⚠️Pièges à éviter
- ⚠️0 n'est pas premier
- ⚠️1 n'est pas premier
- ⚠️PGCD(a,0) = a
📝Exercices types au Bac
Calcul de PGCD
Coefficients de Bézout
Démonstrations de divisibilité
