Lemme d'Euclide

En mathématiques le lemme d'Euclide est un résultat d'arithmétique élémentaire qui correspond à la Proposition 30 du Livre VII des Éléments d'Euclide. Il énonce que :

Théorème — Si un nombre premier $p$ divise le produit de deux nombres entiers $b$ et $c$ , alors $p$ divise $b$ ou $c$ .

Une généralisation est connue sous le nom de lemme de Gauss :

Théorème — Si un nombre entier a divise le produit de deux autres nombres entiers b et c, et si a est premier avec b, alors a divise c.

Ceci peut être noté de façon formelle :

$\forall (a, b, c)\in\mathbb{Z}^3, ( a|bc \land \operatorname{PGCD}(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 éléments de mathématiques de Jean Prestet au XVII^e siècle^[1].

Le lemme d'Euclide se généralise aux polynômes (cf l'article Arithmétique des polynômes), ainsi qu'à tout anneau factoriel.

Démonstration

Soit $(a,b,c)\in\mathbb{Z}^3$ , avec $\operatorname{PGCD}(a,b)=1$ et $a | b c$

Comme a est premier avec b, d'après le théorème de Bachet-Bézout, il existe donc deux entiers relatifs u et v tels que :

u a + v b = 1

Multiplions membre à membre par c :

u a c + v b c = c

Comme $a | b c$ , il existe un entier relatif 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

Énoncé

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{N}^2, \forall p\in\mathbb{P}, 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

Énoncé

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{N}^3, ( b|a \land c|a \land \operatorname{PGCD}(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 c divise kb. Comme c est premier avec b, d'après le théorème de Gauss, c divise k.
Il existe donc un entier naturel m tel que : k = mc.
Ainsi, a = kb = mbc. Autrement dit, bc divise a.

Généralisation

Soient $a\in\mathbb Z$ , $n \in \mathbb{N}^*$ et $(b_i)_{i\in[1,n]}\in{\mathbb{Z}^*}^n$ vérifiant $\forall (i,j)\in[1,n]^2, i\ne j \Rightarrow\operatorname{PGCD}(b_i,b_j)=1$ .

On a alors : $\left( \prod_{i=1}^n b_i \right)|a \Longleftrightarrow \forall i\in[1,n], b_i | a$

Troisième conséquence

Énoncé

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{Q}, \exists !(p,q)\in\mathbb{Z}\times\mathbb{N}^*, \left( \left(\operatorname{PGCD}(p,q)=1\right) \land \left(r={p \over q}\right)\right)$

Démonstration

Soit $r \in \mathbb{Q}$

Existence

$r \in\mathbb{Q} \Rightarrow \exists (p,q)\in\mathbb{Z}\times\mathbb{N}^*, r = \frac{p}{q}$

On note $d = \operatorname{PGCD}(p,q)$ .

$d | p \Rightarrow \exists p_0 \in \mathbb{Z}, p = d p_0$ .

De même, $d | q \Rightarrow \exists q_0 \in \mathbb{N}^*, q = d q_0$ .

Montrons que $\operatorname{PGCD}(p_0,q_0)=1$ .

Selon le théorème de Bachet-Bézout, $\exists (a,b)\in\mathbb{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$ .

Cette égalité assure que $\operatorname{PGCD}(p_0,q_0)=1$ .

On a $\frac{p}{q} = \frac{d p_0}{d q_0}$ .

D'où $\frac{p}{q} = \frac{p_0}{q_0}$ .

Le couple $(p 0, q 0)$ convient donc bien.

Unicité

Soit $(p_1,p_2,q_1,q_2)\in{\mathbb{Z}}^2\times{\mathbb{N}^*}^2$ vérifiant :

$r = \frac{p_1}{q_1} = \frac{p_2}{q_2}$
$\operatorname{PGCD}(p_1,q_1) = \operatorname{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 $\operatorname{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 $\operatorname{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)\in\mathbb{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 $b c$ 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 $b a'$ , on a que $a$ divise $a'$ donc $d = 1$ , CQFD.

Références

↑ Euclide, Les Éléments, traduction, commentaires et notes de Bernard Vitrac [détail des éditions], vol. 2, p. 338-339.

Voir aussi

A lire avant

Portail des mathématiques

Catégories :

Divisibilité et factorisation
Lemme de mathématiques

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Lemme d'Euclide de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

Euclide (mathématicien) — Euclide Pour les articles homonymes, voir Euclide (homonymie). Euclide … Wikipédia en Français
Euclide — Pour les articles homonymes, voir Euclide (homonymie). Euclide Euclide (d après une peinture du XVIIIe siècle) … Wikipédia en Français
Lemme (mathématiques) — Le lemme, en mathématiques et en logique mathématique, est un résultat intermédiaire sur lequel on s appuie pour conduire la démonstration d un théorème plus important. Principe En effet, la méthode de démonstration d un théorème est souvent la… … Wikipédia en Français
Lemme d'itération pour les langages algébriques — Le Lemme d itération pour les langages algébriques, aussi connu sous le vocable Lemme de Bar Hillel, Perles et Shamir, donne une condition de répétition nécessaire pour les langages algébriques. Sa version simplifiée pour les langages rationnels… … Wikipédia en Français
Lemme d'Ogden — Le lemme d Ogden est un résultat de théorie des langages analogue au lemme de l étoile. On l utilise principalement pour démontrer que certains langages ne sont pas algébriques. Le lemme d Ogden est une version plus élaborée du lemme d itération… … Wikipédia en Français
Lemme de Bézout — Théorème de Bachet Bézout Cet article parle de l identité de Bézout et du théorème de Bézout en arithmétique. Pour le théorème de Bézout en géométrie algébrique voir Théorème de Bézout. En mathématiques, le théorème de Bachet Bézout ou identité… … Wikipédia en Français
Algorithme d'Euclide (mathématiques élémentaires) — Algorithme d Euclide L algorithme d Euclide est un algorithme permettant de déterminer le plus grand commun diviseur (P.G.C.D.) de deux entiers dont on ne connaît pas la factorisation. Il est déjà décrit dans le livre VII des Éléments d Euclide.… … Wikipédia en Français
Algorithme d'Euclide — L algorithme d Euclide est un algorithme permettant de déterminer le plus grand commun diviseur (P.G.C.D.) de deux entiers dont on ne connaît pas la factorisation. Il est déjà décrit dans le livre VII des Éléments d Euclide. Dans la tradition… … Wikipédia en Français
Anneau euclidien — Euclide (Juste de Gand, vers 1474) En mathématiques et plus précisément en algèbre, dans le cadre de la théorie des anneaux, un anneau euclidien est un type particulier d anneau intègre. Un anneau est dit euclidien s il est possible d y définir… … Wikipédia en Français
Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Lemme d'Euclide

Sommaire

Démonstration