PGCD(a,b) divise 25
Répondre à la discussion
Affichage des résultats 1 à 17 sur 17

PGCD(a,b) divise 25



  1. #1
    Jean-Luc97233

    PGCD(a,b) divise 25


    ------

    Bonjour

    Je suis bloqué sur une démonstration :

    on a :

    a=4n+11
    b=3n+2

    et on veut démontrer que pgcd(a,b) divise 25

    j'ai utilisé le lemme d'Euclide ce qui me donne pgcd(a,b)=pgcd(3n+2,n+9) mais je ne vois pas trop à quoi çà m'avance


    Merci d'avance

    Cordialement

    -----

  2. #2
    gg0
    Animateur Mathématiques

    Re : PGCD(a,b) divise 25

    Une étape de plus élimine les n et fait apparaître le 25.

    Cordialement.

  3. #3
    Jean-Luc97233

    Re : PGCD(a,b) divise 25

    En m'inspirant de ta remarque, voilà ce que j'obtiens :

    Si pgcd(a,b) divise 25 alors il existe k tel que k*pgcd(3n+2,n+9)=25
    d'ou pgcd(k(3n+2),k(n+9))=25

    avec k(3n+2)=25 et k(n+9)=25

    et par substitution j'obtiens k=2.

    Est ce bien cela ?

  4. #4
    Jean-Luc97233

    Re : PGCD(a,b) divise 25

    Je trouve qu'il y a quelque chose qui cloche dans ma démo

  5. A voir en vidéo sur Futura
  6. #5
    gg0
    Animateur Mathématiques

    Re : PGCD(a,b) divise 25

    Ce qui cloche, c'est que tu pars de la conclusion, ce qui est aberrant; et pour trouver une valeur d'une lettre qui ne fait pas partie du problème.

    pgcd(a,b)=pgcd(3n+2,n+9) =pgcd(n+9,(3n+2)-3(n+9))

  7. #6
    Jean-Luc97233

    Re : PGCD(a,b) divise 25

    Merci gg0. Une fois de plus je passe des heures à deux doigts de l'évidence.

    On a donc pgcd(a,b)=pgcd(n+9,25) qui est inclus dans l'ensemble des diviseurs D(n+9,25) donc pgcd(a,b) divise 25

    La question suivante est la détermination de n tel que pgcd(a,b)=1

    On a pgcd(a,b)=1 d'ou a et b sont premiers entre eux donc 25 ne divise pas n+9 d'ou 25k' différent de n+9 donc n différent de 25k'-9 avec k' entier relatif.

    En posant k=5k'. On a n différent de 5k-9.

    Est ce correct ?

    Cordialement

  8. #7
    gg0
    Animateur Mathématiques

    Re : PGCD(a,b) divise 25

    "On a pgcd(a,b)=1 d'ou a et b sont premiers entre eux donc 25 ne divise pas n+9 "
    Je ne comprends pas ce "donc". Quelle règle appliques-tu ?

    La suite n'a pas de sens, puisque k' et k ne sont pas définis.

  9. #8
    Jean-Luc97233

    Re : PGCD(a,b) divise 25

    OK OK OK, Manque de rigueur !

    On a montré que pgcd(4n+11,3n+2)=pgcd(n+9, abs(-25)) par utilisation du lemme d'Euclide.

    On a pgcd( 4n+11,3n+2) =1 d'ou pgcd(n+9,25)=1

    Par définition "deux nombres sont premiers entre eux s'il n'ont aucun facteur premier en commun" or 25=5*5 donc n+9 ne doit pas être divisible par 5 c'est à dire que pour tout entier relatif k, n+9 différent de 5*k donc n différent de 5*k-9.

    Qu'en penses tu ?

  10. #9
    gg0
    Animateur Mathématiques

    Re : PGCD(a,b) divise 25

    Il manque encore la réponse : comment est n ? Dit autrement : quels sont les entiers n pour lesquels pgcd(a,b)=1 ? Toi tu parles de certains n qui ne conviennent pas.

  11. #10
    Jean-Luc97233

    Re : PGCD(a,b) divise 25

    Bien sur, rigueur !, rigueur !

    L'ensemble des solutions est l'ensemble des entiers relatifs privé de 5*k-9 avec k entier relatif.

    Merci pour ta patience et ta rigueur.

    Cordialement

  12. #11
    gg0
    Animateur Mathématiques

    Re : PGCD(a,b) divise 25

    Et en remarquant que 9=10-1, on trouve que ce sont les entiers dont le reste modulo 5 est différent de 1. Reste plus qu'à le prouver ... (*)

    Cordialement.

    (*) tu as seulement montré que ceux dont le reste est 1 ne conviennent pas.

  13. #12
    Jean-Luc97233

    Re : PGCD(a,b) divise 25

    Oui, mais n'y a t-il pas équivalence entre les deux propositions :

    n différent de 5*k-9 avec k entier relatif.
    n différent de 5*k-10+1
    n différent de 5*(k-2)+1 ( reste = 1 ) est bien équivalent aux entiers dont le reste modulo 5 est différent de 1 non ?

  14. #13
    gg0
    Animateur Mathématiques

    Re : PGCD(a,b) divise 25

    Alors il va falloir bâtir ta preuve par équivalence dès le début. Ce qu tu n'as pas fait (message #8). Il me semble plus simple de vérifier que si n n'est pas congru à 1 modulo 5, pgcd( 4n+11,3n+2) =.

    Cordialement.

  15. #14
    Jean-Luc97233

    Re : PGCD(a,b) divise 25

    Je vois qu'entre hier et aujourd'hui, la variable âge a été incrémentée . Joyeux anniversaire !

    Quand le sage montre la lune, l'idiot regarde le doigt !

    j'avoue que tout m'échappe dans ta remarque : je pensais avoir décrit l'ensemble des solutions, et je conjecture que mon résultat est équivalent avec celui de la congruence. Qu'apporte donc de plus la congruence ?

    Soit n congru a 1 modulo 5 ( ensemble a éliminer par la suite ), il existe q entier naturel tel que n=5q+1
    soit donc pgcd(4(5q+1)+11,3(5q+1)+2)=5pg cd(4q+3,3q+1)= ???

    Je ne vois pas du tout ou tu veux en venir

    Cordialement

  16. #15
    gg0
    Animateur Mathématiques

    Re : PGCD(a,b) divise 25

    Merci !

    Tu as peut-être bien décrit l'ensemble des solutions, mais tu n'as pas prouvé que c'est effectivement l'ensemble des solutions. La seule chose que tu as prouvé, c'est que si n est solution, n n'est pas de la forme 5k-9, ou encore 5m+1. tu n'as pas prouvé que si n n'est pas de la forme 5k-9, ou encore 5m+1, alors n est solution.

    La congruence apporte une description immédiate des n qui conviennent : 0, 2,3,4,5, 7,8, ..., et sans doute le moyen de vérifier ce qui manque.

    Je n'ai pas trop compris pourquoi tu fais ce calcul :
    pgcd(4(5q+1)+11,3(5q+1)+2)=5pg cd(4q+3,3q+1)
    à part qu'il montre une fois de plus que dans ce cas, pgcd(a,b) est différent de 1 (ce qu'on sait déjà, avec ton début de preuve et l'équivalence du message #12. Ce n'est pas refaire ta preuve qui est nécessaire, mais en faire la réciproque.

    Si tu ne comprends pas, réécris exactement ce que tu as prouvé (en notant bien l'hypothèse et la conclusion, et le lien logique entre les deux).

    Cordialement.

  17. #16
    Jean-Luc97233

    Re : PGCD(a,b) divise 25

    Pour ce petit exercice on me demandais juste l'ensemble des solutions. La réciproque ne m'étais pas demandée...mais bon, soyons plus royaliste que le Roy

    Pour le calcul que tu n'a pas compris, je n'ai fait que partir des éléments que tu m'a proposé mais sans trop savoir quel était mon objectif final...No comment

    Je comprends tes explications petit à petit.

    Pour la réciproque, mon premier réflexe serait de procéder par l'absurde ( je n'ai pas encore bien analysé les rouages de ta proposition d'utilisation de la congruence ) :

    Supposons : pgcd(a,b)=1, c'est à dire pgcd(n+9,25)=1.
    Soit n=5k-9 avec k entier relatif, on a pgcd(5k+9-9,25)=pgcd(5k,25) avec 5k et 25 non premier entre eux donc gcd(5k,25) différent de 1 d'ou contradiction.
    Donc n différent de 5k-9.
    Idem pour 5m+1.

    Est ce correct ?

    Cordialement

  18. #17
    gg0
    Animateur Mathématiques

    Re : PGCD(a,b) divise 25

    Bon, je renonce.

    manifestement, tu n'as pas compris que tu n'as pas fait ce que tu dis. Tu n'as pas déterminé l'ensemble des solutions. Tu as juste prouvé que certains nombres ne sont pas des solutions ...

    Ciao !

Discussions similaires

  1. Divisé par 0
    Par invitec343ca4d dans le forum Mathématiques du supérieur
    Réponses: 20
    Dernier message: 22/05/2011, 19h42
  2. 1 divisé par 0
    Par invite25455aed dans le forum Mathématiques du collège et du lycée
    Réponses: 4
    Dernier message: 05/03/2010, 19h35
  3. Pf divise (Mf)^n
    Par invite6909706f dans le forum Mathématiques du supérieur
    Réponses: 3
    Dernier message: 22/06/2007, 19h16
  4. [TS] a^n divise b^n+c
    Par invite0edb71fb dans le forum Mathématiques du collège et du lycée
    Réponses: 10
    Dernier message: 01/05/2007, 20h25
  5. PGCD : est-il possible de retrouver A et B en connaissant le PGCD, Q, et R ?
    Par inviteae2308e6 dans le forum Mathématiques du supérieur
    Réponses: 3
    Dernier message: 31/05/2005, 19h54