Répondre à la discussion
Affichage des résultats 1 à 8 sur 8

Pgcd



  1. #1
    milsabor

    Pgcd


    ------

    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

    -----
    "J'ai comme l'impression d'avoir moi même quelques problèmes avec ma propre existence"

  2. #2
    Bleyblue

    Re : Pgcd

    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.

  3. #3
    milsabor

    Re : Pgcd

    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.
    ..
    "J'ai comme l'impression d'avoir moi même quelques problèmes avec ma propre existence"

  4. #4
    zinia

    Re : Pgcd

    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 !

  5. A voir en vidéo sur Futura
  6. #5
    milsabor

    Re : Pgcd

    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
    "J'ai comme l'impression d'avoir moi même quelques problèmes avec ma propre existence"

  7. #6
    zinia

    Re : Pgcd

    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 ...."

  8. #7
    milsabor

    Re : Pgcd

    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?
    "J'ai comme l'impression d'avoir moi même quelques problèmes avec ma propre existence"

  9. #8
    zinia

    Re : Pgcd

    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

Discussions similaires

  1. Pgcd
    Par gwendaelle dans le forum Mathématiques du collège et du lycée
    Réponses: 6
    Dernier message: 20/11/2007, 21h08
  2. Pgcd
    Par M I L A S dans le forum Mathématiques du supérieur
    Réponses: 5
    Dernier message: 08/11/2007, 19h10
  3. Pgcd!
    Par maths_comme_maths dans le forum Mathématiques du collège et du lycée
    Réponses: 2
    Dernier message: 04/10/2007, 18h07
  4. PGCD and co
    Par prof shadoko dans le forum Mathématiques du collège et du lycée
    Réponses: 3
    Dernier message: 08/01/2007, 21h49
  5. PGCD : est-il possible de retrouver A et B en connaissant le PGCD, Q, et R ?
    Par frhs dans le forum Mathématiques du supérieur
    Réponses: 3
    Dernier message: 31/05/2005, 19h54