Pgcd

[alexisdu06]

Bonjour,

Je suis nouveau sur le forum, j'aurais besoin de votre précieuse aide pour résoudre l'exercice suivant proposé par mon prof:

Donner une condition sur les entiers m et n pour que pgcd(m+2n;m-n)=pgcd(m;n).

La condition doit reposer uniquement sur les entiers m et n et non sur le pgcd. :help:

Merci à tous d'avance.

[DamX]

Bonjour,

Je suis nouveau sur le forum, j'aurais besoin de votre précieuse aide pour résoudre l'exercice suivant proposé par mon prof:

Donner une condition sur les entiers m et n pour que pgcd(m+2n;m-n)=pgcd(m;n).

La condition doit reposer uniquement sur les entiers m et n et non sur le pgcd. :help:

Merci à tous d'avance.

Bonjour,

Je te lance sur une piste pour trouver une condition suffisante.

Note p le pgcd de m+2n et m-n. Avec des combinaisons de c'est deux là, tu vois que dans ce cas p divise 3m et p divise 3n.

PaRtant de là, dans quel cas peux-tu dire que p divise n et m ? Qu'est-ce que cela a pour conséquence ?

Damien

[alexisdu06]

Bonsoir,

Merci de ta réponse Damien mais je cherche une condition nécessaire et suffisante, c'est vrai que j'aurais dû précisé.

Sinon, pour ta condition, p divise 3n et p divise 3n, si p est premier avec 3 alors p divise n et p divise m. Donc si m et n ne sont pas multiples de 3, on a p=pgcd(m;n) (car d'une part p divise pgcd(m;n) et d'autre part pgcd(m;n) divise m+2n et m-n donc pgcd(m;n) divise p).

[DamX]

Bonsoir,

Merci de ta réponse Damien mais je cherche une condition nécessaire et suffisante, c'est vrai que j'aurais dû précisé.

Sinon, pour ta condition, p divise 3n et p divise 3n, si p est premier avec 3 alors p divise n et p divise m. Donc si m et n ne sont pas multiples de 3, on a p=pgcd(m;n) (car d'une part p divise pgcd(m;n) et d'autre part pgcd(m;n) divise m+2n et m-n donc pgcd(m;n) divise p).

Et bien en fait non. P n'a rien à voir avec m et n donc cette conclusion "si m et n ne sont pas multiples de 3" est fausse. D'ailleurs Contre-exemple : m=4, n=1 pgcd=1, mais m+2n= 6 et m-n=3-> pgcd= 3!

En fait je ne sais pas exactement comment le montrer proprement mais il me semble que la condition est :
Soit k le plus grand entier tel que 3^k|m et 3^k|n (on enlevé le maximum de "3" de leurs compositions)

Alors pgcd(m,n)=pgcd(m+2n,m-n) ssi 3 ne divise pas (m/3^k - n/3^k)

Damien

[Doraki]

pgcd(m+2n;m-n) = pgcd(m-n ; 3m)
pgcd(m;n) = pgcd(m-n ; m)

pgcd(m-n ; 3m) = pgcd(m-n ; m)
<=> il existe a et b tels que m = a(m-n)+b(3m)
<=> il existe a et b / an = m(a+3b-1)

on fait 3 cas selon la valeur de a modulo 3, pour obtenir :
<=> il existe c et d / (3c)n = m(3d+2) ou (3c+1)n = m(3d) ou (3c+2)n = m(3d+1)

En fait, à part quand m=n=0, on est dans 1 exactement 1 des 4 cas de figures disjoints suivant :
(pour n non nul il suffit par exemple de regarder le repésentant irréductible de m/n, qui donne l'une des 8 possibilités)

il existe c et d / (3c)n = m(3d+2) <=> il existe c et d / (3c)n = m(3d+1)
il existe c et d / (3c+1)n = m(3d) <=> il existe c et d / (3c+2)n = m(3d)
il existe c et d / (3c+2)n = m(3d+1) <=> il existe c et d / (3c+1)n = m(3d+2)
il existe c et d / (3c+1)n = m(3d+1) <=> il existe c et d / (3c+2)n = m(3d+2)


Donc pgcd(m-n ; 3m) = pgcd(m-n ; m) <=> on est dans les 3 premiers cas <=> on est pas dans le dernier cas <=> n=0 ou le représentant irréductible de la fraction m/n n'est pas de la forme (3c+1)/(3d+1) ni (3c+2)/(3d+2).

[nodjim]

Doraki, j'avoue avoir un peu de mal à suivre, pourrais tu trouver un exemple avec des pgcd différents ?

[alexisdu06]

Bonjour,

Oui, Damien, il était tard, j'ai un peu tout mélangé désolé, j'ai fait comme si p était le pgcd de m et n.

Excuse-moi Doraki mais je ne comprends pas d'où viennent tes équivalences dans tes 4 cas. Et qu'est-ce qu'un représentant irréductible?

Merci à tous les deux de vos réponses.