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 !