Calculer le pgcd

[aviateurpilot]

salut tt le monded

Soient m et n des entiers premiers entre eux. Calculer le pgcd
des entiers et

merci d'avance pour vos réponces

[aviateurpilot]

:pi::pi::pi:

[aviateurpilot]

personne ne veut esquiser une reponse ?

[Mikou]

Salut,
Il est evident que
De plus on sait ( on peut le demontrer tres facilement ) que le pgcd de deux nombres pairs est un nombre pair.
Comme m et n sont supposés premiers entre eux soit ils sont tout les deux de la forme 2n+1 soit l'un est de la forme 2n et lautre 2n+1 ( en effet deux nombres pairs ne sont jms premiers entre eux )

* cas 1 :
Par symetrie des roles, on prendera m pair et n impair.
comme on a divisible par 2
Apresent il nous suffit de justifier que si m paire alors n'est divisible qu'une seule fois par deux ( autrement dit sont unique diviseur pair est 2 )
Cela ce fait tres bien par recurrence.
On suppose la propriete vraie au rang m (pair) ( elle est verifiée biensur au rang 0 )
au rang m+2 (le premier nb pair successif a m) :
On conclut qu'au rang m+2 admet comme seul diviseur pair : 2


Conclusion le pgcd de avec m pair et n impair est 2


Il reste encore le cas 2 a traiter: m;n tt deux impairs et premiers entre eux

[aviateurpilot]

alors si m et n ont une parité différente
avec b impair
le pgcd c pas 2 d'apres ce que t'a fait

[Mikou]

NON ! il ne peut etre diviser que par 2 ! pas par 4 , pas par 6 ... seulement par 2 :happy3:

[aviateurpilot]

ah oui mikou t'a raison

[aviateurpilot]

si n>ou=2m

si 2m>n


donc dans tous les cas car
on pose
alors (1)
en utilisant l'operation (1) on va seurement trouver que A=pgcd(f(r),f(r')) avec r et r'
moi je pense que ca sera les rests de la divisition de m et n par 2
si c vrai
si n et m ont une parité differente A=pgcd(f(1),f(0))=pgcd(12,2)=2 c ce que ta trouve mikou
et si n et m ont la meme parité A=pgcd(f(1),f(1))=pgcd(12,12)=12
mais j'en suis pas sure :hein:
quelqu'un peut confirmer ou me montrer ou es l'erreur?