Médaille
N°1 pour apprendre & réviser du collège au lycée.
Marianne

Conforme au programme
officiel 2018 - 2019

Démonstration de l'algorithme d'Euclide
Démonstration

Introduction

Dans cette fiche, nous allons nous intéresser au théorème algorithme d’Euclide, qui permet de déterminer si des nombres sont premiers entre eux.

Prérequis

Afin de démontrer cet algorithme nous avons besoin du théorème suivant :

aa et bb sont deux entiers naturels non nuls tels que la division euclidienne de aa par bb se traduit par a=bq+ra=bq+r avec rr compris entre 00 et bb tous deux exclus 0<r<b0 < r < b.

Alors l’ensemble des diviseurs commun à aa et bb est identique à ceux communs à bb et rr D(a ;b)=D(b ;r)\text D(a\ ;b)=\text D(b\ ;r) ce qui amène à PGCD (a ;b)=PGCD (b ;r)\text{PGCD }(a\ ;b)=\text{PGCD }(b\ ;r).

Démonstration

  • Démontrons que si dd divise aa et bb, alors dd divise bb et rr : Si dd divise aa et bb, dd divise toute combinaison linéaire de aa et bb, donc en particulier abqa-bq, soit rr. Il en résulte que l’ensemble des diviseurs de aa et bb sont inclus dans les diviseurs de bb et rr : D(a ;b)D(b ;r)\text D(a\ ;b)⊂\text D(b\ ;r)
  • Démontrons que si δδ divise bb et rr, alors δδ divise aa et bb. Si δδ divise bb et rr, δδ divise toute combinaison linéaire de bb et rr, donc en particulier bq+rbq+r, soit aa. Il en résulte que l’ensemble des diviseurs de bb et rr figurent parmi les diviseurs de aa et bb : D(b ;r)D(a ;b)\text D(b\ ;r)⊂\text D(a\ ;b)

La double inclusion équivaut donc à dire que l’ensemble des diviseurs à aa et bb sont communs à ceux de bb et rr D(a ;b)=D(b ;r)\text D(a\ ;b)=\text D(b\ ;r). Ces deux ensembles étant identiques, ils ont le même plus grand élément donc : PGCD (a ;b)=PGCD(b ;r)\text{PGCD }(a\ ;b)=\text{PGCD}(b\ ;r)

Lorsque bb ne divise pas aa, le PGCD\text{PGCD} de aa et bb est le dernier reste non nul dans la succession des divisions de l’algorithme d’Euclide.