Votre navigateur n'accepte pas le Javascript.La navigation sur ce site risque de ne pas fonctionner correctement.

126. Le lemme d’Euclide

Contexte

Les nombres premiers constituent des éléments très importants dans l’étude des nombres.

Qu’est-ce qu’un nombre premier ? On entend souvent qu’un nombre est premier, si et seulement si, il n’est divisible que par 1 et par lui-même.

Cette assertion est presque correcte, elle mérite d’être précisée. Elle laisse une ambiguïté sur le chiffre $1.$ En fait, le chiffre $1$ n’est pas un nombre premier, le plus petit nombre premier est $2$. Pourquoi ?

Retenez qu’un nombre $p$ est premier, si et seulement si, $p$ est un élément de $\N$, de sorte que $p$ admette exactement deux diviseurs (qui sont $1$ et $p$).

Le nombre $1$ n’admet qu’un seul diviseur et n’est pas premier.

Dans la littérature mathématique, on trouve l’énoncé suivant. Pour tout nombre premier $p$ et pour tout couple $(a,b)$ d’entiers naturels, si $p$ divise le produit $ab$, alors $p$ divise $a$ ou $p$ divise $b$. Autrement dit, un nombre premier qui divise un produit divise nécessairement un des facteurs du produit.

Ce résultat s’appelle le lemme d’Euclide. En dépit des apparences, démontrer ce résultat, sans faire appel au PGCD (plus grand diviseur commun), n’est pas simple. Il existe plusieurs façons d’y parvenir, aussi je vous présente dans cet article une piste qui utilise la propriété fondamentale de $\N$, toute partie non vide de $\N$ admet un plus petit élément.

Démonstration du lemme d’Euclide

Soit $p$ un nombre premier. On considère deux entiers naturels $a$ et $b$ de sorte que $p\mid ab.$

Remarquez que, si l’un des nombres $a$ ou $b$ est nul, comme $p\mid 0$, on a immédiatement $p\mid a$ ou $p\mid b.$

Dans la suite, vous supposerez que $a$ et $b$ sont non nuls.

On considère alors l’ensemble $A=\{n\in\NN, p \mid an\}.$ $A$ est une partie de $\N$ qui contient $b.$ Notons $m$ le plus petit élément de $A.$

Effectuez la division euclidienne de $b$ par $m$. Il existe $(q,r)\in\N^2$ avec $0\leq r \leq m-1$ tel que $b =mq+r.$ En multipliant par $a$, vous obtenez $ab = q am +ar$ d’où $ar = ab-q am.$ Or $p\mid ab$ et $p\mid am$ donc $p\mid ar.$ Comme $r < m$, l’entier naturel $r$ n’appartient pas à $A$. Comme $p\mid ar$ c’est que $r\notin\NN$ et donc $r=0$ et $m\mid b.$

De même effectuez la division euclidienne de $p$ par $m.$ Il existe $(q’,r’)\in\N^2$ avec $0\leq r’\leq m-1$ tel que $p = mq’+r’.$ Vous multipliez par $a$ et obtenez $ap-amq’ = ar’$. Comme $p\mid ap$ et comme $p\mid am$ vous obtenez $p\mid ar’$. Comme $r'<m$, $r’\notin A$ donc $r’=0.$ Cela montre que $m\mid p.$ Comme $p$ est premier, il y a deux possibilités.

Soit $m=1$. Dans ce cas, $p\mid am$ s’écrit $p\mid a.$

Soit $m=p$. Comme $m\mid b$ vous obtenez $p\mid b.$

Le lemme d’Euclide est démontré.

Prolongement

Pour ceux qui aiment la théorie des groupes, ils auront sûrement remarqué un lien avec l’application $x\mapsto ax$, le théorème de Lagrange et la structure de $\Z/p\Z.$

Partagez !

Diffusez cet article auprès de vos connaissances susceptibles d'être concernées en utilisant les boutons de partage ci-dessous.

Aidez-moi sur Facebook !

Vous appréciez cet article et souhaitez témoigner du temps que j'y ai passé pour le mettre en œuvre. C'est rapide à faire pour vous et c'est important pour moi, déposez un j'aime sur ma page Facebook. Je vous en remercie par avance.

Lisez d'autres articles !

Parcourez tous les articles qui ont été rédigés. Vous en trouverez sûrement un qui vous plaira !