Pgcd

[invite4a9059ea]

Bonjour,

j'ai du mal avec la question suivante, si quelqu'un pouvait m'éclairer ...

Quels sont les conditions nécessaires et suffisantes pour que pgcd(m,n) = pgcd(m+n,m-2n) ?

Merci
Cdt
-----

[Médiat]

Bonjour,

Et qu'avez-vous fait/essayé ?

[invite4a9059ea]

Bonjour Médiat,

L'ennui c'est que je ne sais pas trop comment m'y prendre avec cet exercice, j'ai du mal avec l'arithmétique !

[Médiat]

Déjà vous pouvez remarquer que le PGCD n'est défini (sauf avis contraire dans l'énoncé) que pour les nombres entiers naturels (positifs donc), cela vous donne une première condition simple.

Vous pouvez aussi remarquer (démontrer) que si un nombre divise m et n, alors il divise m + n et m - 2n (si positif), et en fait toutes les combinaisons linéaires de m et n.

Ce n'est pas suffisant, mais un début ...

[A voir en vidéo sur Futura]

[invite4a9059ea]

Le pgcd étant défini que pour les entiers naturels positifs , on en déduit que m et
Soit d = pgcd(m,n) alors d|m et d|n
si d est un diviseur commun à m et n alors d est un diviseur de toute combinaisons linéaires de m et n et en particulier un diviseur du pgcd de ces combinaisons linéaires .
On a donc d|m+n et d|m-2n ce qui implique que d|pgcd(m+n,m-2n) ,
donc d=pgcd(m,n) pgcd(m+n,m-2n).
De même, soit d'=pgcd(m+n,m-2n) avec m+n et m-2n deux entiers naturels strictement positifs.
On a donc d'|m+n et d'|m-2n donc d'| 2(m+n)+(m-2n)=3m et d'|(m+n)-(m-2n)=3n
donc d'|pgcd(3m,3n) c.à.d d'|3pgcd(m,n)
Si d' {1,3} alors d'|pgcd(m,n) et donc dans ce cas d'=pgcd(m+n,m-2n) pgcd(m,n)

conclusion :
Si pgcd(m+n,m-2n) {1,3} alors on a bien l'égalité pgcd(m,n)= pgcd(m+n,m-2n) , avec m,n,m+n,m-2n entiers naturels strictement positifs .

Est-ce correct ? manque-t-il des conditions ?

cdt

[invite4842e1dc]

Salut

Voici quelques commentaires suite à ton message (pour te faire réfléchir et qui sont peut être à confirmer par un "spécialiste") :

Pour démontrer l'égalité pgcd(m,n) = pgcd(m+n,m-2n) (mais pas "obligatoirement" pour pouvoir trouver une CNS)
une des solutions est de démontrer que l'ensemble des diviseurs communs de m et n est égal à l'ensemble des diviseurs communs de m+n et m-2n
en démontrant une "double" inclusion ( c'est à dire en faisant une sorte de réciproque" )

Remarque 1 :
Il faut peut être spécifier quelque part dans le raisonnement que

Remarque 2 :
Dans "la réciproque" on a :
si d divise m+n et si d divise m-2n alors d divise 3m et d divise 3n

Et donc on peut écrire que si d ne divise pas 3 alors d divise m et n


Conclusion : l'ensemble des diviseurs communs de m et n est égal à l'ensemble des diviseurs communs de m+n et m-2n si {1,3} n'appartiennent pas à l'ensemble des diviseurs communs de m+n et m-2n
et dans ce cas on a bien : pgcd(m,n) = pgcd(m+n,m-2n)

Questions :
Mais que se passe-t-il si {1,3} appartiennent à cet ensemble ?
Est qu'on a , dans ces 2 cas : pgcd(m,n) = pgcd(m+n,m-2n) ?