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

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

Dans cet article, 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 $p=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$, 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$, 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>n$, alors en multipliant par $b$ qui est strictement positif, il vient $ab>nb$ et la condition $n=ab$ fournit $n>nb$ et en divisant par $n>0$ il vient $1>b$ ce qui contredit le fait que $b$ et 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 nombre naturel $n$ supérieur ou égal à $2$, 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.

Si $n$ était premier, alors soit $a$ serait égal à $1$, ce qui contredit la deuxième ligne de $(**)$ soit $a$ serait égal à $n$, ce qui contredit encore la deuxième ligne de $(**).$

La caractérisation est ainsi établie.

Pour tout nombre naturel $n$ supérieur ou égal à $2$, $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 stipule que quel que soit le nombre premier $p$ et quels que soient les entiers naturels non nuls $a$ et $b$, si $p$ divise le produit $ab$, 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 $p_0$ premier et 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$, 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$, il existe deux entiers $h$ et $k$, compris entre $1$ et $p-1$ 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$, 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$ 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 < p$ et comme $1\leq k < p$ par produit il vient $1\leq hk < p^2.$ Comme $hk = pq$ il vient $pq < p^2.$ En divisant par $p$ qui est strictement positif vous déduisez $q<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$ vient $q\mid hk.$ Finalement, vous avez $p’\mid q \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'<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.$ $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'<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. $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'<h.$

Il en résulte $p’\mid k.$ $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'<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. $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'<k.$

L’hypothèse de départ est ainsi fausse, ce qui prouve que le lemme d’Euclide est démontré.

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 !