Laurentvidal.fr vous aide à trouver des réponses à toutes vos questions grâce à une communauté d'experts passionnés. Découvrez des réponses fiables à vos questions grâce à une communauté d'experts prêts à partager leurs connaissances et expériences variées. Explorez des milliers de questions et réponses fournies par une communauté d'experts sur notre plateforme conviviale.
Sagot :
a. Remarque: Si a et b sont deux nombres entiers, a divise b signifie qu'il existe un nombre entier q tel que b=aq.
Par exemple 6 divise 54 signifie que 54 = 6x9 (ici q=9).
b. Définition: Le PGCD de deux nombres est leur plus grand diviseur commun.
Par exemple le PGCD de 30 et 25 est 5 car 5 divise à la fois 30 et 25 et il n'y a pas de nombre plus grand que 5 qui divise à la fois 30 et 25.
Pour deux nombres "pas trop grands", il est facile de trouver leur PGCD. Mais pour les nombres grands, c'est plus compliqué, mais il existe une méthode : l'Algorithme d'Euclide.
c. Propriétés: Soit a,b et c trois nombres entiers quelconques.
* Si a divise b et c, alors a divise b+c .
En effet a divise b signifie qu'il existe un nombre entier q tel que b=aq.
De même a divise c signifie qu'il existe un nombre entier p tel que c=ap.
Donc b+c=aq+ap=a(q+p) et donc a divise b+c.
* Si a divise b et b+c, alors a divise c.
En effet a divise b signifie qu'il existe un nombre entier q tel que b=aq.
De même a divise b+c signifie qu'il existe un nombre entier p tel que b+c=ap.
Donc c=ap-b=ap-aq=a(p-q) et donc a divise c.
2. Algorithme d'Euclide:
a. Remarque: Un algorithme est un procédé de calcul qui se répète plusieurs fois de suite jusqu'au résultat.
b. Algoritme: Soit a0 et b0 deux nombres entiers tel que a0 < b0. On cherche leur PGCD. Pour cela:
* Soit a0 divise b0, dans ce cas le PGCD de a0 et b0 est a0. En effet a0 divise a0 et a0 divise b0, il n'y a donc pas de nombre plus grand que a0 qui divise a0 et b0.
*Soit a0 ne divise pas b. Dans ce cas, il existe deux nombres q0 et r0 qui sont les quotient et reste de la division euclidienne de b0 par a0. On a
b0 =q0 x a0 + r0 .Le PGCD de a0 et b0 divise b0 et a0, donc en appliquant la deuxième propriété, ce PGCD divise r0.
On pose alors b1=a0 , a1 = r0 et on recommence:
il existe deux nombres r1 et q1 tel que b1=q1 x a1 + r1
ainsi de suite jusqu'à ce que l'on trouve un reste nul.
Le PGCD sera le dernier reste non nul !
c. Exemple: Appliquons cette méthode à la recherche du PGCD de 960 et 108.
960 = 8 x 108 + 96
On remplace 960 par 108 et 108 par 96 et on recommence:
108 = 1 x 96 + 12
On remplace 108 par 96 et 96 par 12 et on recommence:
96 = 8 x 12 + 0
Le dernier reste est 0, donc on s'arrête la. Le PGCD est le dernier reste non nul: c'est 12.
d. Définition: Si deux nombres a et b ont pour PGCD le nombre 1, alors on dit que a et b sont premiers entre eux.
Par exemple 6 divise 54 signifie que 54 = 6x9 (ici q=9).
b. Définition: Le PGCD de deux nombres est leur plus grand diviseur commun.
Par exemple le PGCD de 30 et 25 est 5 car 5 divise à la fois 30 et 25 et il n'y a pas de nombre plus grand que 5 qui divise à la fois 30 et 25.
Pour deux nombres "pas trop grands", il est facile de trouver leur PGCD. Mais pour les nombres grands, c'est plus compliqué, mais il existe une méthode : l'Algorithme d'Euclide.
c. Propriétés: Soit a,b et c trois nombres entiers quelconques.
* Si a divise b et c, alors a divise b+c .
En effet a divise b signifie qu'il existe un nombre entier q tel que b=aq.
De même a divise c signifie qu'il existe un nombre entier p tel que c=ap.
Donc b+c=aq+ap=a(q+p) et donc a divise b+c.
* Si a divise b et b+c, alors a divise c.
En effet a divise b signifie qu'il existe un nombre entier q tel que b=aq.
De même a divise b+c signifie qu'il existe un nombre entier p tel que b+c=ap.
Donc c=ap-b=ap-aq=a(p-q) et donc a divise c.
2. Algorithme d'Euclide:
a. Remarque: Un algorithme est un procédé de calcul qui se répète plusieurs fois de suite jusqu'au résultat.
b. Algoritme: Soit a0 et b0 deux nombres entiers tel que a0 < b0. On cherche leur PGCD. Pour cela:
* Soit a0 divise b0, dans ce cas le PGCD de a0 et b0 est a0. En effet a0 divise a0 et a0 divise b0, il n'y a donc pas de nombre plus grand que a0 qui divise a0 et b0.
*Soit a0 ne divise pas b. Dans ce cas, il existe deux nombres q0 et r0 qui sont les quotient et reste de la division euclidienne de b0 par a0. On a
b0 =q0 x a0 + r0 .Le PGCD de a0 et b0 divise b0 et a0, donc en appliquant la deuxième propriété, ce PGCD divise r0.
On pose alors b1=a0 , a1 = r0 et on recommence:
il existe deux nombres r1 et q1 tel que b1=q1 x a1 + r1
ainsi de suite jusqu'à ce que l'on trouve un reste nul.
Le PGCD sera le dernier reste non nul !
c. Exemple: Appliquons cette méthode à la recherche du PGCD de 960 et 108.
960 = 8 x 108 + 96
On remplace 960 par 108 et 108 par 96 et on recommence:
108 = 1 x 96 + 12
On remplace 108 par 96 et 96 par 12 et on recommence:
96 = 8 x 12 + 0
Le dernier reste est 0, donc on s'arrête la. Le PGCD est le dernier reste non nul: c'est 12.
d. Définition: Si deux nombres a et b ont pour PGCD le nombre 1, alors on dit que a et b sont premiers entre eux.
Nous apprécions votre temps. Revenez nous voir pour des réponses fiables à toutes vos questions. Merci de votre visite. Nous sommes dédiés à vous aider à trouver les informations dont vous avez besoin, quand vous en avez besoin. Merci de faire confiance à Laurentvidal.fr. Revenez pour obtenir plus d'informations et de réponses.
