PGCD.



  • Bonjour, cet exercice ci-dessous me pose problème, puisque je trouve une infinité de couples de solutions:

    1/ Donner l'ensemble des diviseurs de 85 dans N.
    2/ Résoudre dans N le système:{x-y= 84 et PGCD(x,y)= 12.

    Or, même en suivant le cheminement, je n'arrive toujours pas à trouver le nombre exact de couple solutions, pour la 2/.

    Toute aide est la bienvenue et je vous remercie de celle que vous voudriez bien m'apporter.


  • Modérateurs

    Salut,

    1/ Je suppose que tu as pu répondre à cette question. Le seul soucis pour moi est que je n'ai pas trouvé de rapport entre cette question et la suivante.

    Je te propose quand même ma solution pour la question 2 puisqu'elle fonctionne.

    2/ Il existe 2 nombres x' et y' premiers entre eux tels que x=12x' et y=12y' et que PGCD(x';y')=1

    Le systéme se ramène donc à :
    {x'-y'=7
    {PGCD(x';y')=1
    avec x'>y'

    Or le PGCD de x' et de y' est égal au PGCD de y' et x'-y' donc :
    PGCD(y';7)=1
    C'est à dire que y' ne peut pas être un multiple de 7 (7 étant un nombre premier). Alors cela fait une multitude de solutions (que je te laisse le soin de formaliser toi-même ...)
    Si y'=1 alors x'=8 d'où y=12 et x=96
    Si y'=2 alors x'=9 d'où y=24 et x=108
    etc ... toutes les valeurs de y' sont bonnes sauf les multiples de 7.

    Bon ... si on te propose une autre solution, j'aimerais bien la connaitre ...



  • Je suis d'accord, on tombe sur le système [x' = y' + 7 et pgcd (x',y') = 1] comme expliqué ci-dessus.
    Or pgcd (x',y') = 1 ssi pgcd (y'+7,y') ssi y' n'est pas un multiple de 7 (démo facile à faire)

    Donc y' est de la forme 7k+r où k est un entier et r =1 ou 2 ou... ou 6.

    Par regroupement, les solutions (x',y') sont de la forme
    ( 7(k+1)+r, 7k+r) où k est un naturel qcq et r un entier entre 1 et 6.

    x et y s'en déduisent facilement...



  • Je vous remercie pour l'aide apportée et le temps passé.


Se connecter pour répondre
 

Il semble que votre connexion ait été perdue, veuillez patienter pendant que nous vous re-connectons.