PGCD, Bézout et Gauss en Terminale maths expertes

PGCD, théorème de Bézout, théorème de Gauss en Maths expertes : cours complet

Le PGCD (Plus Grand Commun Diviseur), le théorème de Bézout et le théorème de Gauss sont les outils centraux de l'arithmétique : ils permettent de résoudre les équations diophantiennes et fondent la cryptographie.

PGCD

Définition

Le PGCD de deux entiers $a,b$a, b non tous nuls est le plus grand entier positif qui divise à la fois $a$a et $b$b. Noté $\gcd (a,b)$gcd(a, b) ou $a\wedge b$a wedge b.

Algorithme d'Euclide

$$\gcd (a,b)=\gcd (b,r)$$gcd(a, b) = gcd(b, r)

où $r$r est le reste de la division de $a$a par $b$b. On répète jusqu'à reste nul.

Exemple

$\gcd (252,198)$gcd(252, 198) :

$$252=198\times 1+54$$252 = 198 × 1 + 54 $$198=54\times 3+36$$198 = 54 × 3 + 36 $$54=36\times 1+18$$54 = 36 × 1 + 18 $$36=18\times 2+0$$36 = 18 × 2 + 0

Dernier reste non nul : $18$18. Donc $\gcd (252,198)=18$gcd(252, 198) = 18.

Propriétés

• $\gcd (a,0)=|a|$gcd(a, 0) = |a|.
• $\gcd (a,b)=\gcd (b,a)$gcd(a, b) = gcd(b, a).
• $\gcd (a,b)=\gcd (a,b-a)$gcd(a, b) = gcd(a, b - a) (algorithme par soustraction).
• $a|b⟺\gcd (a,b)=|a|$a | b ⇔ gcd(a, b) = |a|.

Théorème de Bézout

Énoncé

Pour tous entiers $a,b$a, b non tous nuls, il existe des entiers $u,v$u, v tels que :

$$au+bv=\gcd (a,b)$$au + bv = gcd(a, b)

Coefficients de Bézout

Les entiers $u,v$u, v ne sont pas uniques, on en trouve avec l'algorithme d'Euclide étendu.

Corollaire (Bézout fort)

$$\gcd (a,b)=1⟺\exists u,v:au+bv=1$$gcd(a, b) = 1 ⇔ ∃ u, v : au + bv = 1

Cette équivalence est très utilisée.

Nombres premiers entre eux

Définition

$a$a et $b$b sont premiers entre eux si $\gcd (a,b)=1$gcd(a, b) = 1.

Exemples

• $6$6 et $35$35 : $\gcd =1$gcd = 1, premiers entre eux.
• $12$12 et $18$18 : $\gcd =6$gcd = 6, non premiers entre eux.

Théorème de Gauss

Énoncé

Soient $a,b,c$a, b, c entiers. Si $a|bc$a | bc et $\gcd (a,b)=1$gcd(a, b) = 1, alors $a|c$a | c.

Application

C'est l'outil principal pour résoudre des équations diophantiennes.

Équations diophantiennes

Forme

$$ax+by=c(a,b,c\in \mathbb{Z})$$ax + by = c (a, b, c ∈ ℤ)

Existence de solutions

Cette équation admet des solutions ssi $\gcd (a,b)|c$gcd(a, b) | c.

Si solutions, méthode

1. Calculer $d=\gcd (a,b)$d = gcd(a, b).
2. Diviser : $a^{\prime }x+b^{\prime }y=c^{\prime }$a' x + b' y = c' avec $a^{\prime }=a/d$a' = a/d, $b^{\prime }=b/d$b' = b/d, $c^{\prime }=c/d$c' = c/d (et $\gcd (a^{\prime },b^{\prime })=1$gcd(a', b') = 1).
3. Trouver une solution particulière $(x_0,y_0)$(x₀, y₀) via Bézout.
4. Solutions générales :

$$x=x_0+b^{\prime }k;y=y_0-a^{\prime }k(k\in \mathbb{Z})$$x = x₀ + b' k ; y = y₀ - a' k (k ∈ ℤ)

Exemple

Résoudre $5x+3y=1$5x + 3y = 1 dans ${\mathbb{Z}}^2$ℤ².

• $\gcd (5,3)=1$gcd(5, 3) = 1, donc solutions existent.
• $5\times 2+3\times (-3)=10-9=1$5 × 2 + 3 × (-3) = 10 - 9 = 1 → $(x_0,y_0)=(2,-3)$(x₀, y₀) = (2, -3).
• Solutions : $x=2+3k$x = 2 + 3k, $y=-3-5k$y = -3 - 5k.

PPCM

Définition

$$\text{ppcm}(a,b)=\frac{|ab|}{\gcd (a,b)}$$ppcm (a, b) = |ab|/(gcd(a, b))

C'est le plus petit multiple commun positif de $a$a et $b$b.

Exemple

$\text{ppcm}(12,18)=\frac{216}{6}=36$ppcm (12, 18) = 216/6 = 36.

Algorithme d'Euclide étendu

Pour trouver $u,v$u, v tels que $au+bv=\gcd (a,b)$au + bv = gcd(a, b).

def euclide_etendu(a, b):
    if b == 0:
        return (a, 1, 0)
    g, u1, v1 = euclide_etendu(b, a % b)
    return (g, v1, u1 - (a // b) * v1)

Applications

Cryptographie RSA

RSA repose sur le petit théorème de Fermat et sur la difficulté de factoriser des produits de grands nombres premiers.

Fractions irréductibles

Pour rendre $\frac{a}{b}$a/b irréductible, on divise par $\gcd (a,b)$gcd(a, b).

Modélisation

Réseaux, partage équitable, périodes synchronisées.

Erreurs fréquentes à éviter

• Mauvais Euclide : bien remplacer $a,b$a, b par $b,r$b, r.
• Bézout non unique : il y a une infinité de couples $(u,v)$(u, v) qui marchent.
• Confondre PGCD et PPCM.
• Oublier la condition $\gcd |c$gcd | c dans les équations diophantiennes.

FAQ — PGCD, Bézout, Gauss

Pourquoi l'algorithme d'Euclide est-il rapide ?

Il converge en $O(\log (\min (a,b)))$O(log(min(a, b))) étapes, ce qui est très efficace même pour de très grands nombres.

À quoi sert Bézout ?

À prouver l'existence de solutions à des équations diophantiennes et à construire ces solutions.

Le théorème de Gauss est-il aussi puissant qu'Euclide ?

C'est un complément : Euclide trouve les diviseurs, Gauss permet de déduire des divisibilités.

Quel lien entre PGCD et PPCM ?

$$\gcd (a,b)\times \text{ppcm}(a,b)=|a\times b|$$gcd(a, b) × ppcm (a, b) = |a × b|

C'est l'identité clé.