Bonjour
Ma question est dans le cadre d'un exercice de spécialité maths: dans une question je dois trouver le PGCD de x= 22005+1 et de y= 22006+1. On peut assi écrire y=2x-1, mais je n'ai aucune piste...ah si, l calculatrice me donne le resultat assez rapidement, il doit donc y avoir une astuce quelque part.
Pouvez vous m'aiguiller?
Cordialement
Salut,
Il y a une méthode que j'ai apprise durant le mois de Décembre dernier et qui utilise les congruences modulo (tu connais ?)
Je ne m'en souviens plus bien mais je peux aller revoir mes notes et essayer d'expliquer
EDIT : Aie non je confonds avec autre chose, qui n'a rien à voir je pense (désolé)
Dernière modification par Bleyblue ; 31/05/2006 à 18h27.
Oui, c'est amusant moi aussi je voulais me servir de congruences, mais en fait apres reflexion il me semble que ça n'a aucun rapport... je ne vois pas comment m'en sortir.
..
bonjour,
Si p est un diviseur premier de x, essaie de voir ce que devient ton équation y = 2x -1 modulo p.
Tu dois pouvoir conclure plus vite que ta machine !
exact! je crois que je vois
si la decomposition en facteurs premiers de x s'écrit x=p*k
alors y=2*p*k+1, donc le reste de la division de y par n'importe quel facteur premier de x sera 1
donc x et y n'ont aucun facteur premier en commun
donc leur pgcd est 1
Y-a-t il une meilleure façon de rédiger ou cela suffit-t-il? merci du coup de main en tout cas zinia
Tu as transformé un -1 en +1 mais ça ne change rien aux conclusions.
A propos de rédaction, x=kp n'est pas une décomposition en facteurs premiers (k n'est pas forcément premier), il vaut dire "si p est un facteur premier de x, alors ...."
J'ai trouvé une autre solution:
x= 22005+1 et de y= 22006+1
on a aussi y=2x-1
D'où 2x-y=1
et la on utilise le théorême de Bezout!
1 est la cobinaison libnéaire de x et y, d'où x et y sont premiers entre eux
(Bezout: 2 entiers a et b premiers entre eux ssi il existeu et v tels que au + bv =1)
Ca marche non?
Bonsoir,
Oui, le théorème de Bezout dit bien qu'il faut et il suffit qu'il existe u v et tu as bien
2 x + (-1) y = 1
