PPCM et PGCD

[invite5b27b6d6]

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

[GuYem]

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

[invite3d7be5ae]

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.

[invite6f0362b8]

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

[A voir en vidéo sur Futura]

[invite6f0362b8]

oops ..forgive me ...

[GuYem]

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

[invite3d7be5ae]

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

[GuYem]

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.

[invite3d7be5ae]

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.

[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!

[invite3d7be5ae]

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.

[invited955b97b]

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.

[invite3d7be5ae]

Je m'autocite :

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)

[ericcc]

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

[invité576543]

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.