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

296. Déterminez sans division si un nombre est premier (2/2)

Soit $n$ un nombre impair supérieur ou égal à $7$ et qui n’est pas un carré.

L’objectif de cet article est de démontrer que la méthode suivie dans le contenu rédigé dans l'article 295 fonctionne bien.

Elle fournit toujours une réponse en un nombre fini d’étapes et permet de conclure que :

  • soit le nombre $n$ est premier :
  • soit il ne l’est pas – on dit qu’il est composé – et il vous permet d’écrire $n$ comme le produit de deux entiers explicites qui sont différents de $1$ et de $n.$

Le point de départ

Vous considérez l’ensemble :

A = \{m\in\N, m^2>n\}.

Comme l’entier $n$ est supérieur ou égal à $7$, l’entier $n-1$ est supérieur ou égal à $6.$

Par produit, vous déduisez :

n(n-1)\geq 42.

Vous développez et isolez le carré de $n$ :

\begin{align*}
n^2-n&\geq 42\\
n^2&\geq n+42\\
n^2&\geq n+1\\
n^2&>n.
\end{align*}

Vous avez obtenu l’appartenance de $n$ à l’ensemble $A$, donc $A$ est non vide.

$A$ étant une partie de $\N$ non vide, vous déduisez que $A$ admet un plus petit élément.

Dans la suite, vous noterez :

\boxed{k=\mathrm{Min}\  \{m\in\N, m^2>n\}.}

Vous aurez aussi besoin du nombre $K=\frac{n+1}{2}.$ Comme $n$ est impair supérieur ou égal à $7$, $K$ est un entier supérieur ou égal à $4$ :

\boxed{K = \frac{n+1}{2}.}

Cas de la factorisation avec $1$ et $n$ et ses conséquences

La factorisation de $n$ est ne semble n’avoir que peu d’intérêt :

n = n\times 1.

Ceci n’est qu’un leurre.

Vous allez maintenant utiliser les identités remarquables bien connues des Babyloniens, qui ont formé une ancienne civilisation de la Mésopotamie. Ils ont contribué au développement des mathématiques et avaient des connaissances sur les identités remarquables.

Comme :

\begin{align*}
(n+1)^2&=n^2+2n+1\\
(n-1)^2&=n^2-2n+1\\
\end{align*}

il vient par soustraction :

(n+1)^2-(n-1)^2 = 4n.

Or, $4$ est lui-même un carré, donc :

\begin{align*}
n &= \frac{(n+1)^2}{4}-\frac{(n-1)^2}{4} \\
&=\left(\frac{n+1}{2}\right)^2-\left(\frac{n-1}{2}\right)^2\\
&=K^2-\left(\frac{n-1}{2}\right)^2.
\end{align*}

De ce résultat, vous déduisez que :

K^2 - n

est un carré et que ce carré vaut $\left(\frac{n-1}{2}\right)^2.$ Comme $n\geq 7$ il vient $n-1\geq 6$ donc $\frac{n-1}{2}\geq 3$ et par suite $\left(\frac{n-1}{2}\right)^2 \geq 9.$

Donc $K^2 – n\geq 9$ et $K^2 > n.$

Par suite, $K\in A$ et par définition du minimum de $A$, il vient :

\boxed{k\leq K.}

Etude du cas d’égalité

Supposez un instant que :

k = K.

Alors $K=\frac{n+1}{2}$ est le minimum de $A.$

Or, comme $n$ est impair supérieur ou égal à $7$, $\frac{n-1}{2}$ est un entier supérieur ou égal à $3$. Comme il est strictement inférieur à $k$, vous déduisez que $\frac{n-1}{2}\notin A.$ Donc :

\begin{align*}
\left(\frac{n-1}{2}\right)^2&\leq n\\
\frac{(n-1)^2}{4}&\leq n\\
(n-1)^2&\leq 4n\\
n^2-2n+1&\leq 4n\\
n^2-6n&\leq -1\\
n^2-6n+9&\leq 8\\
(n-3)^2 &< 9\\
n-3&<3\\
n&<6.
\end{align*}

Ceci est absurde puisque $n\geq 7.$ Il est donc impossible d’avoir $k=K$ et par suite :

\boxed{k < K.}

Le test par la méthode de Fermat

De ce qui précède, l’ensemble $B$ défini par :

B = \{\ell^2-n, \ell\in\llbracket k, K-1\rrbracket\}.

est non vide.

Deux cas se produisent.

Cas 1 : l’ensemble $B$ contient un carré

Sous cette hypothèse, il existe un entier $\ell \in \llbracket k, K-1\rrbracket$ et un entier naturel $m$ tels que :

\ell^2-n  = m^2.

Alors :

\begin{align*}
n &= \ell^2-m^2\\
&=(\ell+m)(\ell-m).
\end{align*}

D’une part, $\ell$ et $m$ sont positifs donc la somme $\ell +m$ est positive.

Comme $n\in\N^{*}$ est un multiple de $\ell+m$, la somme $\ell + m$ est strictement positive donc $\ell+m \geq 1.$

Il en résulte par la règle des signes que la différence $\ell-m$ est strictement positive aussi.

Supposez un instant que $\ell -m = 1.$ Alors : $m = \ell-1.$ Du coup :

\begin{align*}
n &= \ell^2-(\ell-1)^2\\
&=\ell^2-(\ell^2-2\ell+1)\\
&=2\ell-1.
\end{align*}

Ainsi :

\begin{align*}
\ell &= \frac{n+1}{2}\\
&=K.
\end{align*}

Cela est absurde, puisque $\ell\leq K-1.$

Il en résulte que $\ell-m$ est un entier supérieur ou égal à $2.$

Le produit :

\begin{align*}
n =(\ell+m)(\ell-m)
\end{align*}

montre que $\ell -m \leq n.$

En effet si tel n’était pas le cas, vous auriez :

\ell-m > n\\
\ell+m \geq 1

et par produit l’inégalité serait stricte :

(\ell+m)(\ell-m)>n

ce qui serait absurde.

Supposez enfin que $\ell-m = n.$

Alors nécessairement $\ell+m = 1.$

Or $\ell^2\geq k^2>n\geq 7$ donc $\ell^2 > 4$ donc $\ell > 2.$ La positivité de $m$ fournit $\ell + m >2$ ce qui contredit $\ell+m=1.$

Il a été montre que $\ell-m \in\llbracket 2, n-1\rrbracket.$ On dit que $\ell-m$ est un diviseur propre de $n.$ En effet, $n$ admet un troisième diviseur qui est différent de $1$ et de $n$.

Par suite, $n$ n’est pas premier et vous avez une factorisation par ce diviseur propre :

\begin{align*}
n =(\ell+m)(\ell-m).
\end{align*}

Cas 2 : l’ensemble $B$ ne contient pas de carré

Vous supposez, en raisonnant par l’absurde, que $n$ n’est pas un nombre premier.

Il existe un entier $d$ compris entre $2$ et $n-1$ tel que $n$ soit un multiple de $d.$

Du coup il existe aussi un entier naturel $d’$ tel que :

n = dd'.

Supposez $d’\in\{1, n\}.$ Alors $d\in\{1,n\}$ ce qui est absurde, donc $d’\in \llbracket 2, n-1\rrbracket.$

Si $d$ était pair, alors il existerait un entier naturel $d_0$ tel que $d = 2d_0$ et par suite :

n=2d_0d'.

Comme $d_0d’\in\N$ vous déduisez que $n$ est pair, ce qui est absurde.

De même, si $d’$ était pair, alors $n$ serait pair, ce qui est absurde.

Donc $d$ et $d’$ sont deux entiers impairs appartenant à l’ensemble $\llbracket 2, n-1\rrbracket.$

Le reste de la division euclidienne de $d$ par $2$ ne pouvant être nul, c’est donc qu’il est égal à $1.$ Le résultat est aussi identique pour $d’.$

Ainsi, il existe deux entiers naturels $u$ et $u’$ tels que :

\begin{align*}
d&=2u+1\\
d'&=2u'+1.
\end{align*}

Comme $d\geq 2$, vous déduisez $2u+1\geq 2$ donc $2u\geq 1$ et donc $u\neq 0$ donc $u\geq 1.$

De même, vous avez aussi $u’\geq 1.$

Utilisant à nouveau $n = dd’$ il vient :

\begin{align*}
n&=(2u+1)(2u'+1)\\
&=4uu'+2u+2u'+1\\
&=u^2+u'^2+2uu'+2u+2u'+1-(u^2+u'^2)+2uu'\\
&=(u+u'+1)^2-(u^2+u'^2-2uu')\\
&=(u+u'+1)^2-(u-u')^2.
\end{align*}

Posez $\ell = u+u’+1.$ Vous avez $\ell \in\N$ et $\ell \geq 3.$

Si vous aviez $u=u’$ alors $n$ serait le carré de $\ell$ ce qui est absurde.

Comme $u\neq u’$ vous déduisez $(u-u’)^2\geq 1$ et donc $(u+u’+1)^2-n \geq 1$ donc $(u+u’+1)^2>n$ et par suite $u+u’+1\in A.$ Cela prouve que :

\begin{align*}
k&\leq u+u'+1\\
k&\leq \ell.
\end{align*}

D’autre part, de l’égalité $n = 4uu’+2u+2u’+1$ et en minorant le produit $uu’$ par $1$, vous déduisez :

\begin{align*}
n&\geq 4uu'+2u+2u'+1 
\\
&\geq 4+2u+2u'+1
\\
&\geq 5+2u+2u'.
\end{align*}

Or $n=2K-1$ donc :

\begin{align*}
2K-1&\geq 5+2u+2u'\\
2K&\geq 6+2u+2u'\\
K&\geq 3+u+u'\\
K-1&\geq 2+u+u'\\
K-1&\geq 1+\ell\\
K-1&\geq \ell.
\end{align*}

Vous avez $\ell\in \llbracket k, K-1\rrbracket$ et d’autre part :

\ell^2-n = (u-u')^2.

Donc $B$ contient un carré, ce qui est absurde.

Ainsi, $n$ est premier.

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!