Ppcm

  

et donc noté :
d = pgcd (a,b) ou d = ab

- trouver l’ensemble des diviseurs de chaque nombre.
- lister les diviseurs communs dans l’ordre croissant et prendre le plus grand.

Rappel  :

Si la décomposition en facteurs premiers de a est :
Alors, tout diviseur d de a s’écrit :
avec pour tout i compris entre 1 et m : 0 < _i < _i

Avec pour tout i compris entre 1 et n : _i = min (_i ; _i)

- décomposer chaque nombre en produit de facteurs premiers.
- affecter aux facteurs premiers communs l’exposant le plus petit.

3) Si une des divisions a un reste égal à 1 alors pgcd (a,b) = 1 car le reste suivant strictement inférieur à 1 ne peut être que nul.

a et b sont dits premiers entre eux si  pgcd (a,b) = 1

si et seulement si
il existe u et v entiers relatifs tels que : a x u + b x v = 1

Propriété n° 1

Quel que soit k, entier naturel non nul : si pgcd (a,b) = 1 alors pgcd (ka,kb) = k

si k est un relatif non nul : (ka,kb) = _lk_l

Propriété n° 2

pgcd (a,b) = d
⇔
il existe a’ et b’ entiers relatifs tels que : a = da’ et b = db’ avec pgcd (a’,b’) = 1

2) Elle peut également être utilisée pour trouver le PGCD de deux nombres écrits sous la forme d’un produit de deux facteurs.

Exemple : 55 = 5 x 11 et 65 = 5 x 13.
11 et 13 sont premiers entre eux donc d’après la réciproque le PGCD de 55 et 65 est 5.

Propriété n° 1 ( étendue )

Quel que soit k, entier naturel non nul : pgcd (ka,kb) = kpgcd (a,b)
si k est un relatif non nul : pgcd (ka,kb) = _lk_lpgcd (a,b)

Propriété n° 3 : ( extension du sens direct du Théorème de Bézout )

Si pgcd (a,b) = d alors il existe u et v entiers relatifs tels que  : a x u + b x v = d

Propriété n° 4 :

Si d entier non nul peut s’écrire d = a x u + b x v avec u et v entiers relatifs alors : pgcd (a,b) divise d.

Propriété n°5

Tout diviseur commun à a et b divise le pgcd de a et b

Si a divise bc et a et b premiers entre eux alors a divise c.

Notons M(a) l’ensemble des multiples de a et  M(b) celui des multiples de b.
L’ensemble de leurs multiples communs est noté :  M(a,b). 
M(a,b) =  M(a)  M(a) ;

ab est un multiple de a et de b donc  M(a,b) n’est pas vide.
M(a,b) étant un sous ensemble non vide de , il admet un plus petit élément.

Propriété n° 1 : soient a et b deux entiers naturels non nuls.

Si  pgcd (a,b) = 1  alors  ppcm (a,b) = ab 
( ou _lab_l si a et b sont des relatifs non nuls.)

m est un multiple de b donc b \ m
d’où b \ am’

Or a et b sont premiers entre eux donc d’après le théorème de Gauss : b \ m’.
D’où, il existe m’’ entier naturel non nul tel que : m’ = bm’’.

m = abm’’ par conséquent ab \ m.

ab est donc inférieur à tout multiple commun à a et b,

or ab est lui-même un multiple commun à a et b
donc ab est le ppcm de a et b.

Propriété n° 2 :soient a et b deux entiers naturels non nuls.

Quel que soit k, entier naturel non nul : si pgcd (a,b) = 1  alors ppcm (ka, kb) = kab
( ou _lkab_l s’il s’agit de relatifs )

m est un multiple de kb donc kb \ m
d’où kb \ kam’.

Il existe donc k’’ entier naturel non nul tel que : kam’ = kbk’’

Or k est non nul donc : am’ = bk’’, d’où : b \ am’.

Propriété n° 3 :Relation entre le PGCD et le PPCM.

pgcd (a,b) x ppcm (a,b) = a x b

Propriété n° 2 ( étendue ) : soient a et b deux entiers naturels non nuls.

Quel que soit k, entier naturel non nul : ppcm (ka,kb) = kppcm (a,b)

pgcd (ka,kb) x ppcm (ka,kb) = ka x kb
(k x pgcd (a,b)) x ppcm (ka,kb) = k² x ab
(k x pgcd (a,b)) x ppcm (ka,kb) = k² x pgcd(a,b) x ppcm (a,b)

En simplifiant par k x pgdc (a,b) qui est nul, on obtient donc :
ppcm (ka,kb) = k x ppcm (a,b)

Propriété n° 4 : soient a et b deux entiers relatifs.

Tout multiple commun à a et b est un multiple du ppcm de a et de b.

Démonstration pour des entiers naturels  :
Soit d le PGCD de a et de b.

Alors, il existe a’ et b’ entiers naturels non nuls tels que : a = da’ et b = db’
avec a’ et b’ premiers entre eux.

D’où d’après la propriété n° 2 étendue : ppcm (a,b) = ppcm (da’, db’) = dppcm (a’,b’)

= da’ b’ car a’ et b ’ premiers entre eux

Soit m multiple commun à a et b.

m est multiple de a donc il existe k entier naturel non nul tel que : m = ka

m est multiple de b
donc : b \ ka soit : db’ \ kda’.

Or d’ non nul donc b’ \ ka’.
b’ est premier avec a’ donc d’après le théorème de Gauss : b’ \ k.

Il existe donc k’’ entier naturel non nul tel que : k = k’’b’.
D’où : m = k’’ b’ a = k’’ b’ da’ = k’’ppcm (a,b)

Conclusion : m est un multiple du ppcm de a et b.

Remarque :
On dit alors que le ppcm est également le plus petit multiple au sens de la division.

De plus, réciproquement :
tout multiple du ppcm de a et de b est un multiple commun à a et b donc :

Les multiples communs à a et b sont les multiples du ppcm de a et de b.

3/ Recherche du PPCM : à l’aide du PGCD

Méthode n° 1 :

- calculer le pgcd à l’aide d’une des méthodes vues dans le module sur le PGCD.
- en déduire le ppcm à l’aide de sa relation au pgcd.

Rappels des méthodes vues pour le PGCD :
1) lister tous les diviseurs communs et prendre le plus grand.

2) utiliser la décomposition en facteurs premiers.

3) chercher le dernier reste non nul dans l’algorithme d’Euclide.

Application : chercher le PPCM de 3780 et 792.
Commençons donc par chercher leur PGCD à l’aide par exemple de l’algorithme d’Euclide.

 Le pgcd est le dernier reste non nul donc pgcd (3780,792) = 36

Or : pgcd (3780,792) = 3780,792 x 792

donc :

3/ Recherche du PPCM : décomposition en facteurs premiers

Si on appelle p1, p2, ... , pn les facteurs premiers figurant
soit dans la décomposition de a soit dans celle de b alors a et b s’écrivent :

Avec pour tout i compris entre 1 et n : _i  > 0 et _i

Soit m multiple commun à a et à b :
a \ m et b \ m donc la décomposition de m doit comporter tous les p_i

d’où pour tout m multiple commun à a et à b :

Avec pour tout i compris entre 1 et n :

Le plus petit multiple étant celui qui a les puissances les plus petites :

Avec pour tout i compris entre 1 et n : 

Méthode n° 2  :

- décomposer chaque nombre en produit de facteurs premiers.
- affecter à chaque facteur premier commun l’exposant le plus grand.
- conserver l’exposant des facteurs premiers non communs.

Application : reprenons l’exemple de a = 3780 et b = 792.

3780 = 2² x 3³ x 5 x 7  792 = 2² x 3² x 11 

D’où ppcm (3780,792) = 2³ x 3³ x 5 x 7 x 11 = 83160