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

PPCM et PGCD



  1. #1
    invite5b27b6d6

    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. #2
    invitedf667161

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

  3. #3
    invite3d7be5ae

    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.

  4. #4
    invite6f0362b8

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

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

    Re : PPCM et PGCD

    oops ..forgive me ...

  7. #6
    invitedf667161

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

  8. #7
    invite3d7be5ae

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

  9. #8
    invitedf667161

    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.

  10. #9
    invite3d7be5ae

    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.

  11. #10
    invitedf667161

    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!

  12. #11
    invite3d7be5ae

    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.

  13. #12
    invited955b97b

    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.

  14. #13
    invite3d7be5ae

    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)

  15. #14
    inviteaf1870ed

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

  16. #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 à 19h14.

Discussions similaires

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