Maths-cours

Cours & exercices de mathématiques

  • Troisième
  • Seconde
  • Première
  • Terminale
  • Tle Complément.
  • Tle Expert
  • Quiz
  • 3ème
  • 2nde
  • 1ère
  • Tle
  • Tle Comp
  • Tle XP
  • Quiz

Troisième

Complément

Deux méthodes de calcul du PGCD

1 - Méthode des soustractions successives

Cette méthode se base sur le résultat suivant :

Théorème

Soient aaa et bbb sont deux entiers naturels non nuls avec a>ba > ba>b alors PGCD(a ;b)=PGCD(b ;a−b)PGCD\left(a~; b\right) = PGCD\left(b~; a-b\right)PGCD(a ;b)=PGCD(b ;a−b).

Remarque

L'intérêt de ce théorème est qu'il remplace le calcul du PGCD de deux nombres par le calcul du PGCD de deux nombres plus petits. On peut ainsi calculer un PGCD utilisant plusieurs fois de suite ce théorème (méthode des soustractions successives).

Exemple

Calculons le PGCD de 600600600 et 315315315 par la méthode des soustractions successives.

600−315=285600-315 =285600−315=285 donc PGCD(600 ;315)=PGCD(315 ;285)PGCD\left(600~; 315\right)=PGCD\left(315~; 285\right)PGCD(600 ;315)=PGCD(315 ;285)

315−285=30315-285 =30315−285=30 donc PGCD(315 ;285)=PGCD(285 ;30)PGCD\left(315~; 285\right)=PGCD\left(285~; 30\right)PGCD(315 ;285)=PGCD(285 ;30)

285−30=255285-30 =255285−30=255 donc PGCD(285 ;30)=PGCD(255 ;30)PGCD\left(285~; 30\right)=PGCD\left(255~; 30\right)PGCD(285 ;30)=PGCD(255 ;30)

255−30=225255-30 =225255−30=225 donc PGCD(255 ;30)=PGCD(225 ;30)PGCD\left(255~; 30\right)=PGCD\left(225~; 30\right)PGCD(255 ;30)=PGCD(225 ;30)

225−30=195225-30 =195225−30=195 donc PGCD(225 ;30)=PGCD(195 ;30)PGCD\left(225~; 30\right)=PGCD\left(195~; 30\right)PGCD(225 ;30)=PGCD(195 ;30)

195−30=165195-30 =165195−30=165 donc PGCD(195 ;30)=PGCD(165 ;30)PGCD\left(195~; 30\right)=PGCD\left(165~; 30\right)PGCD(195 ;30)=PGCD(165 ;30)

165−30=135165-30 =135165−30=135 donc PGCD(165 ;30)=PGCD(135 ;30)PGCD\left(165~; 30\right)=PGCD\left(135~; 30\right)PGCD(165 ;30)=PGCD(135 ;30)

135−30=105135-30 =105135−30=105 donc PGCD(135 ;30)=PGCD(105 ;30)PGCD\left(135~; 30\right)=PGCD\left(105~; 30\right)PGCD(135 ;30)=PGCD(105 ;30)

105−30=75105-30 =75105−30=75 donc PGCD(105 ;30)=PGCD(75 ;30)PGCD\left(105~; 30\right)=PGCD\left(75~; 30\right)PGCD(105 ;30)=PGCD(75 ;30)

75−30=4575-30 =4575−30=45 donc PGCD(75 ;30)=PGCD(45 ;30)PGCD\left(75~; 30\right)=PGCD\left(45~; 30\right)PGCD(75 ;30)=PGCD(45 ;30)

45−30=1545-30 =1545−30=15 donc PGCD(45 ;30)=PGCD(15 ;30)PGCD\left(45~; 30\right)=PGCD\left(15~; 30\right)PGCD(45 ;30)=PGCD(15 ;30)

30−15=1530-15 =1530−15=15 donc PGCD(30 ;15)=PGCD(15 ;15)PGCD\left(30~; 15\right)=PGCD\left(15~; 15\right)PGCD(30 ;15)=PGCD(15 ;15)

Or évidemment PGCD(15 ;15)=15PGCD\left(15~; 15\right) = 15PGCD(15 ;15)=15 donc finalement :

PGCD(600 ;315)=15PGCD\left(600~; 315\right)=15PGCD(600 ;315)=15.

Remarque

On voit que cette méthode est assez simple au niveau calcul (elle ne requiert que des soustractions) mais elle peut dans certains cas s'avérer assez longue. Une méthode plus rapide est l'algorithme d'Euclide.

2 - Algorithme d'Euclide

L'algorithme d'Euclide utilise le théorème suivant :

Théorème

Soient aaa et bbb sont deux entiers naturels non nuls avec a>ba > ba>b et rrr le reste de la division euclidienne de aaa par bbb.

Si r≠0r\neq 0r≠0 alors PGCD(a ;b)=PGCD(b ;r)PGCD\left(a~; b\right) = PGCD\left(b~; r\right)PGCD(a ;b)=PGCD(b ;r).

Remarques

  • Si r=0r=0r=0, cela signifie que bbb divise aaa donc dans ce cas PGCD(a;b)=bPGCD\left(a;b\right)=bPGCD(a;b)=b

  • Comme le précédent, ce théorème remplace le calcul d'un PGCD par le calcul du PGCD de deux nombres plus petits.

    On peut, là encore, calculer un PGCD utilisant plusieurs fois de suite ce théorème. cette méthode s'appelle l'algorithme d'Euclide (ou la méthode des divisions successives).

Exemple

Calculons, à nouveau, le PGCD de 600600600 et 315315315 mais avec l'algorithme d'Euclide cette fois :

600600600 touche division euclidienne 315 315315 : Q=1 Q=1Q=1 et R=285R=285R=285 donc PGCD(600 ;315)=PGCD(315 ;285)PGCD\left(600~; 315\right)=PGCD\left(315~; 285\right)PGCD(600 ;315)=PGCD(315 ;285)

315315315 touche division euclidienne 285285285 : Q=1 Q=1Q=1 et R=30R=30R=30 donc PGCD(315 ;285)=PGCD(285 ;30)PGCD\left(315~; 285\right)=PGCD\left(285~; 30\right)PGCD(315 ;285)=PGCD(285 ;30)

285285 285 touche division euclidienne 303030 : Q=9 Q=9Q=9 et R=15R=15R=15 donc PGCD(285 ;30)=PGCD(30 ;15)PGCD\left(285~; 30\right)=PGCD\left(30~; 15\right)PGCD(285 ;30)=PGCD(30 ;15)

3030 30 touche division euclidienne 151515 : Q=2 Q=2Q=2 et R=0R=0R=0

On s'arrête car le reste est nul.

Le PGCD est le dernier reste non nul donc :

PGCD(600 ;315)=15PGCD\left(600~; 315\right)=15PGCD(600 ;315)=15.

Remarque

Si vous souhaitez vous entraîner à cette méthode, vous pouvez vérifier votre calcul et votre résultat grâce à cet outil : PGCD Algorithme d'Euclide

  Signaler une erreur

Dans ce chapitre...

Cours

  • Division euclidienne - Nombres premiers - PGCD

Exercices

  • facileCritères de divisibilité
  • facileDivisibilité: Vocabulaire
  • moyenPGCD : Simplification d'une fraction
  • moyenPGCD - Décompte de carreaux (Brevet Besançon 2005)
  • moyenProblème de partage (Brevet Nord 2006)

Méthodes

  • Décomposer un entier en produit de facteurs premiers

Outils

  • Outil : PGCD Algorithme d'Euclide

Quiz

  • moyenNombres premiers

VOIR AUSSI...

  • tableau de signe
  • loi de probabilité
  • fonction trigonométrique
  • suite géométrique
  • théorème de thalès
  • polynôme second degré
  • limites
  • fonction affine
  • théorème de pythagore
  • fonction exponentielle
  • division euclidienne
  • trigonométrie
  • python en seconde
  • fonction paire
  • loi normale
  • algorithme de dijkstra
  • tableau de variation
  • fonction dérivée

© 2021 - Maths-cours.fr - Nous contacter

Nous utilisons des cookies pour vous garantir la meilleure expérience sur notre site. Si vous continuez à utiliser ce dernier, nous considérerons que vous acceptez l'utilisation des cookies.Ok