École AVOSZ

Connectez-vous

343. Le lemme d’Euclide démontré par deux arguments de minimalité

Yannis TRIANTAPHYLIDES

Dans ce contenu, vous notez $\mathscr{P}$ l’ensemble des nombres premiers.

Un nombre $p$ sera qualifié de premier, si et seulement si, il est entier et supérieur ou égal à $2$ et si, quels que soient les entiers naturels $a$ et $b$ non nuls :

\boxed{p = ab \implies \left(\left\{\begin{align*}a&=1\\ b&=p\end{align*}\right. \quad \text{ ou }\quad \left\{\begin{align*}a&=p\\ b&=1.\end{align*}\right.\right)}

Un nombre entier supérieur ou égal à $2$ qui n’est pas premier sera qualifié de nombre composé.

Caractérisez un nombre entier composé

Soit $n$ un nombre entier supérieur ou égal à $2.$ Supposez que $n$ ne soit pas premier. Alors il existe deux entiers naturels $a$ et $b$ non nuls tels que $n=ab$ et ils vérifient ce qui suit :

(*) :\left\{\begin{align*} a&\neq 1 \text{ ou } b\neq n\\ a&\neq n \text{ ou } b\neq 1. \end{align*}\right.

Si $a=1\comma$ alors $b\neq n$ d’après la première ligne de $(*).$ Or, la condition $n=ab$ devient $n=b$ ce qui amène à une contradiction. Donc $a\geq 2.$

Si $a=n\comma$ alors $b\neq 1$ d’après la deuxième ligne de $(*).$ Or, la condition $n=ab$ devient $n=nb$ et comme $n\neq 0$ vous déduisez $b=1$ ce qui amène à une contradiction.

Si $a\gt n\comma$ alors en multipliant par $b$ qui est strictement positif, il vient $ab\gt nb$ et la condition $n=ab$ fournit $n\gt nb$ et en divisant par $n\gt0$ il vient $1\gt b$ ce qui contredit le fait que $b$ est un entier naturel non nul.

Vous déduisez de cette analyse que $2\leq a \leq n-1.$

Le raisonnement est strictement identique pour $b.$

Il est ainsi établi que, pour tout entier naturel $n$ supérieur ou égal à $2\comma$ si $n$ n’est pas premier, alors il existe deux entiers $a$ et $b$ tels que :

\left\{\begin{align*} &n=ab\\ &2\leq a \leq n-1\\ &2\leq b \leq n-1. \end{align*}\right.

Réciproquement, soit $n$ un nombre entier supérieur ou égal à $2$ tel qu’il existe deux entiers $a$ et $b$ vérifiant les conditions suivantes :

(**): \left\{\begin{align*} &n=ab\\ &2\leq a \leq n-1\\ &2\leq b \leq n-1. \end{align*}\right.

Les entiers $a$ et $b$ sont des entiers naturels non nuls. Si $n$ était premier, alors soit $a$ serait égal à $1\comma$ ce qui contredit la deuxième ligne de $(**)$ soit $a$ serait égal à $n\comma$ ce qui contredit encore la deuxième ligne de $(**).$

La caractérisation est ainsi établie.

Pour tout entier naturel $n$ supérieur ou égal à $2\comma$ $n$ n’est pas premier, si et seulement si, il existe deux entiers $a$ et $b$ tels que :

\boxed{\left\{\begin{align*} &n=ab\\ &2\leq a \leq n-1\\ &2\leq b \leq n-1. \end{align*}\right.}

Le lemme d’Euclide à partir du raisonnement par l’absurde

Vous cherchez à démontrer le lemme d’Euclide qui affirme que, quel que soit le nombre premier $p$ et quels que soient les entiers naturels non nuls $a$ et $b\comma$ si $p$ divise le produit $ab\comma$ alors $p$ divise $a$ ou $p$ divise $b.$

Les deux arguments de minimalité

Vous supposez que le lemme d’Euclide n’est pas vérifié.

Vous en concluez qu’il existe un nombre premier $p_0$ ainsi que deux entiers naturels non nuls $a_0$ et $b_0$ tels que :

\left\{\begin{align*} &p_0 \mid a_0b_0\\ &p_0 \nmid a_0\\ &p_0 \nmid b_0. \end{align*} \right.

Vous introduisez alors l’ensemble suivant afin d’utiliser un premier argument de minimalité :

\boxed{A = \{u\in\mathscr{P}, \exists(a,b)\in(\NN)^2, u\mid ab \text{ et }u\nmid a \text{ et }u\nmid b\}.}

Comme $p_0\in A\comma$ l’ensemble $A$ est non vide.

Les inclusions $A\subset \mathscr{P} \subset \N$ montrent que $A$ est une partie non vide de $\N.$ Elle admet donc un plus petit élément que vous notez $p.$

Par définition de $p$ vous avez $p\in A.$ De plus, $p$ est un nombre premier et il existe deux entiers naturels non nuls $a$ et $b$ tels que :

\left\{\begin{align*} &p \mid ab\\ &p \nmid a\\ &p \nmid b. \end{align*} \right.

Vous effectuez la division euclidienne de $a$ par $p.$ Il existe un quotient $q_a\in\N$ et un reste $r_a\in\N$ avec $0\leq r_a\leq p-1$ tels que $a = q_a p + r_a.$

Notez que si $r_a = 0$ alors $a = q_a p$ donc $p\mid a$ ce qui est absurde. Donc :

1\leq r_a\leq p-1.

De même, vous effectuez la division euclidienne de $b$ par $p.$ Il existe un quotient $q_b\in\N$ et un reste $r_b\in\N$ avec $0\leq r_b\leq p-1$ tels que $b = q_b p + r_b.$

Notez que si $r_b = 0$ alors $b = q_b p$ donc $p\mid b$ ce qui est absurde. Donc :

1\leq r_b\leq p-1.

Vous calculez maintenant le produit $ab$ ce qui fournit :

\begin{align*} ab &= ( q_a p + r_a)( q_b p + r_b)\\ &=( q_a p + r_a) q_b p + ( q_a p + r_a) r_b\\ &=( q_a q_b p + r_a q_b) p + q_a r_b p + r_a r_b\\ &=( q_a q_b p + r_a q_b+ q_a r_b) p + r_a r_b. \end{align*}

Ainsi :

r_a r_b = ab -( q_a q_b p + r_a q_b+ q_a r_b) p.

Or, $p$ divise $ab.$

Comme $p$ divise le produit $( q_a q_b p + r_a q_b+ q_a r_b) p$ vous concluez par différence que :

p\mid r_ar_b.

Vous posez $r = r_a+r_b$ et définissez l’ensemble $B$ suivant pour préparer le second argument de minimalité :

\boxed{B=\{u\in\N, \exists(h,k)\in \llbracket 1, p-1\rrbracket ^2, u=h+k \text{ et } p\mid hk\}.}

D’après ce qui précède, $r\in B.$

L’ensemble $B$ est une partie non vide de $\N.$ Elle admet donc un plus petit élément que vous notez $s.$

Aboutissez à une contradiction

Par définition de l’entier $s\comma$ il existe deux entiers $h$ et $k\comma$ compris entre $1$ et $p-1\comma$ tels que $s = h+k$ et $p\mid hk.$

Comme les nombres $p$ puis $h$ et $k$ sont des entiers naturels non nuls, il existe un entier naturel $q$ non nul tel que :

hk = pq.

Si $q$ est égal à $1\comma$ alors $hk = pq$ s’écrit $hk = p.$ Comme $h$ et $k$ sont des entiers naturels non nuls et que $p$ est premier, cela entraîne :

\left\{\begin{align*}h&=1\\ k&=p\end{align*}\right. \text{ ou } \left\{\begin{align*}h&=p\\ k&=1.\end{align*}\right.

Dans le premier cas, $k = p$ et c’est absurde puisque $k \leq p-1.$ Dans le second cas, $h = p$ mais c’est encore absurde puisque $h \leq p-1.$

Vous en déduisez que $q\geq 2.$

Comme $1\leq h \lt p$ et comme $1\leq k \lt p$ par produit il vient $1\leq hk \lt p^2.$ Comme $hk = pq$ il vient $pq \lt p^2.$ En divisant par $p$ qui est strictement positif vous déduisez $q\lt p.$

L’entier $q$ vérifie l’encadrement suivant : $2\leq q \leq p-1.$

Or, tout entier naturel supérieur ou égal à $2$ est divisible par un nombre premier.

Soit $p’\in\mathscr{P}$ tel que $p’ \mid q.$ Comme $q\mid pq$ et comme $hk = pq$ il vient $q\mid hk.$ Finalement, vous avez $p’\mid q$ et $q \mid hk$ donc $p’\mid hk.$

Donc $p’$ est un nombre premier divisant le produit $hk$ avec $h$ et $k$ entiers naturels non nuls. Comme $p’\leq q \leq p-1$ vous avez $p’\lt p.$ Or $p$ est le plus petit élément de $A$ du coup $p’\notin A.$ Il en résulte que, soit $p’ \mid h$ soit $p’\mid k.$

Supposez que $p’\mid h.$ L’entier $h$ étant non nul, il existe un entier naturel non nul $h’$ tel que $h = p’h’.$
Comme $p’\mid q$ et que $q$ est non nul, il existe un entier naturel non nul $q’$ tel que $q = p’q’.$

L’égalité $hk = pq$ s’écrit $p’h’k = pp’q’.$ Comme $p’$ est non nul, il vient $h’k = pq’$ du coup $p\mid h’k.$

Vous posez maintenant $s’ = h’+k.$ L’égalité $h=p’h’$ avec $p’\geq 2$ entraîne $h’\lt h.$ Or $h\leq p-1$ donc $1\leq h’\leq p-1.$
Comme vous avez déjà $k\in\llbracket 1, p-1\rrbracket$ vous déduisez que $s’\in B.$

Le second argument de minimalité est utilisé ici. L’entier $s$ est le minimum de $B$ donc $s\leq s’$ si bien que $h+k\leq h’+k$ d’où $h\leq h’.$ Cela est contradictoire avec $h’\lt h.$

Il en résulte $p’\mid k.$ L’entier $k$ étant non nul, il existe un entier naturel non nul $k’$ tel que $k = p’k’.$
Comme $p’\mid q$ et que $q$ est non nul, il existe un entier naturel non nul $q’$ tel que $q = p’q’.$

L’égalité $hk = pq$ s’écrit $hp’k’ = pp’q’.$ Comme $p’$ est non nul, il vient $hk’ = pq’$ du coup $p\mid hk’.$

Vous posez maintenant $s » = h+k’.$ L’égalité $k=p’k’$ avec $p’\geq 2$ entraîne $k’\lt k.$ Or $k\leq p-1$ donc $1\leq k’\leq p-1.$
Comme vous avez déjà $h\in\llbracket 1, p-1\rrbracket$ vous déduisez que $s »\in B.$

Le second argument de minimalité est encore utilisé ici. L’entier $s$ est le minimum de $B$ donc $s\leq s »$ si bien que $h+k\leq h+k’$ d’où $k\leq k’.$ Cela est contradictoire avec $k’\lt k.$

Les deux cas possibles aboutissant à une contradiction, l’hypothèse de départ est fausse, ce qui démontre le lemme d’Euclide.