Lemme d'Euclide

Infos
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: Ceci peut être noté de façon formelle : :\forall (a, b, c)\in\mathbb^3, ( a|bc \land \operatorname(a, b)=1 ) \Rightarrow a|c Dans le traité de Gauss, les Disquisitiones arithmeticae, l'énoncé du lemme d'Euclide constitue la proposition 14 (section 2) et
Lemme d'Euclide

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: Ceci peut être noté de façon formelle : :\forall (a, b, c)\in\mathbb^3, ( a|bc \land \operatorname(a, b)=1 ) \Rightarrow 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 17 siècle , vol. 2, p. 338-339..

Démonstration

Soit (a, b, c)\in\mathbb^3, avec \operatorname(a, b)=1 et a|bc Comme 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.)
- \forall (a, b)\in\mathbb^2, \forall p\in\mathbb, p|ab \Rightarrow ( p|a \lor 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.
- \forall (a, b, c)\in\mathbb^3, ( b|a \land c|a \land \operatorname(b, c)=1 ) \Rightarrow 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\in\mathbb Z, n \in \mathbb^
- et (b_i)_i\in\in\mathbb^
-^n vérifiant \forall (i, j)\in^2, i\ne j \Rightarrow\operatorname(b_i, b_j)=1. :On a alors : \left( \prod_^n b_i \right)|a \Longleftrightarrow \forall i\in, 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.
- \forall r\in\mathbb, \exists !(p, q)\in\mathbb\times\mathbb^
-, \left( \left(\operatorname(p, q)=1\right) \land \left(r=p \over q\right)\right)

Démonstration

Soit r \in \mathbb
- Existence r \in\mathbb \Rightarrow \exists (p, q)\in\mathbb\times\mathbb^
-, r = \frac On note d = \operatorname(p, q). d | p \Rightarrow \exists p_0 \in \mathbb, p = d p_0. De même, d | q \Rightarrow \exists q_0 \in \mathbb^
-, q = d q_0. Montrons que \operatorname(p_0, q_0)=1. Par l'identité de Bézout, \exists (a, b)\in\mathbb^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 \operatorname(p_0, q_0)=1. On a \frac = \frac. D'où \frac = \frac. Le couple (p_0, q_0) convient donc bien.
- Unicité Soit (p_1, p_2, q_1, q_2)\in\mathbb^2\times\mathbb^
-^2 vérifiant :
- r = \frac = \frac
- \operatorname(p_1, q_1) = \operatorname(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 \operatorname(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 \operatorname(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)\in\mathbb^2. Puis p_1 = p_2. La forme irréductible d'un rationnel est donc unique.

Voir aussi

- Euclide
- Théorème fondamental de l'arithmétique
- Algorithme d'Euclide

A lire avant

- Divisibilité
- PGCD Catégorie:Divisibilité et factorisation Euclide Lemme en:Euclid's lemma fa:لم اقلیدس it:Lemma di Euclide lb:Lemma vum Euklid pl:Lemat Euklidesa ru:Лемма Евклида uk:Лема Евкліда zh:歐幾里德引理
Sujets connexes
Algorithme d'Euclide   Disquisitiones arithmeticae   Diviseur   Divisibilité   Décomposition en produit de facteurs premiers   Euclide   Identité de Bézout   Nombre premier   Théorème fondamental de l'arithmétique  
#
Accident de Beaune   Amélie Mauresmo   Anisocytose   C3H6O   CA Paris   Carole Richert   Catherinettes   Chaleur massique   Championnat de Tunisie de football D2   Classement mondial des entreprises leader par secteur   Col du Bonhomme (Vosges)   De viris illustribus (Lhomond)   Dolcett   EGP  
^