Pgcd de deux nombres entiers


  • L

    Bonsoir,
    je n'arrive pas à montrer que si (x;y) avec x et y qui sont des inconnues et des entiers sont solution de l'équation x + y - 1 = Pgcd (x;y), alors le Pgcd de x et de y est égal à 1. Pourriez-vous m'aider? Merci d'avance

    *EDIT Zorro = j'ai mis des espaces dans l'expression x + y - 1 car il y avait un bug d'affichage *


  • Zorro

    Bonsoir,

    J'ai supprimé les 2 autres messages envoyés en doublon.

    Je dois avouer mon incompétence en arithmétique ! Attendons que quelqu'un de plus compétent passe par ici.


  • Zorro

    J'ai quand même un doute sur l'énoncé ! Qu'est x1 ? un paramètre quelconque ?

    Prenons un exemple
    Si (x;y) est solution de PGCD(x;y) = 7 , alors je ne vois pas comment on arrivera à PGCD(x;y) = 1


  • L

    l'équation est x-1=Pgcd(x,y) entre le x et le 1 il y a un moins


  • Zorro

    en effet il y a un bug d'affichage moi je ne vois que x1 alors que si je cherche à modifier ton premier message il y a x + y - 1 = Pgcd(x;y)

    lors est-ce x - 1 = Pgcd(x;y) ou x + y - 1 = Pgcd(x;y) ?

    P.S.

    N'abuse pas du bouton "Envoyer" j'ai encore supprimé 2 messages doublons !!!!! la prochaine fois je serais moins sympa !


  • Zorro

    Si c'est x + y - 1 = Pgcd(x;y) soit x + y = 1 + Pgcd(x;y)

    une idée réponse :

    soit d = PGCD (x ; y) Alors il existe x' et y' premiers entre eux tels que x=dx' et y=dy'.

    L'égalité x + y = 1 + PGCD (x ; y) s'écrit x + y = 1 + d

    donc dx' + dy' = 1 + d donc dx' + dy' - d = 1

    soit encore d(x'+y'-1)=1, donc d = 1 et x' + y' - 1 = 1 donc d = 1 et x' + y' = 2

    On en déduit que x' = 1 et y' = 1 et surtout que d = 1


  • Zorro

    Pour la 2ème question :

    En déduire que si (x;y) est solution, alors x ou y est impair. Je ne sais pas comment m'y prendre Pourriez-vous m'aider? Merci d'avance

    Il faut raisonner par l'absurde ! Si x est pair et y aussi alors PGCD(x ; y) ne peut pas être 1


  • L

    Si tu suppose que x est pair alors on pose : x=2k avec k un entier quelconque.
    Ton équation devient :
    2k + y - 1 = pgcd(2k;y)

    Si y pair alors PGCD(x,y)=2 ce qui n'est pas possible car si on pose cette fois-ci ,y=2k' on a alors

    2k + 2k' - 1 différent de Pgcd(2k;2k') . Le premier terme de l'équation donnerait un nombre impair alors que l'autre terme un nombre pair.

    SI y impair, là encore imposible. Si tu pose , y=2k' on a :2(k+k')=Pgcd(2k+(2k+1)) . Premier terme : pair et deuxième terme : impair.

    Donc par contraposée, ta question est vérifiée

    Edit Zorro : ajout d'espaces dans les expresssions qui ne s'affichait pas correctement


  • Zorro

    Pour moi si y est impaire il ne s'écrit pas y = 2k' mais 2k' + 1

    et là ton équation (pas la miennne) se transforme bien en

    2k + 2k' + 1 - 1 = PGCD(2k ; 2k'+1) pas PGCD(2k+2k'+1)

    Si tu recopies sans comprendre, avec des erreurs, cela risque de moins bien marcher !

    Tu as vu le raisonnement "par contraposée" ?


Se connecter pour répondre