354. Factorisez un entier naturel avec la méthode de Fermat

Soit $n$ un entier naturel. Il convient tout d’abord de remarquer que la racine carrée de $n$ est inférieure ou égale à $\frac{n+1}{2}.$ En effet :

\begin{align*} (n-1)^2 &\geq 0\\ n^2-2n+1&\geq 0\\ n^2+2n+1&\geq 4n\\ (n+1)^2 &\geq 4n\\ n+1 &\geq 2\sqrt{n}\\ \frac{n+1}{2}&\geq \sqrt{n}. \end{align*}

Ainsi :

\boxed{\forall n\in\N, \sqrt{n}\leq \frac{n+1}{2}.}

Par définition, un entier naturel supérieur ou égal à $2$ qui n’est pas premier sera qualifié de composé.

Le résultat à démontrer

Il s’agit d’établir que, pour tout entier naturel $n$ impair supérieur ou égal à $3\comma$ vous avez l’équivalence :

\boxed{n\text{ n'est pas premier}\Longleftrightarrow \exists k\in \N \cap \left[\sqrt{n}, \frac{n+1}{2}\right[, k^2-n\text{ est le carré d'un entier.} }

Note. Ce résultat a déjà été établi dans un autre article. Une démonstration plus succincte est présentée dans ce contenu.

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

Démontrez le sens $\implies$

Soit $n$ un entier naturel impair composé supérieur ou égal à $3.$ Il existe deux entiers naturels $a$ et $b$ compris entre $2$ et $n-1$ tels que $n=ab.$

Si $a$ est pair, alors $2\mid a.$ Comme $a\mid n$ vous déduisez par transitivité que $2\mid n$ donc $n$ est pair ce qui est absurde. De même si $b$ est pair, il vient $2\mid b$ puis $b\mid n$ donc $2\mid n$ du coup $n$ est pair, contradiction. Donc $a$ et $b$ sont impairs.

Le reste de la division euclidienne de $a$ par $2$ est donc égal à $1.$ De même, le reste de la division euclidienne de $b$ par $2$ est égal à $1.$ Il existe deux entiers naturels $a’$ et $b’$ tels que $a = 2a’+1$ et $b = 2b’+1$ d’où $a+b = 2(a’+b’+1)$ ce qui prouve que $a+b$ est pair. Ainsi $\frac{a+b}{2}$ est un entier naturel. En utilisant le même raisonnement, $a – b = 2(a’-b’)$ donc $a-b$ est un entier relatif pair et $\frac{a-b}{2}$ est un entier relatif.

Vous posez maintenant $k = \frac{a+b}{2}.$ Il a été vu que $k\in\N.$

Comme $a\gt1$ et comme $b\gt1\comma$ le produit $(a-1)(b-1)$ est strictement positif. En développant, vous obtenez :

\begin{align*} &(a-1)(b-1)\gt 0\\ &ab-a-b+1 \gt 0\\ &ab+1 \gt a+b\\ &n+1 \gt a+b\\ &\frac{n+1}{2} \gt k. \end{align*}

Maintenant, $k^2-n$ est le carré d’un entier relatif. En effet :

\begin{align*} k^2-n &= \left(\frac{a+b}{2}\right)^2-ab\\ &= \frac{a^2+2ab+b^2}{4}-\frac{4ab}{4}\\ &= \frac{a^2-2ab+b^2}{4}\\ &=\left(\frac{a-b}{2}\right)^2. \end{align*}

Comme un carré est positif, il vient $k^2-n \geq 0$ puis $k^2\geq n$ et enfin $k\geq \sqrt{n}$ ce qui donne le résultat.

Démontrez le sens $\impliedby$

Soit $n$ un entier naturel impair supérieur ou égal à $3.$ Vous supposez qu’il existe un entier naturel $k$ tel que :

\left\{\begin{align*} &\sqrt{n}\leq k \lt \frac{n+1}{2}\\ &k^2-n\text{ est le carré d'un entier}. \end{align*} \right.

Comme $n\geq 3$ il vient $\sqrt{n}\geq 1$ donc $k\geq 1.$

Il existe un entier relatif $u$ tel que $k^2-n=u^2 = (\vert u \vert)^2.$ En posant $\ell = \vert u \vert$ il vient :

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

Comme $2k \lt n+1$ vous déduisez ce qui suit :

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

Comme $\ell$ et $k-1$ sont positifs, vous déduisez $\ell \lt k-1$ donc $1\lt k-\ell.$

Ainsi, l’entier $k-\ell$ est supérieur ou égal à $2$ et divise $n.$

Si $n$ était premier, alors $k-\ell = n$ puisque $k-\ell$ est un diviseur positif de $n$ différent de $1.$ L’égalité $(k+\ell)(k-\ell) = n$ s’écrirait $n(k+\ell) = n$ d’où $k+\ell =1.$ Comme $k\geq 1$ et $\ell\geq 0\comma$ cela impose $k=1$ et $\ell = 0\comma$ donc $k-\ell = 1\comma$ ce qui contredit le fait que $k-\ell$ est supérieur ou égal à $2.$

Donc $n$ est composé.

Application : factorisez $2279$

Cherchez d’abord le plus petit carré parfait qui soit supérieur ou égal à $2279.$

Comme $40^2 = 1600$ et comme $50^2=2500$ vous prenez $45^2=2025.$

Ce nombre étant strictement inférieur à $2279$ vous calculez le carré suivant.

\begin{align*} 46^2&= 2025+45+46\\ &= 2025+91\\ &= 2116. \end{align*}

Vous poursuivez :

\begin{align*} 47^2&= 2116+46+47\\ &= 2116+93\\ &= 2209. \end{align*}

Vous continuez :

\begin{align*} 48^2&= 2209+47+48\\ &= 2209+95\\ &= 2304. \end{align*}

Comme $48^2 \geq 2279$ vous évaluez la différence suivante :

\begin{align*} 48^2- 2279 &= 2304-2279\\ &=104-79\\ &=99-74\\ &=25\\ &=5^2. \end{align*}

Ainsi $2279$ va être factorisé comme suit :

\begin{align*} 2279 &= 48^2-5^2\\ &=(48+5)(48-5)\\ &=53\times 43. \end{align*}

Application : factorisez $10541$

Vous avez $100^2 =10000$ ce qui vous amène à calculer le carré parfait suivant.

\begin{align*} 101^2&= 10000+100+101\\ &= 10000+201\\ &= 10201. \end{align*}

Comme $10201\lt 10541$ vous poursuivez.

\begin{align*} 102^2&= 10201+101+102\\ &= 10201+203\\ &= 10404. \end{align*}

Comme $10404\lt 10541$ vous poursuivez.

\begin{align*} 103^2&= 10404+102+103\\ &= 10404+205\\ &= 10609. \end{align*}

Étant donné que $10609\geq 10541$ vous calculez la différence suivante :

\begin{align*} 103^2-10541 &= 10609-10541\\ &=109-41\\ &=99-31\\ &=68. \end{align*}

Comme $68$ n’est pas un carré parfait, vous calculez la prochaine différence :

\begin{align*} 104^2-10541 &= (103^2-10541) + (103+104)\\ &=68+207\\ &=275. \end{align*}

Comme $275$ n’est pas un carré parfait, vous calculez la prochaine différence :

\begin{align*} 105^2-10541 &= (104^2-10541) + (104+105)\\ &=275+209\\ &=484\\ &=22^2. \end{align*}

Ainsi, $10541$ est factorisable et :

\begin{align*} 10541 &= 105^2-22^2\\ &=(105+22)(105-22)\\ &=127\times 83. \end{align*}

Prolongement

Un autre exemple est détaillé dans un autre article.

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