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

PPCM et PGCD



  1. #1
    ofifi

    PPCM et PGCD


    ------

    Je ne comprend pas de PPCM (le plus petit commun multiple) et PGCD (le plus grand commun diviseur)de deux ou plusieurs nombres.

    -----

  2. Publicité
  3. #2
    GuYem

    Re : PPCM et PGCD

    Salut, je ne comprends pas ta question, il doit manquer des mots

    Le PPCM de a et b, comme son nom l'indique, est le plus petit multiple commun de ces deux nombres. Par exemple le nombre ab est clairement un multiple commun à a et b ; mais ce n'est pas forcément le plus petit. Pour être encore plus concret;
    avec a=36 et b=24 le PPCM est 72 et non pas 36*24.

    Le PGCD de a et b, comme son nom l'indique, est le plus grand commun diviseur à a et b. Par exemple 1 est un diviseur à la fois de a et de b, mais ce n'est pas forcément le plus grand! Pour être encore plus concret:
    avec a=36 et b=24 le PGCD est 12 et non pas 1.

    En espérant t'avoir un peu éclairé.
    Bravo jolie Ln, tu as trouvé : l'armée de l'air c'est là où on peut te tenir par la main.

  4. #3
    Pole

    Re : PPCM et PGCD

    PPCM(a,b)=(a*b)/PGCD(a,b)

    Le PGCD est le plus grand k entier où l'on peut écrire
    a=d*k et b=e*k
    Pour les trouver on peut multiplier tout les nombres premiers qui apparaissent dans la décomposition des deux nombres.
    Il y a aussi l'algorithme d'Euclide (vu en 3ème) :
    c=a mod b (reste de la division de a par b)
    b=a
    a=c
    et on recommence tant que c est différent de 0. Le PGCD est b.
    Exemple (a=10,b=15) :
    a=2*5 b=3*5 le PGCD est donc 5.
    algorithme d'Euclide :
    c=15;b=10;a=15
    c=5;b=15;a=5
    c=0;b=5;a=0
    donc le PGCD est 5.
    Le premier algorithme est rapide pour les nombres de 2 chiffres et il peut être appliqué de tête pour ces nombres.
    Le deuxième algorithme est rapide (complexité polynomiale) pour les grands nombres mais il ne peut pas être appliqué de tête.

    Doublé par GuYem le temps d'écrire tout ça.
    Pour comprendre la récursivité croisée, il faut comprendre les arbres d'appels. Et vice versa.

  5. #4
    Penelope20k

    Re : PPCM et PGCD

    PPCM(a,b)=(a*b)/PGCD(a,b)
    juste une question c 'est une division , ou une division eucvlidienne .. parceque ca na pas l'air de bien marcher cette formule
    a moins que je lise mal ..

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

    Re : PPCM et PGCD

    oops ..forgive me ...

  8. #6
    GuYem

    Re : PPCM et PGCD

    C'est bien une division, et qui tombe juste par dessus le marché cela dit ce n'est pas dur de voir que PGCD(a,b) divise ab !

    Cependant d'habitude on ne prends pas ça comme définition du PPCM mais plutôt celle que j'ai donnée plus haut.

    Après c'est une réelle difficulté que de démontrer l'égalité ab = PGCD.PPCM ...
    Bravo jolie Ln, tu as trouvé : l'armée de l'air c'est là où on peut te tenir par la main.

  9. Publicité
  10. #7
    Pole

    Re : PPCM et PGCD

    Citation Envoyé par GuYem
    Après c'est une réelle difficulté que de démontrer l'égalité ab = PGCD.PPCM ...
    a=c*k
    b=d*k
    PPCM(a,b)=b*c=a*d
    PGCD(a,b)=k
    PPCM(a,b)*PGCD(a,b)=b*c*k =a*d*k
    =(c*k)*b=(d*k)*a
    =a*b =b*a
    Et voilà.
    Pour comprendre la récursivité croisée, il faut comprendre les arbres d'appels. Et vice versa.

  11. #8
    GuYem

    Re : PPCM et PGCD

    Citation Envoyé par Pole
    a=c*k
    b=d*k
    PPCM(a,b)=b*c=a*d
    PGCD(a,b)=k
    PPCM(a,b)*PGCD(a,b)=b*c*k =a*d*k
    =(c*k)*b=(d*k)*a
    =a*b =b*a
    Et voilà.
    Comment tu justifies ça ?

    Il faut forcément utiliser quelque part le fait que c et d sont premiers entre eux.
    Bravo jolie Ln, tu as trouvé : l'armée de l'air c'est là où on peut te tenir par la main.

  12. #9
    Pole

    Re : PPCM et PGCD

    Citation Envoyé par GuYem
    Comment tu justifies ça ?

    Il faut forcément utiliser quelque part le fait que c et d sont premiers entre eux.
    Exact, j'ai oublié de mettre que c'est le plus grand k entier.
    Pour comprendre la récursivité croisée, il faut comprendre les arbres d'appels. Et vice versa.

  13. #10
    GuYem

    Re : PPCM et PGCD

    Certes mais la justification du fait que le PPCM vaut bien ce que tu dis demande encore un peu de travail.

    Je n'ai jamais su faire cette démonstration, c'est pour ça que j'en parle!
    Bravo jolie Ln, tu as trouvé : l'armée de l'air c'est là où on peut te tenir par la main.

  14. #11
    Pole

    Re : PPCM et PGCD

    Citation Envoyé par GuYem
    Certes mais la justification du fait que le PPCM vaut bien ce que tu dis demande encore un peu de travail.

    Je n'ai jamais su faire cette démonstration, c'est pour ça que j'en parle!
    b*c=a*d car b*c=(b*a)/k et a*d=(a*b)/k

    Si le "vrai" PPCM est plus petit, il divise forcément b*c (et donc a*d). Il doit donc diviser b ou c. Et aussi a ou d. (c'est pas très clair mais bon) Or j'ai montré que d et c sont premier entre eux. Donc le petit PPCM divise a et b. Ce qui dit que PPCM(a,b)<a et <b ce qui est absurde.

    Reste à faire le cas où le vrai PPCM est plus grand.
    Pour comprendre la récursivité croisée, il faut comprendre les arbres d'appels. Et vice versa.

  15. #12
    tartampion

    Re : PPCM et PGCD

    Ce qui est intéressant avec cette question, c'est que j'ai entendu un ingé qui fait maintenant que des cours particuliers me dire que la plupart des bac+ machin ne savent pas résoudre des exos qui sont tirés du Collège et dont la solution est fondée sur la notion de PPCM et de PGCD.

    Et ben, vous savez quoi : je n'ai pas osé lui avouer qu'il m'était arrivé cette mésaventure quand j'étais étudiant et que je donnais des cours à un élève. J'avais donné une mauvaise méthode de résolution suite à la reprise d'un brevet blanc. La honte.

    A réviser donc.

  16. Publicité
  17. #13
    Pole

    Re : PPCM et PGCD

    Je m'autocite :
    Citation Envoyé par Pole
    b*c=a*d car b*c=(b*a)/k et a*d=(a*b)/k
    .....
    Reste à faire le cas où le vrai PPCM est plus grand.
    Comme c'est le Plus Petit Commun Multiple, c'est que b*c=a*d est faux. Et comme il est multiple de a et de b, c'est un multiple commun de a et b. Et comme on cherche le Plus Petit, b*c est forcément le PPCM de a et b. (voir message au-dessus)
    Pour comprendre la récursivité croisée, il faut comprendre les arbres d'appels. Et vice versa.

  18. #14
    ericcc

    Re : PPCM et PGCD

    Je ne suis pas entièrement convaincu par le raisonnement de Pole. Pour ma part j'ai toujours utilisé la décomposition de a et b en facteurs premiers. C'est un peu laborieux mais straightforward : on écrit a et b sous la forme de produits de facteurs premiers. On fait de meme avec b. On écrit explicitement le produit ab.
    Ensuite on identifie l'ensemble des facteurs communs, soit PGCD(a,b), et on vérifie que ce qui reste est le PPCM(a,b).

  19. #15
    invité576543
    Invité

    Re : PPCM et PGCD

    Soit c un diviseur commun de a et b, alors a*b/c = a * (b/c) = b * (a/c) donc a*b/c est un commun multiple.

    Réciproquement, si d est un CM qui divise ab, d/a et d/b sont entiers, alors a = (ab/d) d/b et b = (ab/d) d/a montrent que ab/d est un CD

    On a donc

    c CD => ab/c est un CM qui divise ab

    et

    d est un CM qui divise ab => ab/d est un CD

    De là facile de montrer que si d est le plus petit, c est le plus grand; et réciproquement.
    Dernière modification par invité576543 ; 02/12/2005 à 18h14.

Discussions similaires

  1. PGCD et PPCM
    Par martienne dans le forum Mathématiques du collège et du lycée
    Réponses: 22
    Dernier message: 30/10/2008, 19h19
  2. PPcm, Pgcd
    Par elicie23 dans le forum Mathématiques du collège et du lycée
    Réponses: 2
    Dernier message: 23/06/2008, 15h00
  3. PGCD et PPCM
    Par nicoroller dans le forum Mathématiques du supérieur
    Réponses: 8
    Dernier message: 14/11/2006, 19h47
  4. [ex] pgcd / ppcm
    Par n0unours dans le forum Mathématiques du supérieur
    Réponses: 5
    Dernier message: 02/01/2006, 14h26
  5. Pgcd,ppcm
    Par sensor dans le forum Mathématiques du supérieur
    Réponses: 25
    Dernier message: 25/11/2005, 18h25