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 ce contenu est de démontrer que la méthode de factorisation de Fermat, suivie dans un autre article, fonctionne bien.

Pour en savoir davantage, allez lire le contenu rédigé dans l'article 295.

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, il est alors dit composé, et la méthode 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\gt n\}.

Comme l’entier $n$ est supérieur ou égal à $7\comma$ 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\comma$ ce qui donne :

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

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

L’ensemble $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=\min \{m\in\N, m^2\gt n\}.}

Vous aurez aussi besoin du nombre $K=\frac{n+1}{2}.$ Comme $n$ est impair et supérieur ou égal à $7\comma$ le nombre $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 suivante de $n$ 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 \gt n.$

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

\boxed{k\leq K.}

Étude 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 et supérieur ou égal à $7\comma$ le nombre $\frac{n-1}{2}$ est un entier supérieur ou égal à $3.$ Comme il est strictement inférieur à $K = k\comma$ 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 &\lt 9\\ n-3&\lt3\\ n&\lt6. \end{align*}

Le passage de $(n-3)^2\lt9$ à $n-3\lt3$ est valable car $n-3$ est positif. Ceci est absurde puisque $n\geq 7.$ Il est donc impossible d’avoir $k=K$ et par suite :

\boxed{k \lt K.}

Le test par la méthode de Fermat

De ce qui précède, vous avez $k\leq K-1.$ L’ensemble $B$ défini par :

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

est donc non vide. La méthode consiste à calculer successivement ses éléments, pour $\ell$ allant de $k$ à $K-1\comma$ et à tester à chaque fois s’il s’agit d’un carré parfait.

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, les entiers $\ell$ et $m$ sont positifs donc la somme $\ell +m$ est positive.

Comme $n\in\N^{*}$ est un multiple de $\ell+m\comma$ 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 :

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

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

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

\left\{\begin{align*} \ell-m &\gt n\\ \ell+m &\geq 1 \end{align*}\right.

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

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

ce qui serait absurde.

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

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

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

Il a été montré que $\ell-m \in\llbracket 2, n-1\rrbracket.$ L’entier $\ell-m$ est alors appelé un diviseur propre de $n\comma$ c’est-à-dire un diviseur de $n$ 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.

Comme $n\geq 7\comma$ 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'.

Si vous aviez $d’\in\{1, n\}\comma$ vous auriez $d\in\{n,1\}$ 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 puisque $n$ est impair.

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, il est égal à $1.$ Il en est de même 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\comma$ 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, puisque $n$ n’est pas un carré.

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\gt 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\comma$ vous déduisez :

\begin{align*} n&= 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 donc $\ell\in \llbracket k, K-1\rrbracket$ et d’autre part :

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

Donc $B$ contient un carré, ce qui contredit l’hypothèse du cas 2.

Ainsi, $n$ est premier.

Concluez

Soit $n$ un entier impair supérieur ou égal à $7$ qui n’est pas un carré. Vous calculez les nombres $\ell^2-n$ pour $\ell$ allant de $k$ à $K-1.$ Si l’un d’eux est un carré $m^2\comma$ alors $n = (\ell+m)(\ell-m)$ est une factorisation de $n$ par deux entiers différents de $1$ et de $n.$ Sinon, le nombre $n$ est premier. Dans tous les cas, la méthode s’arrête après au plus $K-k$ étapes.