A) Plus Petit Commun Multiple (PPCM)

Soient \(a\) et \(b\) deux entiers relatifs non nuls et A l’ensemble des entiers naturels non nuls appartenant à (\( \mathbb{Z}\) \( \cap \) \( \mathbb{Z}\)).
\(\left| {ab} \right| \in A\); donc A, partie non vide de \( \mathbb{N}\), admet un plus petit élément.

A.1) Définition

Soient \(a\) et \(b\) deux entiers relatifs non nuls
On appelle plus petit commun multiple de \(a\) et \(b\), le plus petit élément strictement positif de (\( \mathbb{Z}\) \( \cap \) \( \mathbb{Z}\)).

Exemple :
On a : \(16\) \( \mathbb{Z}\) \( = \{ ...; - 24;\) \( - 12;0;16;\) \(32;48;64;\) \(80;96;...\} \)
\(12\) \( \mathbb{Z}\) \( = \{ ...; - 24;\) \( - 12;0;24;\) \(36;60;72;\) \(84;...\} \)
\(12\) \( \mathbb{Z}\) \( \cap \) \(16\) \( \mathbb{Z}\) \( = \{ ...; - 48;\) \(0;96;...\} \)
\(PPCM\left( {12,16} \right)\) \( = 48\)

Remarques
Pour tous entiers relatifs non nuls 4a4 et \(b\), on a \(PPCM\left( {a,b} \right) = \) \(PPCM\left( {\left| a \right|,\left| b \right|} \right)\)
Dans une recherche de PPMC, on peut se ramener à la recherche du PPMC de deux entiers naturels non nuls.
Pour tous entiers relatifs non nuls \(a\) et \(b\), on a : \(Max\left( {a,b} \right) \le \) \(PPCM\left( {a,b} \right) \le \) \(ab\)
Pour tous entiers relatifs non nuls \(a\) et \(b\), on a : \(PPCM\left( {a,b} \right) = \) \(a \Leftrightarrow a \in b\) \( \mathbb{Z}\)

A.2) Propriétés

Propriété I :
Soient \(a\) et \(b\) deux entiers naturels non nuls et \(\mu \) leur \(PPMC\)
On a : \(a\) \( \mathbb{Z}\) \( \cap \) \(b\)\( \mathbb{Z}\) = \(\mu \) \( \mathbb{Z}\)

Propriété II

Soient \(a\), \(b\) et \(k\) trois entiers naturels non nuls, on a : \(PPMC\left( {ka,kb} \right)\) \( = kPPMC\left( {a,b} \right)\)

B) PGCD de deux entiers relatifs

B.2) Définition

Soient \(a\) et \(b\) deux entiers relatifs non nuls.
L’ensemble des diviseurs communs à \(a\) et \(b\), notée \(d\left( {a,b} \right)\), contient 1 et est fini. Il admet donc un plus grand élément, strictement positif.

On appelle plus grand diviseur commun de \(a\) et \(b\), et on le note \(PGCD\left( {a,b} \right)\), le plus grand élément de \(d\left( {a,b} \right)\).
En d’autres termes : Soient \(a,b \in \) \( \mathbb{Z^2}\) deux entiers, non tous les deux nuls. Le plus grand entier qui divise à la fois \(a\) et \(b\) s’appelle le plus grand commun diviseur de \(a \) et \( b\) et se note \(PGCD\left( {a;b} \right)\).

Exemple :
\(d\left( {24} \right) = \{ - 24; - 12;\) \( - 8; - 6; - 4; - 3;\) \( - 2; - 1;0;1;2;3;\) \(4;6;8;12;24\} \)
\(d\left( {30} \right) = \{ - 30;\) \( - 15; - 10; - 6;\) \( - 5; - 3; - 2; - 1;\) \(0;1;2;3;5;\) \(6;10;15;30\} \)
\(d\left( {24;30} \right) = \{ - 6;\) \( - 3; - 2; - 1;0;\) \(1;2;3;6\} \)
\(PGCD\left( {24;30} \right)\) \( = 6\)

Remarques :
• Pour tous entiers relatifs non nuls \(a\) et \(b\), on a : \(PGCD\left( {a;b} \right) = \) \(PGCD\left( {\left| a \right|;\left| b \right|} \right)\).
• Pour tous entiers relatifs non nuls \(a\) et \(b\), on a : \(1 \le PGCD\left( {a;b} \right)\) \( \le Min\left( {a;b} \right)\).
• Pour tous entiers relatifs non nuls \(a\) et \(b\), on a : \(PGCD\left( {a;b} \right) = \) \(b \Rightarrow b \in \) \(d\left( a \right)\).

Propriétés 1 :
Pour tous entiers relatifs non nuls \(a\) et \(b\) et \(\delta \) leur PGCD. On a \(d\left( {a; b} \right) = \) \(d\left( \delta \right)\).

Propriété II
Soient \(a\), \(b\) et \(k\) trois entiers naturels non nuls.
On a : \(PPCD\left( {ka;kb} \right) = \) \(k.PPCD\left( {a;b} \right)\)

Propriété 3
Soient \(a\) et \(b\) deux entiers naturels non nuls et \(\delta \) leur PGCD
Un entier relatifs \(m\) est un multiple de \(\delta \) si et seulement s’il existe deux entiers relatifs \(u\) et \(v\) tels que \(m = au + bv\). C’est-à-dire que \(\delta \) \( \mathbb{Z}\) \( = \{ au + bv,\) \(\left( {u;v} \right) \in \) \( \mathbb{Z^2}\)

C. Recherche pratique du PGCD et du PPCM : Algorithme d’Euclide

C.1 Algorithme d’Euclide

On appelle Algorithme d’Euclide, toute opération visant à déterminer le PGCD des deux entiers \(a\) et \(b\) en effectuant les divisions Euclidiennes successives.

Propriété I
Soient \(a\) et \(b\) deux entiers naturels tels que \(a \succ b \succ 0\) et \(r\) le reste de la division euclidienne de \(a\) par \(b\).
• Si \(r=0\), alors \(d\left( {a;b} \right) = d\left( b \right)\)
• Si \(r \ne 0\), alors \(d\left( {a;b} \right) = d\left( {b;r} \right)\)

Propriété I
Soient \(a\) et \(b\) deux entiers naturels tels que \(a \succ b \succ 0\) et \(r\) le reste de la division euclidienne de \(a\) par \(b\).
• Si \(r=0\), alors \(PGCD\left( {a;b} \right) = b\)
• Si \(r \ne 0\), alors \(PGCD\left( {a;b} \right) = PGCD\left( {b;r} \right)\)

C.2 Recherche du PGCD

Pour déterminer le PGCD de deux entiers naturels \(a\) et \(b\) tels que \(a \succ b \succ 0\), on effectue les divisions euclidiennes successives suivantes :
• Division de \(a\) par \(b\), pour obtenir \(a = b \times {q_0}\) \( + {r_0}\) ( avec \(0 \le {r_0} \prec b\))
• Division de \(b\) par \(r_0\), pour obtenir \(b = {r_0} \times {q_1}\) \( + {r_1}\) ( \(0 \le {r_1} \prec {r_0} \prec b\))
• Division de \(r_0\) par \(r_1\), pour obtenir \({r_0} = {r_1} \times {q_2} + {r_2}\) ( avec \(0 \le {r_2} \prec {r_1}\) \( \prec {r_0} \prec b\))
• …..
Toutes ces opérations peuvent être résumées dans un tableau appelé : tableau d’Algorithme.

C.3 Relation entre le PGCD et le PPCM de deux entiers naturels

Propriété
Soient \(a\) et \(b\) deux entiers naturels non nuls, \(\delta \) leur PGCD et \(\mu \) leur PPMC, alors \(\mu \times \delta = ab\)