leçon n°11 sur le pgcd CAPES

Posté par pauppau pauppau

Bonsoir à tous,
Je suis en train de préparer la leçon n°11 sur le pgcd de deux nombres entiers et je ne sais pas trop comment le définir..
En fait je voudrais dire : le plus grand diviseur commun à a et b, noté pgcd(a,b) est d € N tel que d/a et d/ b et s'il existe d' divisant a et b alors d'/d.
Mais mon problème c'est que j'ai peur qu'on me demande de démontrer la partie d'/d..
Comment le faire simplement ??

Parfois le pgcd est défini comme D(a)D(b)=D(d).. là on trouve une démonstration mais je la trouve longue et pas trop simple..
Voilà je suis un peu perdue, j'espère que vous pourrez m'aider
Merci d'avance

Posté par kioups kioups

Bonsoir,

c'est une définition, pas un théorème, donc aucune raison qu'on te demande de le définir.

A vue d'oeil, le PGCD de deux entiers A et B est le plus grand entier naturel D qui divise A et B.

Cet entier existe car 1 divise A et B.

Une proposition-définition tirée du Monier MPSI Algèbre :

Soient n appartenant à N*, (x1,...xn) appartenant à (Z*)^n.
L'ensemble des diviseurs communs  à x1,...,xn est fini et admet un plus grand élément appelé PGCD.

Preuve :
Cet ensemble est fini et contient 1, donc ce plus grand élément existe.

Voili, voilou !

Posté par pauppau pauppau

Merci beaucoup pour votre réponse, mais ce qui me pose problème c'est le d'/d car dans la définition on sait que d'd mais pas forcément d'/d non ??

Comment le montrer ??

Posté par kioups kioups

Ben, comme tu peux le lire dans ces définitions, tu n'es pas obligé de mettre ça. Je ne vois d'ailleurs pas bien l'intérêt. On veut le Plus Grand Diviseur Commun, s'il est plus grand, on a gagné, pas d'intérêt à savoir que c'est un multiple des autres diviseurs communs. Cela me paraît d'ailleurs évident, mais je ne vois pas bien comment le prouver...

Posté par Drysss Drysss

Si vous voyez les anneaux pour le Capes, tu peux faire la théorie du pgcd dans les anneaux intègres commutatifs dans un premier temps puis dans les anneaux principaux comme Z.

(Ou au moins savoir que ca existe, les examinateurs apprécieraient surement)

Posté par pauppau pauppau

bonsoir à tous,
j'ai su trouver la solution de mon problème
Je vous en fait par au cas où ceci vous intéresse.
Il faut partir de l'identité de bezout :
si d=pgcd(a,b) alors il existe deux entiers naturels u,v tel que au+bv=d.
Ceci se montre facilement en remontant l'algorithme d'Euclide.

finalement, si d'/a et d'/b, d'/au+bv =>d'/d

Merci à tous d'avoir chercher à m'aider

Posté par plumemeteore plumemeteore

Bonjour Pauppau.
a et b accueillent tous les facteurs de d et de d' avec leurs exposants respectifs
Supposons que d' ne divise pas d; il a au moins soit un facteur étranger à d, soit un facteur avec un exposant plus grand que dans d.
Soit g le produit réunissant les facteurs premiers appartenant à d ou à d' avec leur plus grand exposant dans l'un ou l'autre.
g contient tous les facteurs de d avec un exposant supérieur ou égal, avec éventuellement des facteurs nouveaux; g est un multiple de d et comme il est de composition différente, il est plus grand que d
a accueille tous les facteurs de d et tous les facteurs de d' avec leurs exposants
a accueille donc tous les facteurs appartenant à d ou à d' avec leurs plus grand exposants dans l'un ou l'autre, c'est-à-dire qu'il accueille tous les facteurs de g avec leurs exposants, ou qu'il est divisible par g.
De même b est divisible par g.
La supposition de départ mène à une conclusion fausse : g est un diviseur commun à a et à b plus grand que leur pgcd d; elle doit donc être rejetée.