Aller au contenu
Mon Coach de Maths Comprendre, prouver, réussir

Algèbre et géométrie · 2e Bac SM

Arithmétique : PGCD, Bézout, Gauss, Fermat et équation ax + by = c

Partager 252 balles en équipes égales, synchroniser deux horaires : l'arithmétique répond avec le PGCD et le PPCM, et résout des équations en nombres entiers.

Le vocabulaire à connaître

PGCD, PPCM
Le plus grand diviseur commun et le plus petit multiple commun de deux entiers. On a toujours PGCD(a ; b) × PPCM(a ; b) = a × b.
premiers entre eux
Deux entiers dont le PGCD vaut 1.
coefficients de Bézout
Des entiers u et v avec a u + b v = PGCD(a ; b), trouvés en remontant l'algorithme d'Euclide.

Ce qu'on sait

  • Avec les décompositions en facteurs premiers : le PGCD prend les facteurs communs avec le plus petit exposant, le PPCM tous les facteurs avec le plus grand. Si n = p₁ᵃ × p₂ᵇ × …, n a (a + 1)(b + 1)… diviseurs positifs.
  • Bézout : a et b sont premiers entre eux : Deux entiers dont le PGCD vaut 1. si et seulement si il existe u et v avec a u + b v = 1. Gauss : si a divise b c et si a est premier avec b, alors a divise c.
  • Fermat : si p est premier et ne divise pas a, alors aᵖ⁻¹ ≡ 1 [p]. L'équation a x + b y = c a des solutions entières si et seulement si PGCD(a ; b) divise c.

La méthode, étape par étape

1.Pour un PGCD, je fais les divisions euclidiennes successives ; le dernier reste non nul est le PGCD.
2.Pour les coefficients de Bézout : Des entiers u et v avec a u + b v = PGCD(a ; b), trouvés en remontant l'algorithme d'Euclide., je remonte les divisions en exprimant chaque reste.
3.Pour a x + b y = c, je teste que le PGCD divise c, puis je trouve une solution particulière (x₀ ; y₀).
4.J'écris a(x − x₀) = −b(y − y₀) et j'applique Gauss pour obtenir toutes les solutions.
Pour a et b premiers entre eux, les solutions de a x + b y = c sont x = x₀ + b k et y = y₀ − a k, avec k entier.
C.Q.F.D.

L'exemple au propre

1.Je résous 5x + 3y = 41 dans Z × Z.
2.Une solution particulière est (1 ; 12) : 5 × 1 + 3 × 12 = 5 + 36 = 41.
3.En soustrayant, 5(x − 1) = −3(y − 12) ; 5 et 3 sont premiers entre eux, donc 3 divise x − 1 (Gauss).
4.Les solutions sont x = 1 + 3k et y = 12 − 5k. Contrôle : 5(1 + 3k) + 3(12 − 5k) = 5 + 36 = 41.

Dans la même classe

S'entraîner en 2e Bac SM Toutes les fiches