Le résultat connu sous le nom de
lemme d'Euclide correspond à la Proposition 30 du Livre VII des
Éléments d'Euclide. Il énonce que
Une généralisation est connue sous le nom de lemme de Gauss:
ThéorèmeSi un
nombre entier a
divise le produit de deux autres nombres entiers b et c, et que a et b sont premiers entre eux, alors a divise c.
Ceci peut être noté de façon formelle :
∀ (a, b, c) ∈Z 3 , ( a|bc ∧ PGCD (a,b) = 1 ) ⇒ a|c
Dans le traité de Gauss, les Disquisitiones arithmeticae, l'énoncé du lemme d'Euclide constitue la proposition 14 (section 2) et est utilisée pour prouver la théorème de factorisation en nombres premiers. Le lemme de Gauss en découle (article 19).
Les noms de ces deux propositions sont parfois confondus. On notera d'ailleurs que le lemme de Gauss apparaît déjà dans les Nouveaux Eléments de mathématiques de Jean Prestet au 17e siècle.
Démonstration
Soit
(a,b,c) ∈Z 3 , avec
PGCD (a,b) = 1 et
a|bcComme a est premier avec b, d'après l'identité de Bezout, il existe donc deux entiers u et v tels que :
ua + vb = 1
Multiplions membre à membre par c :
uac + vbc = c
Comme a | bc, il existe k tel que bc = ka, d'où :
u a c + v k a = c
( u c + v k ) a = c
Cette relation montre que a | c.
Conséquences
Première conséquence
Enoncé
Soient
a et
b deux entiers naturels non nuls et
p un nombre premier. Si
p divise le produit
ab, alors
p divise
a ou p divise
b.
(Cet énoncé est en fait la forme originelle du Lemme d'Euclide
.)- ∀ (a,b) ∈Z 2 , ∀ p ∈P, p|ab ⇒ ( p|a ∨ p|b )
Démonstration
- Si
p divise
a, alors la propriété est établie.
- Si p ne divise pas a, alors p et a sont premiers entre eux, puisque les seuls diviseurs positifs de p sont 1 et p. Ainsi, p est premier avec a, or p divise ab, donc d'après le théorème de Gauss, p divise b.
Deuxième conséquence
Enoncé
Soient
a,
b et
c des entiers naturels non nuls. Si
b et
c sont premiers entre eux et divisent
a, alors
bc divise
a.
- ∀ (a,b,c) ∈Z 3 , ( b|a ∧ c|a ∧ PGCD (b,c) = 1 ) ⇒ bc|a
Démonstration
-
b divise
a donc il existe un entier naturel
k tel que
a =
kb.
- c divise a donc il existe un entier naturel l tel que a = lc. c divise lc donc c divise kb, or c est premier avec b, donc d'après le théorème de Gauss, c divise k. Il existe donc un entier naturel m tel que : k = mc. a = kb = mbc, d'où bc divise a.
Généralisation
Soient
a ∈Z,
n ∈ N * et
(b i ) i ∈ ∈{Z * } n vérifiant
∀ (i,j) ∈ 2 , i ≠ j ⇒ PGCD (b i ,b j ) = 1.
- On a alors :
( | n Π i = 1 | b i | ) | |a ∀ i ∈, b i | a |
Troisième conséquence
Enoncé
Pour un rationnel
r, il existe un unique couple d'entiers
p et
q premiers entre eux, q strictement positif, tels que r vaut p divisé par q.
-
∀ r ∈Q, ∃ !(p,q) ∈Z × N * ,(( PGCD (p,q) = 1) ∧ | ( | r = | p –– q | ) | ) |
Démonstration
Soit
r ∈ Q r ∈Q ⇒ ∃ (p,q) ∈Z × N * , r = | p –– q |
On note d = PGCD (p,q).
d | p ⇒ ∃ p 0 ∈ Z, p = d p 0 .
De même, d | q ⇒ ∃ q 0 ∈ N * , q = d q 0 .
Montrons que PGCD (p 0 ,q 0 ) = 1.
Par l'Identité de Bézout, ∃ (a,b) ∈Z 2 , a p + b q = d.
On a donc a d p 0 + b d q 0 = d.
D'où a p 0 +b q 0 = 1.
L'Identité de Bézout montre que PGCD (p 0 ,q 0 ) = 1.
On a .
D'où .
Le couple (p 0 ,q 0 ) convient donc bien.
Soit (p 1 ,p 2 ,q 1 ,q 2 ) ∈{Z} 2 × {N * } 2 vérifiant :
-
r = | p 1 ––– q 1 | = | p 2 ––– q 2 |
- PGCD (p 1 ,q 1 ) = PGCD (p 2 ,q 2 ) = 1
On a donc p 1 q 2 = p 2 q 1 .
q 2 | p 1 q 2 , donc q 2 | p 2 q 1 .
Or PGCD (p 2 ,q 2 ) = 1. Le théorème de Gauss montre que q 2 | q 1 .
De même, q 1 | p 1 q 2 . Or PGCD (p 1 ,q 1 ) = 1. Donc, par le théorème de Gauss, q 1 | q 2 .
D'où q 1 = q 2 , car (q 1 ,q 2 ) ∈N 2 .
Puis p 1 = p 2 .
La forme irréductible d'un rationnel est donc unique.
Réciproque du lemme de Gauss
Si
a,b sont deux entiers tels que, pour tout entier c, a divise bc implique que a divise c alors a et b sont premiers entre eux.
En effet, soit d un diviseur commun à a et b : on peut écrire a = a 'd et b = b 'd. Par hypothèse, comme a divise ba ', on a que a divise a ' donc d = 1, CQFD.
Références
Voir aussi
A lire avant