2- PPCM (∨) et PGCD (∧)

2.1 Le plus petit commun multiple

2.1.1 Définition

Soit (a;b) ∈ℤ².
Le plus petit commun multiple de a et b est le plus petit entier positif multiple de a et b, noté a∨b ou ppcm(a;b).

2.1.2 Exemples

1) On pose a=8 et a=10.
Les multiples de 8 ≤ 8x10=80 sont 1; 8; 16; 24; 32; 40; 48;..; 80.

Les multiples de 10 ≤ 10x8=80 sont 1 ; 10 ; 20 ; 30 ; 40 ;.. on s'arrête à ce point car 40 est un multiple de 8 et de plus 40 est le plus petit multiple commun donc 8∨10=40.
2) On pose a=10 et b=20.
10|20 donc 10∨20=20.
3) On pose a=7 et b=5.
les multiples de 7 ≤ 7x5=35 sont 1 ; 7 ; 14 ; 28 ; 35.
Les multiples de 5 ≤ 5x7=35 sont 1 ; 5 ; 15 ; 20 ; 30 ; 35 donc 5∨7=35.

2.2 Le plus grand commun diviseur

2.2.1 Définition

Soit (a;b) ∈ℤ².
Le plus grand diviseur commun de a et b, noté a∧b ou pgcd(a;b) est le plus grand entier positif diviseur de a et b.
En d'autre terme si D_a et D_b sont respéctifs les ensembles des diviseurs de a et b
alors a∧b=d ⇔ d∈D_a∩D_b et ∀p∈D_a∩D_b: d≥p.

2.2.2 Exemple

75∧50=25 et 24∨14=84.

2.2.3 Propriété (crible d'Eratosthène)

Soit n un entier > 1.
1) Si n n'est pas premier alors le(s) diviseur(s) premier(s) de n sont ≤√n.
2) Si aucun nombre premier ≤ √n ne divise pas n alors n est premier.

Exercice 1 tp

Tester si n=127 est premier ?

Correction

√127=11,54...
Les nombres premiers ≤11 sont 2 ; 3 ; 5 ; 7 et 11.
2∤127 car 127 est impair.
3∤127 car la somme de chiffres de 127 ne divise pas 127.
5∤127 car l'unité de 127 n'est pas 5 ou 0.
7∤127 car 127÷7=18,14...
11∤127 car 127÷11=11,54..
alors 127 est un nombre premier.

Exercice 2 tp

Tester si n=247 est premier ?

Correction

√247=15,71..
Les nombres premiers ≤15 sont 2 ; 3 ; 5 ; 7 ; 11 et 13
2∤247 car 253 n'est pas pair.
3∤247 car la somme de chiffres de 247 ne divise pas 247.
5∤ car l'unité de 247 n'est pas 5 ou 0.
7∤247 car 247÷7=35,28..

11∤247 car 247÷11=3,207..
13|247 car 247÷13=19
donc 247 n'est pas premier.

2.2.4 Propriétés

1) avb=m ⇒ a|m et b|m.
2) a∧b=d ⇒ d|a et d|b.
3) (p|a et p|b) ⇒ p|a∧b.
4) (avb)x(a∧b)=|a×b|.

lemme d'Euclide Soient p un nombre premier et (a;b)∈ℤ²
(p|axb) ⇒ (p|a ou p|b ou les deux).

2.2.5 Conséquence

Soient p₁ ; p₂ ; ... ; p_n des entiers naturels premiers et d un nombre premier.
d|p₁×p ... ×p_n ⇒ (∃i∈{1;2;...;n}) d=p_i.

Exemple
Soit d un nombre premier tel que d|182.
182=2x7x13 donc d=2 ou d=7 ou d=13.