S'abonner
decoration
decorationdecoration

Division euclidienne et les deux méthodes pour le PGCD

Définition

Soient aa et bb deux entiers naturels avec bb non nul.

Effectuer la division euclidienne de aa par bb, c’est déterminer le couple d’entiers naturels (q ;r)(q\ ; r) tel que :a=b×q+retr<ba=b \times q + r \quad \text {et} \quad r< b

aa s'appelle le dividende, bb le diviseur, qq le quotient (entier) et rr le reste.

lumix

Le couple (q ;r)(q\ ; r) est unique.

Définition

Un diviseur commun à deux entiers naturels aa et bb est un entier naturel qui divise les deux à la fois. Le plus grand entier qui divise à la fois aa et bb est appelé le Plus Grand Commun Diviseur de aa et bb, et est noté PGCD(a;b)PGCD(a; b).

Propriété

  • Calculs de PGCD avec l'algorithme d'Euclide (divisions successives)

    C’est un algorithme itératif qui consiste à faire des divisions euclidiennes successives. Il repose sur la propriété suivante :Soient aa et bb deux entiers naturels non nuls avec a>ba>b et rr est le reste de la division euclidienne de aa par bb. On a :PGCD(a;b)=PGCD(b;r).PGCD(a; b) = PGCD(b ; r).

  • Algorithme

    Dans la 1ère division, on divise aa (le plus grand) par bb (le plus petit) et dans la 2ème division, on prend bb le diviseur de la 1ère, comme dividende et le reste de la 1ère division comme diviseur et ainsi de suite jusqu’à obtenir un reste nul. Le dernier reste non nul est PGCD(a;b)PGCD(a ; b).

Revenir au chapitre
Commentaires

zighem

0
il y a 3 ans
2x^2 + 12x + 9
Répondre