Overblog Suivre ce blog
Editer l'article Administration Créer mon blog
27 juin 2011 1 27 /06 /juin /2011 12:00

 

Dans cet article je donne la méthode la plus connue pour trouver le PGCD de deux entiers : l'algorithme d'Euclide.

 

Nous disposons de deux nombres a et b. On peut choisir les lettres de sorte que a soit le plus grand des deux.

Si j'effectue la division euclidienne de a par b, alors j'obtiens deux nombres uniques qet r comme ci-dessous :

a=bq+r, où 0r<b

 

r est le reste de la division euclidienne etq le quotient.

 

Propriété. Sir est le reste de la division euclidienne de a par b, alors PGCD(a,b)=PGCD(b,r).

 

La preuve : Soit D=PGCD(a,b). Ddivise aet bdonc a=Da'et b=Db'. Ainsi a=bq+r donneDa'=Db'q+r d'oùr=Da'-Db'q=D(a'-b'q). Donc Ddivise aussi r.

SoitE=PGCD(b,r). E divise bet rdonc b=Eb''et r=Er''. Ainsi a=Eb''+Er''=E(b''+r''). DoncE divisea.

Mais Edivisant aet divisant b, Edivise nécessairement Dpuisque c'est le plus grand des diviseurs communs à aet à b. Aussi Ddivisant bet r, divise également Epour une raison similaire.

Ainsi D=E. Autrement dit PGCD(a,b)=PGCD(b,r).

FIN DE LA PREUVE

 

On peut donc ramener après une division le calcul d'un PGCD à un calcul plus facile puisque les nombres en jeu sont plus petits.

 

Exemple.Calcul de PGCD(1758,125).

1758=125×14+8

Donc PGCD(1758,125)=PGCD(125,8).

Les diviseurs de 125 sont 1,5,25,125

Les diviseurs de 8 sont 1,2,4,8

Donc PGCD(125,8)=1.

 

J'aurai pu aussi effectuer la division euclidienne de 125 par 8 :

125=8×15+5

Donc PGCD(125,8)=PGCD(8,5)

Puis

8=1×5+3

Donc PGCD(8,5)=PGCD(5,3), puis

5=1×3+2

Donc PGCD(5,3)=PGCD(3,2), puis

 

3=1×2+1

Donc PGCD(3,2)=PGCD(2,1) car 1 n'a que 1 comme diviseur positif.

Ainsi par ces divisions euclidiennes successives, on aboutit au PGCD(1758,125) sans connaître tous les diviseurs de 1758 et ni ceux de 125.

 

Cette méthode est valable pour tous les calculs de PGCD, c'est l'algorithme d'Euclide.

 

Algorithme d'Euclide

Soit a et b deux entiers. On note a0=aet a1=b. On effectue les divisions successives :

 

a0= a1q1+a2

a1= a2q2+a3

.........................

as-2= as-1qs-1+as

.........................

Les restes étant de plus en plus petits, on a les inégalités :

a1 > a2 > a3 ...... >as .... ≥0

Nécessairement, à partir d'une certaine étape le reste est nul, autrement dit, il existe une étape d pour laquellead =0 etad -1>0. Et donc

ad-3= ad-2qd-2+ad-1

ad-2= ad-1qd-1+ad= ad-1qd-1

Comme dans l'exemple, on a

PGCD(a,b)=PGCD(a0,a1)=PGCD(a1,a2)=.....=PGCD(ad-2,ad-1)=PGCD(ad-1,0)= ad -1

 

Propriété. Le PGCD de aet best le dernier reste non nul dans les divisions euclidiennes successives.

 

Remarque : PGCD(c,0)=c en effet tout entier est diviseur de 0.

Partager cet article

Repost 0
Published by Maths_Buchwald - dans Nombres
commenter cet article

commentaires

Présentation

  • : Maths Otak'
  • Maths Otak'
  • : Au départ, j'ai créé ce blog pour y publier des articles reliant Maths et histoire de l'art et la culture. Maintenant, il me permet d'aborder des sujets simples de la culture mathématique. J'aime parler de jeux vidéos. Vous trouverez aussi sur ce site des fiches de maths et Histoire des Arts de 2009-2010 au format *.pdf. Je ne sais pas où me mène ce blog donc il ne sera sans doute plus le même si je continue à l'alimenter dans un an. N'hésitez pas à laisser des commentaires.
  • Contact

Twitter

Recherche

Mes vidéos

Catégories