PGCD, algorithme d'Euclide et Bézout

PGCD et PPCM, algorithme d'Euclide, nombres premiers entre eux, identité de Bézout, théorème de Gauss et équations ax + by = c en nombres entiers.

Le programme, thème par thème

Le poids de chaque thème suit celui que lui donne l'examen.

PGCD de a et b : de quoi s'agit-il ?
Voir la réponse
Le plus grand entier qui divise à la fois a et b ; il se calcule sans décomposer, par l'algorithme d'Euclide.
Les diviseurs communs de 84 et 30 sont 1, 2, 3 et 6 : le plus grand est 6. Tout diviseur commun divise aussi le PGCD.
Qu'affiche ce programme ?

```python
a, b = 48, 18
while b:
a, b = b, a % b
print(a)
`
- 6
- 18
- 12
- 0
Voir la réponse
6
Les couples successifs sont (48, 18), (18, 12), (12, 6), (6, 0). La boucle s'arrête quand b vaut 0, et a contient alors le dernier reste non nul : 6.
L'algorithme d'Euclide s'appuie sur l'égalité PGCD(a, b) = PGCD(b, …) ; il s'arrête quand le reste vaut ….
Voir la réponse
L'algorithme d'Euclide s'appuie sur l'égalité PGCD(a, b) = PGCD(b, a mod b) ; il s'arrête quand le reste vaut 0.
Pour 252 et 198 : PGCD(252, 198) = PGCD(198, 54) = PGCD(54, 36) = PGCD(36, 18) = PGCD(18, 0) = 18.
PPCM de a et b : de quoi s'agit-il ?
Voir la réponse
Le plus petit entier strictement positif qui est multiple de a et de b.
Pour a et b strictement positifs, PGCD × PPCM = a × b : PPCM(12, 18) = 12 × 18 / 6 = 36.