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

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 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 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$, 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 le contenu rédigé dans l'article 296. Une démonstration plus succincte est présentée dans cet article.

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 quotient de la division euclidienne de $a$ par $2$ est donc égal à $1.$ De même, le quotient 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+a’+1)$ ce qui prouve que $a+b$ est pair. Ainsi $\frac{a+b}{2}$ est un entier naturel. 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>1$ et comme $b>1$, le produit $(a-1)(b-1)$ est strictement positif. En développant, vous obtenez :

\begin{align*}
&(a-1)(b-1)> 0\\
&ab-a-b+1 > 0\\
&ab+1 > a+b\\
&n+1 > a+b\\
&\frac{n+1}{2} > 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 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 < \frac{n+1}{2}\\
&k^2-n\text{ est le carré d'un entier}.
\end{align*}
\right.

Comme $n\geq 1$ 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 < n+1$ vous déduisez ce qui suit :

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

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

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

Si $n$ était premier, alors $k-\ell = n.$ L’égalité $(k+\ell)(k-\ell) = n$ s’écrit $n(k+\ell) = n$ d’où $k+\ell =1.$ Comme $k$ est supérieur ou égal à $1$ il vient $\ell = 0$ donc $n = k^2$ donc $k$ divise $n.$ Si $k=1$ alors $n =1$ ce qui contredit le fait que $n$ est premier. Si $k=n$ alors $n = n^2$ d’où $n=1$ après simplification par $n$ ce qui est absurde.

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< 10541$ vous poursuivez.

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

Comme $10404< 10541$ vous poursuivez.

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

Etant 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

Vous êtes invité à lire le contenu rédigé dans l'article 295 qui détaille un autre exemple.

353. Tout sous-groupe fini des éléments inversibles d’un corps commutatif est cyclique

Soit $K$ un corps commutatif et soit $G$ une partie de $K\setminus\{0\}$ qui soit un groupe fini de cardinal $n$ lors qu’il est muni de la multiplication dans $K$ comme opération.

Note. En tant que groupe, l’ensemble $G$ n’est pas vide donc l’entier $n$ est supérieur ou égal à $1.$ Il existe un élément $k\in G.$ Comme $G$ est inclus dans $K\setminus\{0\}$ il vient $k\neq 0$ donc $k^{-1}$ est bien défini. En tant que groupe, $k^{-1}$ appartient à $G$ et par produit, $1 = k \times k^{-1}$ appartient à $G.$ Ainsi, le neutre $1$ de la multiplication du corps $K$ appartient aussi à $G$ c’est l’élément neutre du groupe $G.$

Prérequis : ordre d’un élément du groupe $G$

Soit $x$ un élément du groupe $G.$

Existence de l’ordre

Vous considérez l’application $f$ suivante, définie sur $\N$ par :

\forall u\in\N, f(u) = x^u.

Comme l’ensemble $f(\N) = \{f(u), u\in\N\}$ est inclus dans $G$ qui est un groupe fini, l’application $f$ ne peut pas être injective : si tel était le cas, $f(\N)$ serait infini parce que $\N$ l’est, ce qui contredit l’inclusion $f(\N)\subset G;$ Donc il existe deux entiers naturels $p$ et $q$, avec $p\neq q$ tels que $x^p =x^q.$ Si $p>q$, cela s’écrit $x^{p-q}x^q = x^q$ d’où $x^{p-q}= 1$ après simplification par $x^q.$ Sinon, $p<q$ et alors $x^p = x^{q-p}x^p$ d’où $x^{q-p}=1.$ Cela montre qu’il existe un entier naturel non nul $r$ tel que $x^r = 1.$

Le plus petit entier naturel $r$ non nul tel que $x^r=1$ est l’ordre de $x.$ Notez-le $d.$ Par définition de $d$, vous avez :

\boxed{\left\{\begin{align*}
&x^d = 1\\
&\forall i\in\llbracket 0, d-1\rrbracket, x^i \neq 1.
\end{align*}\right.}

Critère de divisibilité

Soit $p$ un entier relatif tel que $x^p = 1.$

En utilisant la division euclidienne de $p$ par $d$, il existe deux entiers $a$ et $b$ avec $0\leq b \leq d-1$ tels que $ p = ad+b.$

Alors :

\begin{align*}
1 &= x^p\\
&= x^{ad+b}\\
&= (x^d)^ax^b\\
&= 1^a x^b\\
&= x^b.
\end{align*} 

Si $b$ n’était pas nul, il serait un entier naturel non nul, strictement inférieur à l’ordre $d$, tel que $x^b=1$ ce qui est impossible par définition de cet ordre.

Donc $b=0$ et $d\mid p.$

Réciproquement, si $p$ est un entier tel que $d\mid p$ alors $p/d$ est un entier ce qui fournit :

\begin{align*}
x^p &= (x^d)^{p/d}\\
&= 1^{p/d}\\
&=1.
\end{align*} 

Il a été démontré ce qui suit, $x$ ayant pour ordre $d$ vous avez :

\boxed{\forall p\in\Z, x^p=1 \Longleftrightarrow d\mid p.}

L’ordre divise le cardinal du groupe

Vous allez maintenant démontrer que l’entier $d$ est un diviseur de $n.$

Soit $H$ la partie finie de $G$ définie par :

H = \{x^i, i\in\llbracket 0, d-1\rrbracket\}.

Par définition, $H$ possède au maximum $d$ éléments.

Soient maintenant $i$ et $j$ deux entiers appartenant à l’intervalle $\llbracket 0, d-1\rrbracket$ tels que $x^i = x^j.$ Si $i>j$ on peut écrire $x^{i-j} = 1$ du coup $d\mid i-j.$ Du coup $d\leq i-j.$ Or, comme $i$ et $j$ sont deux éléments de $\llbracket 0, d-1\rrbracket$ il en est de même de $i-j$ et par suite $i-j\leq d-1$ ce qui fournit $d\leq d-1$ qui est une contradiction. De même, si $i<j$ on écrit $x^{j-i}=1$ ce qui conduit à $d\mid j-i$ avec $d\leq j-i \leq d-1.$ Du coup, $i=j.$ Cela prouve que $H$ possède au moins $d$ éléments.

Les éléments de $H$ sont au nombre exact de $d.$

L’ensemble $H$ contient $x^0=1$ il est non vide. Si $u$ et $v$ sont deux éléments de $H$, il existe $i$ et $j$ entiers tels que $u=x^i$ et $v=x^j.$ Alors $v^{-1} = x^{-j}$ et $uv^{-1} = x^{i-j}.$ Vous effectuez la division euclidienne de $i-j$ par $d$ il existe deux entiers $a$ et $b$ avec $0\leq b\leq d-1$ tels que $i-j = ad+b.$

Alors :

\begin{align*}
uv^{-1} &=x^{i-j}\\
 &= x^{ad+b}\\
&=(x^d)^ax^b\\
&= 1^a x^b\\
&= x^b.
\end{align*} 

Cette dernière égalité montre que $uv^{-1}\in H.$

Vous en déduisez que $H$ est un sous-groupe de $G.$ Par le théorème de Lagrange, le nombre d’éléments de $H$ divise le nombre d’éléments de $G$ et ainsi :

\boxed{d\mid n.}

Partitionnez le groupe $G$ en fonction des ordres

Pour tout entier naturel non nul $d$ divisant $n$ vous notez :

\Omega_d = \{x\in G, d\text{ est un ordre pour  }x\}.

Par définition, vous avez :

\forall d\in\llbracket 1, n\rrbracket, d\mid n \implies \Omega_d\subset G.

Vous en déduisez l’inclusion suivante :

\boxed{\bigcup_{d\mid n} \Omega_d \subset G.}

Réciproquement, soit $x$ un élément de $G.$ Il a été démontré qu’il existe un entier naturel non nul $r$ avec $r\mid n$ tel que $x$ admette $r$ pour ordre. Du coup, $x\in \Omega_r.$ Par suite l’inclusion suivante est acquise :

\boxed{G \subset \bigcup_{d\mid n} \Omega_d .}

Par double inclusion vous avez obtenu :

\boxed{G = \bigcup_{d\mid n} \Omega_d.}

Il s’agit de démontrer que cette union est disjointe.

Soient $d$ et $d’$ deux entiers naturels non nuls avec $d\mid n$ et $d’\mid n$, tels que $\Omega_d\cap \Omega_{d’} \neq \emptyset.$ Il existe $x$ appartenant à la fois à $\Omega_d$ et à $\Omega_{d’}.$ Donc $x$ admet pour ordre $d$ et $x$ admet aussi pour ordre $d’.$ On en déduit $x^d = x^{d’}=1.$ Comme $x^d = 1$ et que $d’$ est un ordre pour $x$, vous déduisez $d’\mid d.$ Comme $x^{d’}=1$ et que $d$ est un ordre pour $x$, vous déduisez $d\mid d’$ et donc $d= d’.$

Note. On retrouve le fait que tout élément d’un groupe fini admet un ordre qui est unique.

L’union $G = \bigcup_{d\mid n} \Omega_d$ étant disjointe, vous avez obtenu une partition de $G$ ce qui permet d’écrire :

\boxed{n = \sum_{d\mid n}\,(\text{nombre d'élements de }\Omega_d).}

Note. Dans certains ouvrages, il est imposé, pour utiliser le terme « partition » d’un ensemble, d’avoir en plus de l’union disjointe, un ensemble non vide pour chaque partie composant cette union. Il est considéré ici que cette restriction n’est pas pertinente dans la mesure où il est tout à fait possible que $\Omega_d$ puisse être vide pour certains diviseurs $d$ de $n.$

Majorez le nombre d’éléments de $\Omega_d$ pour tout diviseur $d$ de $n$

Soit $d$ un entier naturel non nul tel que $d\mid n.$ Il est rappelé que $\varphi(d)\geq 1.$

Dans l’hypothèse où $\Omega_d$ est vide, vous avez déjà :

\text{nombre d'élements de }\Omega_d \leq \varphi(d).

Supposez maintenant que $\Omega_d$ soit non vide. Il existe un élément $x\in G$ d’ordre $d.$ Comme cela a déjà été démontré ci-dessus, l’ensemble $H$ suivant possède $d$ éléments :

H = \{x^i, i\in\llbracket 0, d-1\rrbracket\}.

Soit $y$ un élément de $H.$ Il existe un entier $i$ tel que $y = x^i.$ Alors :

\begin{align*}
y^d &= (x^î)^d\\
&= (x^d)^i\\
&= 1^i\\
&=1.
\end{align*}

Ainsi, $H$ est inclus dans l’ensemble $S$ des racines du polynôme $X^d-1$ qui est de degré $d$ à coefficients dans le corps $K.$ Or, un tel polynôme admet au plus $d$ racines, autrement dit, $S$ possède au maximum $d$ éléments. Comme $H\subset S$ et que $H$ possède $d$ éléments, il en résulte que $H = S.$

Soit $z$ un élément de $G$ d’ordre $d.$ Comme $z^d=1$ vous déduisez $z\in S$ et donc $z\in H.$ Il existe un entier $i$ appartenant à l’intervalle $\llbracket 0, d-1\rrbracket$ tel que $z = x^i.$ Vous allez maintenant montrer que les entiers $i$ et $d$ sont premier entre eux.

Notez $u = PGCD(i,d)$ de sorte que $i/u$ et $d/u$ soient deux entiers.

\begin{align*}
z^{d/u} &= (x^i)^{d/u} \\
&= x^{id/u } \\
&=(x^d)^{i/u}\\
&= 1^{i/u}\\
&=1.
\end{align*}

Comme $z$ est d’ordre $d$, il s’ensuit que $d\mid d/u$ donc $ud \mid d$ et $u\mid 1$ ce qui prouve que $u=1.$

Vous venez donc de montrer que :

\forall z\in G, z\text{ est d'ordre }d\implies (\exists i\in\llbracket0, d-1\rrbracket, PGCD(i,d)=1 \text{ et } z = x^i).

Notez $A_d$ l’ensemble comportant $\varphi(d)$ éléments, défini par :

A_d = \{ i\in\llbracket 0, d-1\rrbracket, PGCD(i,d)=1\}.

Vous avez établi que :

\Omega_d \subset \{x^i, i\in A_d\}.

Il est rappelé que l’ensemble $H$ suivant possède $d$ éléments :

H = \{x^i, i\in\llbracket 0, d-1\rrbracket\}.

Du coup, l’application qui va de $\llbracket 0, d-1\rrbracket$ dans $H$ et qui est définie par $i\mapsto x^i$ est injective. Par restriction, l’application qui va de $A_d$ dans $H$ définie par $i\mapsto x^i$ est aussi injective. Donc le nombre d’éléments de l’ensemble $\{x^i, i\in A_d\}$ est égal au nombre d’éléments de $A_d$ soit $\varphi(d).$

L’inclusion $\Omega_d \subset \{x^i, i\in A_d\}$ fournit l’inégalité :

\text{nombre d'élements de }\Omega_d \leq \varphi(d).

En définitive, il vient d’être démontré que :

\boxed{\forall d\in\NN, d\mid n\implies \text{nombre d'élements de }\Omega_d \leq \varphi(d).}

Utilisez le lien avec la fonction indicatrice $\varphi$ d’Euler pour conclure

D’une part :

n = \sum_{d\mid n}\,(\text{nombre d'élements de }\Omega_d).

D’autre part, selon le contenu rédigé dans l'article 351, la fonction indicatrice d’Euler vérifie l’égalité :

n = \sum_{d\mid n}\,\varphi(d).

Par différence, vous déduisez :

0 = \sum_{d\mid n}\,\left[\varphi(d)-(\text{nombre d'élements de }\Omega_d)\right].

Il a été vu que les termes de cette somme sont positifs. Comme leur somme est nulle, il en résulte que :

\forall d\in\NN, d\mid n \implies \varphi(d) = \text{nombre d'élements de }\Omega_d.

En particulier, $\Omega_n$ possède $\varphi(n)$ éléments. Comme $\varphi(n)\geq 1$ l’ensemble $\Omega_n$ est non vide. Autrement dit, le groupe $G$ est cyclique.

352. Résolvez une équation avec congruence dans le cas linéaire

Dans cet article, vous trouverez des moyens de résoudre une équation de la forme $ax\equiv b \quad [n].$ Le but est d’essayer de diviser successivement le nombre $a$ jusqu’à obtenir $1$ mais certaines précautions doivent être prises.

Quand les trois coefficients admettent un diviseur commun

Fixez trois nombres entiers $a$, $b$ et $n.$ Soit à résoudre l’équation ci-dessous dont l’inconnue $x$ est un nombre entier :

\boxed{(E): \quad ax \equiv b \quad [n].}

Supposez qu’il existe un entier non nul $d$ tel que :

\left\{\begin{align*}
d&\mid a\\
d&\mid b\\
d&\mid n.
\end{align*}\right.

Vous notez $a’$, $b’$ et $n’$ les quotients correspondants, qui sont aussi des nombres entiers :

\left\{\begin{align*}
a' &= a/d\\
b' &= b/d\\
n' &= n/d.
\end{align*}\right.

Vous considérez l’équation suivante dont l’inconnue $x$ est un nombre entier :

\boxed{(E'): \quad a'x \equiv b' \quad [n'].}

Alors les équations $(E)$ et $(E’)$ ont le même ensemble de solutions.

En effet :

\begin{align*}
x\text{ est solution de }(E)  &\Longleftrightarrow ax\equiv b\quad [n]\\
&\Longleftrightarrow n\mid ax- b \\
&\Longleftrightarrow \exists k\in\Z,  ax- b = kn \\
&\Longleftrightarrow \exists k\in\Z,  da'x- db' = kdn' \\
&\Longleftrightarrow \exists k\in\Z,  d(a'x- b') = kdn' \\
&\Longleftrightarrow \exists k\in\Z,  a'x- b' = kn' \\
&\Longleftrightarrow  n' \mid a'x- b'  \\
&\Longleftrightarrow a'x\equiv b'\quad [n]\\
&\Longleftrightarrow x\text{ est solution de }(E').
\end{align*} 

Note. Si équation de la forme $ax\equiv b\quad [n]$ possède au moins une solution, alors $b$ est nécessairement divisible $PGCD(a,n).$

Dans la suite, vous vous attachez à une équation linéaire avec congruence, en supposant désormais que $PGCD(a,n)=1.$

Quand $a$ est premier avec $n$ la congruence modulo $n$ est conservée après une division

Fixez trois nombres entiers $a$, $b$ et $n.$ Vous supposez que $PGCD(a,n)=1$ et qu’il existe un entier non nul $d$ tel que $d\mid a$ et $d\mid b.$ Comme précédemment, vous posez :

\left\{\begin{align*}
a' &= a/d\\
b' &= b/d.
\end{align*}\right.

Alors les équations suivantes possédant la même congruence modulo $n$ ont le même ensemble de solutions :

\begin{align*}
(E): \quad ax &\equiv b \quad [n]\\
(E'): \quad a'x &\equiv b' \quad [n].
\end{align*}

Première étape. Soit $x$ une solution de l’équation $(E’).$ Alors $n \mid a’x-b’.$ Or $ax-b = da’x-db’ = d(a’x-b’).$ Donc $a’x-b’ \mid ax-b.$ Par transitivité, vous déduisez $n \mid ax-b$ et par suite $ax\equiv b \quad [n]$ et $x$ est solution de $(E).$

Seconde étape. Soit maintenant $x$ une solution de $(E).$ Alors $n \mid ax-b$ ce qui s’écrit $n\mid d(a’x-b’).$ Par définition, $PGCD(n,d)$ divise $d.$ Or $d\mid a$ et par transitivité $PGCD(n,d) \mid a.$ Toujours avec la définition du $PGCD$, $PGCD(n,d) \mid n.$ Comme $PGCD(n,d)$ divise à la fois $a$ et $n$ qui sont premiers entre eux, il en résulte que $PGCD(n,d)=1.$ En appliquant le théorème de Gauss, $n\mid d(a’x-b’)$ fournit $n\mid a’x-b’$ et $a’x\equiv b’\quad [n]$ et $x$ est solution de $(E’).$

Appliquez les résultats précédents sur des exemples

Résolvez l’équation $3x\equiv 4\quad [5]$

Vous remarquez que $PGCD(3,5)=1.$ La stratégie va consister à remplacer $4$ par un nombre congru modulo $5$ qui est aussi un multiple de $3.$

Or, vous avez :

\begin{align*}
4 &\equiv 4+5\quad [5]\\
&\equiv 9\quad [5].
\end{align*} 

Vous pouvez diviser par $3$ à la dernière étape pour conclure :

\begin{align*}
3x\equiv 4\quad [5] \Longleftrightarrow 3x\equiv9\quad [5]\\
\Longleftrightarrow x\equiv3 \quad [5].
\end{align*}

L’ensemble des solutions de cette équation est :

\mathscr{S} = \{3+5k, k\in\Z\}.

Résolvez l’équation $18x\equiv 42\quad [50]$

Vous calculez d’abord $PGCD(18,50)$ en utilisant le fait que $PGCD(9,25)=1$ combiné avec la propriété multiplicative du $PGCD.$

\begin{align*}
PGCD(18,50) &= 2PGCD(9,25)\\
&= 2\times 1\\
&=2.
\end{align*}

La congruence modulo $50$ se simplifie en une congruence modulo $25.$

\begin{align*}
18x\equiv 42\quad [50] \Longleftrightarrow 9x\equiv 21\quad [25].
\end{align*}

Vous allez maintenant ajouter ou soustraire $25$ un certain nombre de fois à $21$ jusqu’à tomber sur un multiple de $9.$

\begin{align*}
 9x\equiv 21\quad [25] &\Longleftrightarrow 9x\equiv 21\quad [25]\\
& \Longleftrightarrow 9x\equiv 46\quad [25] \\
&\Longleftrightarrow 9x\equiv 71\quad [25] \\
&\Longleftrightarrow 9x\equiv 96\quad [25] \\
&\Longleftrightarrow 9x\equiv 121\quad [25] \\
&\Longleftrightarrow 9x\equiv 146\quad [25] \\
&\Longleftrightarrow 9x\equiv 171\quad [25] \\
&\Longleftrightarrow 9x\equiv 19\times 9\quad [25]\\
&\Longleftrightarrow x\equiv 19\quad [25].
\end{align*}

L’ensemble des solutions de cette équation est :

\mathscr{S} = \{19+25k, k\in\Z\}.

La méthode ci-dessus fonctionne systématiquement

Fixez trois nombres entiers $a$, $b$ et $n.$ Vous supposez que $PGCD(a,n)=1.$ Vous allez démontrer qu’il existe un entier $q$ tel que $a\mid b+qn.$

En effet, comme $a$ et $n$ sont deux entiers premiers entre eux, en appliquant le théorème de Bezout, il existe deux entiers $u$ et $v$ tels que $au+nv = 1.$ En multipliant par $b$, il vient :

\begin{align*}
&b= abu+bvn\\
&b+(-bv)n = abu.
\end{align*}

En posant $q= -bv$ vous avez l’égalité $b+qn = abu$ si bien que $a\mid b+qn.$

Cela justifie la technique utilisée dans l’exemple précédent.

Quand vous cherchez à résoudre $9x\equiv 21\quad [25]$, vous savez à l’avance qu’il existe un entier $q$ tel que $9 \mid 21+25q.$ Pour un tel entier, vous avez :

\begin{align*}
 9x\equiv 21\quad [25] &\Longleftrightarrow 9x\equiv 21 + 25q\quad [25].

\end{align*}

En notant $h$ le quotient de la division de $21+25q$ par $9$, vous aboutissez à :

\begin{align*}
 9x\equiv 21\quad [25] &\Longleftrightarrow x\equiv h\quad [25].
\end{align*}

La division par $9$ est autorisée sans modifier la congruence modulo $25$ puisque $PGCD(9,25)=1.$

351. La somme des valeurs de l’indicatrice d’Euler prise sur tous les diviseurs d’un entier naturel n non nul est égale à n

Pour tout entier naturel $n$ non nul, vous notez $\varphi(n)$ le nombre d’entiers naturels inférieurs ou égaux à $n-1$ qui sont premiers avec $n.$

Pour tout $n\in\NN$ vous notez :

A_n = \{k\in\llbracket0, n-1\rrbracket, PGCD(k,n)=1\}.

Alors $\varphi(n)$ désigne le nombre d’éléments de l’ensemble $A_n.$

L’objectif de cet article est de démontrer que :

\boxed{\forall n\in\NN, \quad n = \sum_{d\mid n}\varphi(d).}

Note. Pour tout entier $n$ non nul, la somme $\sum_{d\mid n} \varphi(d)$ désigne la somme $\sum_{\substack{1\leq d\leq n \\ d\mid n}} \varphi(d).$

Visualisez la situation pour $n=60$

Déterminez tous les diviseurs de $60$

Le nombre $60$ s’écrit comme un produit faisant apparaître les puissances des nombres premiers $2$, $3$ et $5$ étant donné que :

60 =2^2\times 3\times 5.

$4 = 2^2$ possède trois diviseurs, $1$, $2$ et $4.$

$3$ possède deux diviseurs, $1$ et $3.$

$5$ possède deux diviseurs, $1$ et $5.$

Utilisant le principe du produit, $60$ possède $3\times 2 \times 2 = 12$ diviseurs obtenus comme suit :

\begin{align*}
1\times 1\times 1 &= 1\\
1\times 1\times 5 &= 5\\
1\times 3\times 1 &= 3\\
1\times 3\times 5 &= 15\\
2\times 1\times 1 &= 2\\
2\times 1\times 5 &= 10\\
2\times 3\times 1 &= 6\\
2\times 3\times 5 &= 30\\
4\times 1\times 1 &= 4\\
4\times 1\times 5 &= 20\\
4\times 3\times 1 &= 12\\
4\times 3\times 5 &= 60.
\end{align*}

Vous notez $D$ l’ensemble des diviseurs de $60$, à savoir :

\boxed{D=\{1, 2,3, 4, 5,6, 10, 12, 15, 20, 30, 60\}.}

Parmi tous les entiers compris entre $0$ et $59$ déterminez leur $PGCD$ avec $60$

Vous remplissez les tableaux suivants :

\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline
k & 0 & 1& 2& 3& 4& 5& 6& 7& 8 & 9\\
\hline
PGCD(k,60) & 60 & 1 & 2 & 3 & 4 & 5 & 6 & 1 & 4 & 3\\
\hline
\end{array}
\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline
k & 10 & 11& 12& 13& 14& 15& 16& 17& 18 & 19\\
\hline
PGCD(k,60) & 10 & 1 & 12 & 1 & 2 & 15 & 4 & 1 & 6 & 1\\
\hline
\end{array}
\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline
k & 20 & 21& 22& 23& 24& 25& 26& 27& 28 & 29\\
\hline
PGCD(k,60) & 20 & 3 & 2 & 1 & 12 & 5 & 2 & 3 & 4 & 1\\
\hline
\end{array}
\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline
k & 30 & 31& 32& 33& 34& 35& 36& 37& 38 & 39\\
\hline
PGCD(k,60) & 30 & 1 & 4 & 3 & 2 & 5 & 12 & 1 & 2 & 3\\
\hline
\end{array}
\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline
k & 40 & 41& 42& 43& 44& 45& 46& 47& 48 & 49\\
\hline
PGCD(k,60) & 20 & 1 & 6 & 1 & 4 & 15 & 2 & 1 & 12 & 1\\
\hline
\end{array}
\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline
k & 50 & 51& 52& 53& 54& 55& 56& 57& 58 & 59\\
\hline
PGCD(k,60) & 10 & 3 & 4 & 1 & 6 & 5 & 4 & 3 & 2 & 1\\
\hline
\end{array}

Lorsque $k$ décrit l’ensemble $\llbracket 0, 59\rrbracket$ vous constatez que $PGCD(k,60)$ décrit l’ensemble des diviseurs de $60.$

Vous allez classifier les entiers compris entre $0$ et $59$ selon la valeur que prend leur $PGCD$ avec $60.$

Introduisez une partition

A ce stade, il semblerait naturel de considérer, pour tout $d\in D$ l’ensemble suivant :

 \{k\in\llbracket0, 59\rrbracket, PGCD(k,60)=d\}.

En prenant $d = 60$ cet ensemble serait $\{k\in\llbracket0, 59\rrbracket, PGCD(k,60)=60\}$ et il ne contiendrait qu’un seul élément, or il serait souhaitable qu’il en contienne $\varphi(60).$

Du coup, il convient de considérer, pour tout $d\in D$ l’ensemble :

\Omega_d =  \{k\in\llbracket0, 59\rrbracket, PGCD(k,60)=60/d\}.

Cette définition permet de s’assurer que l’ensemble $\Omega_{60}$ contient exactement $\varphi(60)$ éléments.

Vous remarquez que la famille $(\Omega_d)_{d\in D}$ est une partition de l’ensemble $\llbracket 0, 59\rrbracket.$

En effet, vous avez :

\begin{align*}
\Omega_{1} &= \{0\} \\
\Omega_{2} &= \{30\} \\
\Omega_{3} &= \{20,40\} \\
\Omega_{4} &= \{15, 45\} \\
\Omega_{5} &= \{12, 24, 36, 48\} \\
\Omega_{6} &= \{10, 50\} \\
\Omega_{10} &= \{6, 18, 42, 54\} \\
\Omega_{12} &= \{5, 25, 35, 55\} \\
\Omega_{15} &= \{4, 8, 16, 28, 32, 44, 52, 56\} \\
\Omega_{20} &= \{3, 9, 21, 27, 33, 39, 51, 57 \} \\
\Omega_{30} &= \{2, 14, 22, 26, 34, 38, 46, 58\} \\
\Omega_{60} &= \{1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59\} \\
\end{align*}

En évaluant la fonction $\varphi$ sur les diviseurs de $60$, vous obtenez le tableau suivant :

\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
d & 1 & 2& 3& 4& 5& 6& 10& 12& 15 & 20 & 30 & 60\\
\hline
\varphi(d) & 1 & 1 & 2 & 2 & 4 & 2 & 4& 4 & 8 & 8 &8 & 16\\
\hline
\end{array}

Vous constatez alors que :

\forall d\in D, \Omega_d\text{ possède }\varphi(d)\text{ éléments.}

Il s’ensuit que :

\begin{align*}
60&=\sum_{d\in D} \text{nombre d'éléments de }\Omega_d \\
&= \sum_{d\in D}\varphi(d)\\
&= \sum_{d\mid 60}\varphi(d).
\end{align*} 

Traitez le cas général

Soit $n$ un entier naturel non nul fixé.

Introduisez les notations

Vous notez $D$ l’ensemble des diviseurs de $n$, défini par :

D = \{d\in\NN, d\mid n\}.

Enfin, pour tout $d\in D$ vous notez $\Omega_d$ l’ensemble suivant :

\Omega_d = \{k\in\llbracket 0, n-1\rrbracket, PGCD(k,n)=n/d\}.

Pour tout $d\in D$ déterminez le nombre d’éléments de l’ensemble $\Omega_d$

Soit $d\in D.$ Alors $\frac{n}{d}$ est un entier non nul.

Par définition, $\varphi(d)$ est le nombre d’éléments de l’ensemble :

A_d = \{k\in\llbracket0, d-1\rrbracket, PGCD(k,d)=1\}.

Vous considérez la fonction $f$ suivante qui va de $A_d$ dans $\Omega_d$, définie par :

\forall x\in A_d, f(x) = \frac{n}{d}x.

Montrez que $f$ est bien définie

Soit $x\in A_d.$ Alors $x$ est un entier compris entre $0$ et $d-1$ et $PGCD(x,d)=1.$ Comme $\frac{n}{d}$ est un entier naturel, il en est de même de $\frac{n}{d}x.$ Or, $x < d.$ Après multiplication par $\frac{n}{d}$ vous avez $\frac{n}{d}x < n$ donc $\frac{n}{d}x\in\llbracket 0, n-1\rrbracket.$

Le $PGCD$ étant multiplicatif, l’égalité $PGCD(x,d)=1$ fournit $PGCD\left(\frac{n}{d}x, n\right) = \frac{n}{d}$ après multiplication par $\frac{n}{d}.$ Ainsi, $f(x)\in \Omega_d$ et la fonction $f$ est bien définie.

Montrez que $f$ est bijective

Soient $x$ et $y$ deux éléments de $A_d$ tels que $f(x) = f(y)$, alors $\frac{n}{d}x = \frac{n}{d}y$ d’où $nx = ny$ après multiplication par $d$, puis $x=y$ après division par $n$ qui est non nul. Donc $f$ est injective.

Soit maintenant $y$ un élément de $\Omega_d.$ $y$ est un entier compris entre $0$ et $n-1$, de sorte que $PGCD(y,n) = \frac{n}{d}.$ Par définition du $PGCD$, l’entier $\frac{n}{d}$ divise $y$. En notant $q\in\N$ le quotient de la division de $y$ par $\frac{n}{d}$, vous avez $y = \frac{n}{d}q.$

Si $q\geq d$ alors $\frac{n}{d}q\geq n$ et $y\geq n$ ce qui est impossible, donc $q < d$ et par suite $q\in\llbracket 0, d-1\rrbracket.$

L’égalité $PGCD(y,n) = \frac{n}{d}$ fournit $PGCD\left( \frac{n}{d}q , n\right) = \frac{n}{d}$ qui devient $PGCD(nq, dn = n)$ après multiplication par $n.$ Or $PGCD(nq, dn) = nPGCD(q,d)$ donc $nPGCD(q,d) = n$ d’où $PGCD(q,d)=1$ après division par $n$ qui est non nul. Ainsi, $q\in A_d.$ Comme $y = \frac{n}{d}q$, vous avez $f(q) = y$ et la surjectivité de $f$ est démontrée.

La fonction $f$ étant à la fois injective et surjective, elle est bijective.

Concluez

Les ensembles $A_d$ et $\Omega_d$ étant en bijection, ils ont le même nombre d’éléments.

Pour tout $d\in D$ :

\boxed{\varphi(d) = \text{nombre d'élements de }\Omega_d.}

Démontrez que la famille $(\Omega_d)_{d\in D}$ est une partition de $\llbracket 0, n-1\rrbracket$

Sur l’égalité $\bigcup_{d\in D} \Omega_d = \llbracket 0, n-1\rrbracket$

Soit $d\in D$ par définition de $\Omega_d$ l’inclusion $\Omega_d\subset \llbracket 0, n-1\rrbracket$ est satisfaite.

Donc :

\bigcup_{d\in D} \Omega_d \subset  \llbracket 0, n-1\rrbracket.

Soit $k$ un élément de $\llbracket 0, n-1\rrbracket.$ Vous notez $d’ = PGCD(k,n).$ Par définition du $PGCD$, $d’ \mid n$ donc il existe un entier naturel $d$ tel que $n = dd’.$ Si $d=0$ alors $n=0$ ce qui est absurde, donc $d\in\NN$ et $d\mid n$ donc $d\in D.$ Comme $PGCD(k,n) = \frac{n}{d}$ il s’ensuit que $k\in \Omega_d.$

Ainsi :

\llbracket 0, n-1\rrbracket \subset \bigcup_{d\in D} \Omega_d.

Par double inclusion, vous avez obtenu :

\boxed{\bigcup_{d\in D} \Omega_d = \llbracket 0, n-1\rrbracket.}

L’union $\bigcup_{d\in D} \Omega_d$ est disjointe

Soient maintenant $d_1$ et $d_2$ deux éléments de $D$ tels que $\Omega_{d_1} \cap \Omega_{d_2} \neq \emptyset.$

Il existe $x\in \Omega_{d_1} \cap \Omega_{d_2}.$ Comme $x\in \Omega_{d_1}$ vous déduisez $PGCD(x,n) = \frac{n}{d_1}.$

Comme $x\in \Omega_{d_2}$, vous avez aussi $PGCD(x,n)=\frac{n}{d_2}.$

Vous déduisez :

PGCD(x,n)=\frac{n}{d_1}=\frac{n}{d_2}.

Du coup, il vient $d_1 = d_2.$

Par contraposée, il a été prouvé ce qui suit :

\boxed{\forall (d_1,d_2)\in D^2, \quad d_1\neq d_2\implies \Omega_{d_1}\cap\Omega_{d_2} = \emptyset.}

Démontrez la relation annoncée dans le cas général

La famille $(\Omega_d)_{d\in D}$ est une partition de l’ensemble $\llbracket 0, n-1\rrbracket$ qui possède $n$ éléments.

Par somme, il vient :

 \begin{align*}
n&=\sum_{d\in D} \text{nombre d'éléments de }\Omega_d \\
&= \sum_{d\in D}\varphi(d).
\end{align*} 

Concluez

La propriété suivante a été démontrée :

\boxed{\forall n\in\NN, \quad n = \sum_{d\mid n}\varphi(d).}

350. Extraction d’une racine carrée entière en commençant avec une multiplication par 5

Si on veut se passer de division, il est possible de calculer la racine carrée entière d’un nombre entier $n$ en utilisant des soustractions successives. Une variante est proposée ici : le nombre de départ dont on souhaite connaître la racine carrée entière est multiplié par $5$ dès le début, ce qui va faciliter le déroulement des étapes ultérieures.

Note. Cette technique évite d’avoir à gérer des multiplications par $2$ qui apparaissent dans la méthode de la potence.

Étudiez la situation sur un exemple

Soit $n = 1562$ un nombre dont on veut connaître la racine carrée entière.

Il s’agit de déterminer l’unique entier $p$ tel que $p\leq \sqrt{n} < p+1.$

Vous formez immédiatement le nombre $m = 5n =7810.$ Vous écrivez ce nombre $m$ comme une succession de tranches de $2$ chiffres, soit $m = 78\ 10.$

Première étape

Vous partez de la première tranche, $78$ en retirez successivement $5$, $15$, $25$ etc et vous stoppez juste avant de trouver un nombre strictement négatif.

Cette étape peut être formalisée dans le tableau ci-dessous :

\begin{array}{|c|c|c|c|}
\hline
78 & 73 & 58 & 33 \\
\hline
5 &  15 & 25 &\\
\hline
\end{array}

Cette étape montre que :

78 = (5+15+25) + 33.

Le nombre de soustractions effectuées est égal à $3$, soit autant de termes contenus dans la somme $5+15+25.$

En vertu des sommes formées par les termes consécutifs d’une suite arithmétique, vous avez :

\begin{align*}
5+15+25 &= 3\times \frac{5+25}{2}\\
& = \frac{3\times 30}{2}\\
&= 3\times 3\times \frac{10}{2}\\
&= 5\times 3^2.
\end{align*} 

Ainsi :

78 = 5\times 3^2 + 33.

Note. Le chiffre $3$ est le premier du résultat de la racine carrée entière cherchée.

Deuxième étape

Vous prenez le reste, à savoir $33$ et vous collez les chiffres de la tranche d’après de $m$, ce qui fournit le nombre $3310.$

Le nombre de soustractions effectuées précédemment est égal à $3$, vous collez à ce nombre $05$ ce qui fait $305.$ Puis vous allez, à partie de $3310$ retrancher $305$, $315$, $325$, $335$ etc et vous stoppez juste avant d’obtenir un nombre strictement négatif.

\begin{array}{|c|c|c|c|c|c|c|c|c|c|}
\hline
3310 & 3005 & 2690 & 2365 & 2030& 1685 &1330 & 965& 590& 205\\
\hline
305 &  315 &  325 & 335 &345 & 355 & 365 & 375 & 385\\
\hline
\end{array}

Vu que le nombre de soustractions est égal à $9$, d’après le tableau et les sommes de termes consécutifs d’une suite arithmétique, il vient :

\begin{align*}
3310 &= (305+315+\cdots+385)+205\\
&= 9\times \frac{690}{2}+205\\
&= 9\times 69\times 5+205\\
&= (9\times 60 + 9^2)\times 5 + 205\\
&= (2\times 9\times 30 + 9^2)\times 5 + 205.
\end{align*}

Vous constatez que l’autre facteur de la multiplication par $5$ contient la fin d’une identité remarquable.

Note. Le chiffre $9$ est le deuxième du résultat de la racine carrée entière cherchée.

Comment prouve-t-on que la racine carrée entière de $1562$ est bien $39$ ?

Vous partez de la première étape, vous multipliez par $100$ et vous ajoutez $10$, ce qui fournit :

\begin{align*}
78 &= 5\times 3^2 + 33\\
7800 &= 5\times 3^2 \times 100 + 3300\\
7810 &= 5\times 3^2 \times 10^2 + 3310\\
7810 &= 5\times 30^2 + 3310.
\end{align*} 

En appliquant la deuxième étape, il vient :

\begin{align*}
7810 &= 5\times 30^2 + (2\times 9\times 30 + 9^2)\times 5 + 205\\
&= 5(30^2 + 2\times 9\times 30+9^2) + 205\\
&= 5\times 39^2 + 205.
\end{align*} 

En divisant par $5$, il vient :

1562 = 39^2 + 41.

Il est donc établi que :

1562 \geq 39^2.

Or :

\begin{align*}
39^2+41 &< 39^2+39+40\\
1562 &< 40^2.
\end{align*} 

De ces deux encadrements, vous obtenez :

\begin{align*}
39^2&\leq 1562 < 40^2\\
39 &\leq \sqrt{1562}< 40.
\end{align*} 

Autrement dit, la racine carrée entière de $1562$ est égale à $39.$

Cas où $n\leq 1999$

Soit $n$ un entier naturel inférieur ou égal à $1999$, de sorte que $5n<9995.$

En posant $m = 5n$, vous constatez que $m$ possède deux tranches de deux chiffres, autrement dit, $m = 100c+u$ où $c$ est $u$ sont deux entiers naturels inférieurs ou égaux à $99.$ Comme $m$ est un multiple de $5$, l’entier $u$ est aussi un multiple de $5$ et vaut $95$ au maximum.

La première tranche

Comme tout à l’heure, vous effectuez un certain nombre de soustractions (voire aucune), vous retranchez à $c$ les entiers $5$, $15$, $25$ juste avant de trouver un nombre strictement négatif. Tous ces entiers sont de la forme $10k-5$ avec $k$ entier supérieur ou égal à $1.$

Soit $k$ le nombre de soustractions effectuées.

Premier cas. Supposez $c\geq 5.$ Alors $k\geq 1.$

Les deux inégalités sont vérifiées :

\begin{align*}
& 5+\dots+(10k-5) \leq c\\
&c <  5+\dots+(10k+5).
\end{align*} 

Le nombre de termes de la somme $5+\dots+(10k-5)$ est égal à $k$, si bien que :

\begin{align*}
5+\dots+(10k-5) &= k\times \frac{5+10k-5}{2}\\
&=5k^2.
\end{align*}

Le nombre de termes de la somme $5+\dots+(10k-5)$ est égal à $k+1$, si bien que :

\begin{align*}
5+\dots+(10k+5) &= (k+1)\times \frac{5+10k+5}{2}\\
&= (k+1)\times \frac{10(k+1)}{2}\\
&=5(k+1)^2.
\end{align*}

Par ce procédé, pour trouvez un entier $k$ tel que :

5k^2\leq c < 5(k+1)^2.
\begin{array}{|c|c|c|c|}
\hline
c & \dots & \dots & c-5k^2 \\
\hline
5 & \dots & \dots &\\
\hline
\end{array}

Remarquez que $c<100$ si bien que $5k^2< 100$ donc $k^2<20$ d’où $k^2<25$ donc $k<5$ puis $k\leq 4.$ Ainsi $k$ est bien un chiffre.

Second cas. Supposez $c<5.$ Alors le nombre de soustractions est égal à $0$ et vous posez $k=0.$ Comme $5(k+1)^2 =20 $·K² 5, l’inégalité $5k^2\leq c < 5(k+1)^2$ est encore satisfaite.

Dans les deux cas, l’inégalité $\boxed{5k^2\leq c < 5(k+1)^2}$ est valable et $k\in\llbracket 0, 4\rrbracket$ est un chiffre.

La seconde tranche

Lorsque vous effectuez les $k$ soustractions précédentes au nombre $c$, vous obtenez un reste qui est égal à :

r = c-5k^2.

Comme $c <5(k+1)^2$ il convient de noter que $c<5(k^2+2k+1)$ donc $c-5k^2< 10k+5.$

Il s’ensuit que $\boxed{0\leq r \leq 10k+4.}$

A partir de ce reste, vous collez la deuxième tranche $u.$ Or c’est multiplier $r$ par $100$ et ajouter $u.$

Le nombre $p = 100r+u$ est ainsi obtenu.

C’est à partir de ce nombre que vous allez coller $05$ au chiffre $k$ calculé précédemment.

Concrètement, vous allez soustraire $100k+5$, $100k+15$, $100k+25$ au nombre $p$ jusqu’à vous arrêter avant de tomber sur un nombre strictement négatif.

Notez $\ell$ le nombre de soustractions effectuées.

Premier cas. Supposez que $p\geq 100k+5$, soit $p\geq 5(20k+1)$ de sorte que $\ell \geq 1.$

Alors :

\begin{align*}
& (100k+5)+\dots+(100k+10\ell-5) \leq p\\
&p <  (100k+5)+\dots+(100k+10\ell+5).
\end{align*} 

Le nombre de termes de la somme $(100k+5)+\dots+(100k+10\ell-5)$ est égal à $\ell$, si bien que :

\begin{align*}
(100k+5)+\dots+(100k+10\ell-5)  &= \ell\times \frac{100k+5+100k+10\ell-5}{2}\\
&=\ell\times \frac{200k+10\ell}{2}\\
&=\ell\times (100k+5\ell)\\
&=5\ell\times (20k+\ell).
\end{align*}

Le nombre de termes de la somme $(100k+5)+\dots+(100k+10\ell+5)$ est égal à $\ell+1$, si bien que :

\begin{align*}
(100k+5)+\dots+(100k+10\ell+5)  &= (\ell+1)\times \frac{100k+5+100k+10\ell+5}{2}\\
&=(\ell+1)\times \frac{200k+10\ell+10}{2}\\
&=(\ell+1)(100k+5\ell+5)\\
&=5(\ell+1)(20k+\ell+1).
\end{align*}

Par ce procédé, vous trouvez un entier $\ell$ tel que :

\boxed{5\ell\times (20k+\ell) \leq p < 5(\ell+1)(20k+\ell+1).}
\begin{array}{|c|c|c|c|c|c|c|c|c|c|}
\hline
p = 100r+u & \dots & \dots & \dots & \dots& \dots &\dots & \dots& \dots&p-5\ell\times (20k+\ell)\\
\hline
100k+5 & \dots &  \dots & \dots &\dots & \dots & \dots & \dots & \dots\\
\hline
\end{array}

Second cas. Supposez que $p< 100k+5$, soit $p< 5(20k+1)$ de sorte que $\ell = 0.$ Alors, $p$ étant positif, l’inégalité $5\ell\times (20k+\ell) \leq p < 5(\ell+1)(20k+\ell+1)$ est encore valable : en effet, quand $\ell=0$ vous avez $5(\ell+1)(20k+\ell+1) = 5(20k+1).$

Le nombre $\ell$ est bien un chiffre

Raisonnez par l’absurde en supposant que $\ell \geq 10.$

Du coup :

\begin{align*}
& p\geq 50(20k+10)\\
&p  \geq 1000k+500\\
&100r+u\geq 1000k+500.

\end{align*}

Comme $95\geq u$ vous déduisez ce qui suit :

\begin{align*}
&100r+95\geq 100r+u\\
&100r+95 \geq 1000k+500.
\end{align*}

Cela fournit :

100r\geq 1000k+405.

Il a été montré précédemment que :

r\leq 10k+4.

Après multiplication par $100$, il vient :

100r\leq 1000k+400 < 1000k+405\leq 100r.

D’où la contradiction recherchée.

Donc $\ell$ est bien un chiffre.

Prouvez que la racine carrée entière de $n$ est égale à $10k+\ell$

Vous partez de l’encadrement obtenu à partir de la deuxième tranche et l’ensemble s’enchaîne :

\begin{align*}
5 (20k+\ell) &\leq p < 5(\ell+1)(20k+\ell+1)\\
5 (20k+\ell) &\leq 100r+u < 5(\ell+1)(20k+\ell+1)\\
5 (20k+\ell) &\leq 100(c-5k^2)+u < 5(\ell+1)(20k+\ell+1)\\
5 (20k+\ell) &\leq 100c-500k^2+u < 5(\ell+1)(20k+\ell+1)\\
5 (20k+\ell)+500k^2 &\leq 100c+u < 5(\ell+1)(20k+\ell+1)+500k^2\\
5 (20k+\ell)+500k^2 &\leq m < 5(\ell+1)(20k+\ell+1)+500k^2\\
5 (20k+\ell)+500k^2 &\leq 5n < 5(\ell+1)(20k+\ell+1)+500k^2\\
 \ell(20k+\ell)+100k^2 &\leq n < (\ell+1)(20k+\ell+1)+100k^2\\
(10k)^2 +2(10k) \ell + \ell^2&\leq n < (10k)^2+2(10k)(\ell+1)+(\ell+1)^2\\
(10k+\ell)^2 &\leq n < (10k+\ell+1)^2.
\end{align*}

Il en résulte que :

\boxed{10k+\ell \leq \sqrt{n} < (10k+\ell)+1.}

Ainsi la racine carrée entière de $n$ a bien été déterminée.

Prolongements

Démontrez que la méthode décrite ci-dessus reste valable pour des nombres plus grands, quitte à rajouter des tranches supplémentaires.

Soit $n$ un entier tel que $n\leq 199999$, de sorte que $5n \leq 999995.$ En découpant $m=5n$ en trois tranches de deux chiffres, vous avez $m = 10000a+100b+c$ où $a$, $b$ et $c$ sont des entiers naturels tels que $a\leq 99$, $b\leq 99$ et $c\leq 95.$

En appelant $k$ le nombre de soustractions de la première tranche, $\ell$ le nombre de soustractions de la deuxième tranche et $h$ le nombre de soustractions de la troisième tranche, démontrez que $k$, $\ell$ et $h$ sont des chiffres et que la racine carrée entière de $n$ est égale à $100k+10\ell+h.$

Généralisez alors à un entier naturel $n$ quelconque : posez encore $m=5n$ que vous découpez en $r$ tranches de deux chiffres et poursuivez.

349. Démontrez que le nombre de Mersenne n°11 n’est pas premier et que le nombre de Mersenne n°13 est premier

Pour tout entier naturel $n$, vous notez $M_n$ le nombre de Mersenne numéro $n$, défini par la formule suivante :

M_n = 2^n-1.

Dans cet article, vous cherchez à déterminer des diviseurs premiers candidats des nombres $M_{11}$ et $M_{13}$ afin d’éviter des tests successifs de divisibilité qui peuvent rapidement devenir longs.

Étudiez le nombre de Mersenne n°11

Analyse

Par définition :

\begin{align*}
M_{11} &= 2^{11}-1\\
&= 2^4 2^4 2^3-1\\
&=16\times 16\times 8 -1\\
&=256\times 8 -1\\
&=2048 - 1\\
&=2047.
\end{align*} 

Supposez que $M_{11}$ ne soit pas un nombre premier. Alors il existe deux diviseurs propres de $M_{11}$, notés $d$ et $d’$, tels que $2\leq d\leq 2046$ puis $2\leq d’\leq 2046$ et $2047 = dd’.$

Si $d$ et $d’$ sont tous les deux strictement supérieurs à $\sqrt{2047}$ il s’ensuit que $dd’ > (\sqrt{2047})^2$ donc $dd’ > 2047$ ce qui est absurde.

Donc $2047$ admet un diviseur propre inférieur ou égal à $\sqrt{2047}.$ Par suite, ce diviseur propre, supérieur ou égal à $2$ est divisible par un nombre premier $p.$ Ce nombre premier $p$ divise donc $2047.$

Comme $40^2 =1600$ et comme $50^2=2500$, vous calculez $45^2 =2025.$ Puis $46^2 =45^2 + 45+46 =2025+45+46 =2070+46 =2116.$ Ces résultats prouvent que $45<\sqrt{2047}<46.$ Comme $p\leq \sqrt{2047} < 46$ vous déduisez que $\boxed{p\leq 45.}$

Il serait possible de tester tous les nombres premiers inférieurs ou égaux à $45$ mais il y en a encore trop.

Un argument de théorie des groupes va permettre de limiter grandement les possibilités.

Comme $2047 = 2^{11}-1$ et comme $p\mid 2^{11}-1$, il s’ensuit que :

2^{11}\equiv 1\mod p.

Cette écriture montre que $2$ est inversible modulo $p$ (et que $2^{10}$ est son inverse modulo $p.$)

Notez $r$ l’ordre de $2$ modulo $p.$ Comme $2^{11} \equiv 1 \mod p$, vous avez $r\mid 11.$ Or, $11$ est un nombre premier, donc $r = 1$ ou $r=11.$

Si $r=1$, alors $2\equiv 1 \mod p$ donc $1\equiv 0 \mod p$ donc $p\mid 1$ ce qui est absurde.

Donc $r=11.$

D’après le petit théorème de Fermat, $2^{p-1}\equiv 1 \mod p$ donc $r\mid p-1$ ce qui s’écrit : $p\equiv 1 \mod 11.$

Vous en déduisez que :

p\in\{1, 12, 23, 34, 45\}.

De cette liste, vous excluez $1$ qui n’est pas premier car strictement inférieur à $2$. Vous excluez $12$ et $34$ qui sont pairs et divisibles par $2$ donc non premiers. Vous excluez aussi $45$ qui est divisible par $5.$

Vous en déduisez que $\boxed{p=23.}$

Synthèse

D’après ce qui précède, si $2047$ n’est pas un nombre premier, il est divisible par $23.$

En effectuant la division, vous constatez que $\frac{2047}{23} = 89.$

Concluez

Ainsi, $2047 = 23\times 89.$

\boxed{M_{11} \text{ n'est pas un nombre premier.}}

Étudiez le nombre de Mersenne n°13

Analyse

Par définition :

\begin{align*}
M_{13} &= 2^{13}-1\\
&= 2^{11} \times 4-1\\
&=2048\times 4 -1\\
&=8192 -1\\
&=8191.
\end{align*} 

Supposez que $M_{13}$ ne soit pas un nombre premier. Alors il existe deux diviseurs propres de $M_{13}$, notés $d$ et $d’$, tels que $2\leq d\leq 8190$ puis $2\leq d’\leq 8190$ et $8191 = dd’.$

Si $d$ et $d’$ sont tous les deux strictement supérieurs à $\sqrt{8191}$ il s’ensuit que $dd’ > (\sqrt{8191})^2$ donc $dd’ > 8191$ ce qui est absurde.

Donc $8191$ admet un diviseur propre inférieur ou égal à $\sqrt{8191}.$ Par suite, ce diviseur propre, supérieur ou égal à $2$ est divisible par un nombre premier $p.$ Ce nombre premier $p$ divise donc $8191.$

Comme $90^2 =8100$ et comme $91^2=90^2+90+91 =8100+181=8281$, vous avez $90<\sqrt{8191}<91.$ Comme $p\leq \sqrt{8191} < 91$ vous déduisez que $\boxed{p\leq 90.}$

Comme $8191 = 2^{13}-1$ et comme $p\mid 2^{13}-1$, il s’ensuit que :

2^{13}\equiv 1\mod p.

Cette écriture montre que $2$ est inversible modulo $p$ (et que $2^{12}$ est son inverse modulo $p.$)

Notez $r$ l’ordre de $2$ modulo $p.$ Comme $2^{13} \equiv 1 \mod p$, vous avez $r\mid 13.$ Or, $13$ est un nombre premier, donc $r = 1$ ou $r=13.$

Si $r=1$, alors $2\equiv 1 \mod p$ donc $1\equiv 0 \mod p$ donc $p\mid 1$ ce qui est absurde.

Donc $r=13.$

D’après le petit théorème de Fermat, $2^{p-1}\equiv 1 \mod p$ donc $r\mid p-1$ ce qui s’écrit : $p\equiv 1 \mod 13.$

Vous en déduisez que :

p\in\{1, 14, 27, 40, 53, 66, 79\}.

De cette liste, vous excluez $1$ qui n’est pas premier car strictement inférieur à $2$. Vous excluez $14$, $40$ et $66$ qui sont pairs et divisibles par $2$ donc non premiers. Vous excluez aussi $27$ qui est divisible par $3.$

Du coup :

\boxed{p\in\{ 53, 79\}.}

Synthèse

D’après ce qui précède, si $M_{13} = 8191$ n’est pas un nombre premier, il est divisible par $53$ ou par $79.$

Or, les divisions montrent que $154<\frac{8191}{53}<155$ et que $103<\frac{8191}{79}<104.$

Par contraposée, comme $8191$ n’est divisible ni par $53$, ni par $79$, il est premier.

Concluez

\boxed{M_{13} \text{ est un nombre premier.}}

348. Minorez le PPCM des n premiers entiers naturels

Dans cet article, vous allez démontrer que pour tout entier $n$ non nul, le plus petit multiple commun des entiers naturels allant à de $1$ à $n$, est supérieur ou égal à $\frac{2^n}{4}$, ce qui s’écrit :

\forall n\geq 1, \quad PPCM(1,\dots,n) \geq \frac{2^n}{4}.

Une inégalité et du second degré

Tout d’abord, Ppour tout réel $x$ appartenant à l’intervalle $[0,1]$ vous aller montrer que $x(1-x)\leq \frac{1}{4}.$

Vous fixez un réel $x$ compris entre $0$ et $1.$

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

Le réel $4x(1-x)-1$ est égal à l’opposé d’un carré, il est donc négatif ou nul. Il s’ensuit que :

\begin{align*}
4x(1-x)-1 \leq 0\\
4x(1-x)\leq 1\\
x(1-x)\leq \frac{1}{4}.
\end{align*}

Lien entre un PPCM et une intégrale

Soit $n$ un entier naturel non nul.

Pour tout $x\in [0,1]$, le réel $x(1-x)$ est positif et il est inférieur à $\frac{1}{4}.$ En élevant à la puissance $n$, il vient :

\begin{align*}
(x(1-x))^n\leq \frac{1}{4^n}\\
x^n(1-x)^n \leq \frac{1}{4^n}.
\end{align*}

En intégrant sur l’intervalle $[0,1]$ vous définissez une intégrale notée $I = \int_0^1 x^n(1-x)^n\dx$ et vous avez :

\boxed{I\leq \frac{1}{4^n}.}

En utilisant la formule du binôme, vous avez :

(1-x)^n = \sum_{k=0}^n\binom{n}{k}(-1)^{k}x^k.

En multipliant par $x^n$ il vient :

x^n(1-x)^n = \sum_{k=0}^n \binom{n}{k}(-1)^kx^{n+k}.

En intégrant sur l’intervalle $[0,1]$ vous définissez une intégrale notée $I$ qui se calcule de la façon suivante :

\begin{align*}
I &= \int_0^1 x^n(1-x)^n\dx\\
&= \int_0^1 \sum_{k=0}^n \binom{n}{k}(-1)^kx^{n+k}\dx \\
&=\sum_{k=0}^n \binom{n}{k} (-1)^k\int_0^1 x^{n+k}\dx \\
&= \sum_{k=0}^n \binom{n}{k} (-1)^k\  \left[\frac{x^{n+k+1}}{n+k+1}\right]_0^1\\
&=\sum_{k=0}^n \binom{n}{k} (-1)^k\  \frac{1}{n+k+1}.
\end{align*}

Notez $\mu = PPCM(1,\dots,2n+1)$ le plus petit multiple commun de tous les entiers naturels allant de $1$ jusqu’à $2n+1.$

Vous avez :

\mu I = \sum_{k=0}^n \binom{n}{k} (-1)^k\  \frac{\mu}{n+k+1}.

Or, par définition de $\mu$, quel que soit $k\in\llbracket 0, n\rrbracket$, $n+k+1 \mid \mu$ donc $\frac{\mu}{n+k+1}\in\N.$

Pour tout $k\in \llbracket 0, n\rrbracket$ le coefficient binomial $\binom{n}{k}$ est un nombre entier. Par produit et par somme, vous déduisez que $\mu I$ est un nombre entier relatif.

D’autre part, en utilisant la relation de Chasles sur les intégrales :

I = \int_{0}^{1/4} x^n(1-x)^n\dx + \int_{1/4}^{3/4} x^n(1-x)^n\dx + \int_{3/4}^1 x^n(1-x)^n\dx.

Sur les intervalles $[0,1/4]$ et $[3/4,1]$ la fonction $x\mapsto x^n(1-x)^n$ est positive, il en résulte que, par intégration, les intégrales $\int_{0}^{1/4} x^n(1-x)^n\dx$ et $\int_{3/4}^1 x^n(1-x)^n\dx$ sont positives. Il s’ensuite que :

I\geq \int_{1/4}^{3/4} x^n(1-x)^n\dx.

Or, quand $x\in[1/4, 3/4]$ vous avez aussi $1-x\in[1/4, 3/4]$ si bien que, par produit de réels positifs, $x(1-x)\in[1/16, 9/16].$

Pour tout $x\in[1/4, 3/4]$, $x(1-x)\geq \frac{1}{16}$ donc en élevant à la puissance $n$, il vient $x^n(1-x)^n\geq \frac{1}{16^n}.$ En intégrant sur l’intervalle $[1/4, 3/4]$ vous déduisez :

\begin{align*}
\int_{1/4}^{3/4} x^n(1-x)^n\dx &\geq \int_{1/4}^{3/4} \frac{1}{16^n}\dx \\
&\geq \left(\frac{3}{4}-\frac{1}{4}\right)\frac{1}{16^n}\\
&\geq \frac{1}{2\times 16^n}. 
\end{align*}

Vous déduisez finalement que $I\geq \frac{1}{2\times 16^n}.$ Le réel $I$ est donc strictement positif.

Comme $\mu \geq 1$ vous déduisez que $\mu I$ est un entier strictement positif, donc $\boxed{\mu I \geq 1.}$

En divisant par $I$, vous obtenez $\mu \geq \frac{1}{I}.$

Or, il a été montré que $I\leq \frac{1}{4^n}$ donc $\frac{1}{I }\geq 4^n$ ce qui donne $\mu \geq 4^n.$

Finalement, il a été montré le résultat suivant :

\boxed{\forall n\geq 1, \quad PPCM(1, \dots, 2n+1)\geq 4^n.}

Passez au cas général

Lorsque $n=1$, $PPCM(1, \dots, n) = PPCM(1) = 1.$ Or $1$ est bien supérieur ou égal à $\frac{1}{2} = \frac{2^1}{4}.$

Lorsque $n=2$, $PPCM(1, \dots, n) = PPCM(1, 2) = 2.$ Or $2$ est bien supérieur ou égal à $1 = \frac{2^2}{4}.$

Soit maintenant $n$ un entier naturel supérieur ou égal à $3.$

Cas où $n$ est impair

Comme $n-1$ est pair et supérieur ou égal à $2$, il existe un entier naturel $m\geq 1$ tel que $n-1 = 2m.$

Comme $PPCM(1, \dots, n) = PPCM(1,\dots,2m+1)$ il vient :

\begin{align*}
PPCM(1, \dots, n) &\geq 4^m \\
 &\geq (2^2)^m \\
&\geq  2^{2m}\\
&\geq 2^{n-1}\\
&\geq \frac{2^n}{2}\\
&\geq \frac{2^n}{4}.
\end{align*} 

Cas où $n$ est pair

Il s’agit de se ramener au cas impair.

Notez que $PPCM(1,\dots, n)$ est un multiple des $n-1$ entiers allant de $1$ jusqu’à $n-1.$

Comme $PPCM(1, \dots, n-1)$ est le plus petit multiple commun de ces $n-1$ entiers, vous déduisez :

PPCM(1, \dots, n) \geq PPCM(1, \dots, n-1).

Comme $n$ est pair et supérieur ou égal à $3$ il est même supérieur ou égal à $4.$

Donc $n-1$ est impair et il est supérieur ou égal à $3.$ Il existe un entier $m\geq 1$ tel que $n-1 = 2m+1.$ Comme $PPCM(1, \dots, n-1) = PPCM(1,\dots,2m+1)$ vous déduisez :

\begin{align*}
PPCM(1, \dots, n) &\geq PPCM(1, \dots, n-1)\\
&\geq PPCM(1, \dots, 2m+1)\\
&\geq 4^m\\
&\geq  2^{2m}\\
&\geq  2^{n-2}\\
&\geq \frac{2^n}{4}.
\end{align*} 

Concluez

Le résultat suivant est bien démontré :

\boxed{\forall n\geq 1, \quad PPCM(1,\dots,n) \geq \frac{2^n}{4}.}

347. Dénombrez le nombre de possibilités de choisir des entiers naturels dont la somme est connue

Soit $n$ un entier naturel non nul et $p$ un entier naturel. Il s’agit de déterminer le nombre exact de solutions de l’équation suivante, où toutes les inconnues sont des entiers naturels :

x_1+\dots+x_n=p.

Un exemple, pour $n=3$ et $p=4$

Vous cherchez tous les triplets possibles $(x_1,x_2,x_3)$ d’entiers naturels tels que :

x_1+x_2+x_3=4.

Vous allez traiter cette situation en envisageant toutes les possibilités pour l’inconnue $x_3.$

Cas où $x_3 = 4$

Dans ce cas, vous avez :

x_1+x_2 = 0.

Cela conduit immédiatement à $x_1=x_2=0.$

Il y a un triplet solution $(0,0,4).$

Cas où $x_3 = 3$

Dans ce cas, vous avez :

x_1+x_2 = 1.

Il y a deux possibilités, soit $x_1=1$ et $x_2=0$, soit $x_1=0$ et $x_2=1.$

Cela donne deux triplets $(1,0,3)$ et $(0,1,3).$

Cas où $x_3 = 2$

Dans ce cas, vous avez :

x_1+x_2 = 2.

Il y a trois possibilités, soit $x_1=2$ et $x_2=0$, soit $x_1=1$ et $x_2=1$, soit $x_1=0$ et $x_2=2.$

Cela donne trois triplets $(2,0,2)$, $(1,1,2)$ et $(0,2,2).$

Cas où $x_3 = 1$

Dans ce cas, vous avez :

x_1+x_2 = 3.

Il y a quatre possibilités, soit $x_1=3$ et $x_2=0$, soit $x_1=2$ et $x_2=1$, soit $x_1=1$ et $x_2=2$ et $x_1=0$ et $x_2=3.$

Cela donne quatre triplets $(3,0,1)$, $(2,1,1)$, $(1,2,1)$ et $(0,3,1).$

Cas où $x_3 = 0$

Dans ce cas, vous avez :

x_1+x_2 = 4.

Il y a cinq possibilités, soit $x_1=4$ et $x_2=0$, soit $x_1=3$ et $x_2=1$, soit $x_1=2$ et $x_2=2$ et $x_1=1$ et $x_2=3$, $x_1=0$ et $x_2=4.$

Cela donne cinq triplets $(4,0,0)$, $(3,1,0)$, $(2,2,0)$, $(1,3,1)$ et $(0,4,0).$

Concluez

Le nombre de solutions positives et entières de l’équation $x_1+x_2+x_3=4$ est égal à $15.$

ll serait intéressant de pouvoir généraliser. Aussi, vous allez traiter le cas où le nombre d’inconnues est égal à $n$ et où le résultat de la somme prend des petites valeurs.

Le nombre de solutions pour $n$ inconnues lorsque $p=0$

Il s’agit de résoudre $x_1+\dots+x_n=0$ où toutes les inconnues sont des entiers naturels. Du coup, toutes les inconnues sont nulles et il y a une seule solution, qui est le $n$-uplet suivant : $(0,\dots,0).$

Le nombre de solutions pour $n$ inconnues lorsque $p=1$

Il s’agit de résoudre $x_1+\dots+x_n=1$ où toutes les inconnues sont des entiers naturels.

Soit $(x_1,\dots,x_n)$ un $n$-uplet solution de cette équation.

Il est impossible que toutes les inconnues soient nulles. Du coup, au moins une d’entre elles notée $x_i$, avec $i$ compris entre $1$ et $n$ est supérieure ou égale à $1.$

Si $x_i\geq 2$, la somme $x_1+\dots+x_n$ est supérieure ou égale à $2$ ce qui contredit que $(x_1,\dots,x_n)$ est solution. Donc $x_i = 1.$ Il en résulte immédiatement que la somme $\sum_{j\neq i} x_j$ est nulle, donc toutes les autres inconnues sont nulles.

Il y a donc exactement $n$ solutions candidats possibles pour être solution.

Réciproquement, pour tout $i$ compris entre $1$ et $n$, considérons le $n$-uplet qui contient uniquement des zéros, sauf à la coordonnée numéro $i$ qui est égale à $1.$ La somme des coordonnées est bien égale à $1.$

Il y a donc en tout $n$ solutions.

Note. Pour $n=4$, les solutions seraient $(1,0,0,0)$, $(0,1,0,0)$, $(0,0,1,0)$ et $(0,0,0,1).$

Le nombre de solutions pour $n$ inconnues lorsque $p=2$

Il s’agit de résoudre $x_1+\dots+x_n=2$ où toutes les inconnues sont des entiers naturels.

Deux types de solutions sont possibles : les $n$-uplets dont l’une des coordonnées vaut $2$ et toutes les autres valent $0$. Il y en a exactement $n.$

Il y a aussi les $n$-uplets comportant deux coordonnées parmi $n$ égales à $1$, et les autres sont nulles, il y en a $\binom{n}{2} = \frac{n(n-1)}{2}.$

En définitive, le nombre de solutions est égal à :

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

Le nombre de solutions pour $n$ inconnues lorsque $p=3$

Il s’agit de résoudre $x_1+\dots+x_n=3$ où toutes les inconnues sont des entiers naturels.

Trois types de solutions sont possibles : les $n$-uplets dont l’une des coordonnées vaut $3$ et toutes les autres valent $0$. Il y en a exactement $n.$

Il y a aussi les $n$-uplets comportant une coordonnée égale à $1$, une autre égale à $2$ et les autres sont nulles, il y en a $n(n-1)$ d’après le principe du produit.

Il y a aussi les $n$-uplets comportant trois coordonnées égales à $1$ parmi $n$, les autres étant nulles, il y en a $\binom{n}{3} = \frac{n(n-1)(n-2)}{6}.$

En définitive, le nombre de solutions est égal à :

\begin{align*}
n+n(n-1)+\frac{n(n-1)(n-2)}{6} &= \frac{6n}{6}+\frac{6n(n-1)}{6}+\frac{n(n-1)(n-2)}{6} \\
&=\frac{6n+n(n-1)(6+n-2)}{6}\\
&=\frac{6n+n(n-1)(n+4)}{6}\\
&=\frac{n[6+(n-1)(n+4)]}{6}\\
&=\frac{n(6+n^2+3n-4)}{6}\\
&=\frac{n(n^2+3n+2)}{6}\\
&=\frac{n(n+1)(n+2)}{6}\\
&=\binom{n+2}{3}.
\end{align*}

Avant de passer au cas général, vous aurez besoin d’un lemme sur les coefficients binomiaux

Vous allez démontrer la propriété suivante :

\boxed{\forall (a,b)\in\N^2,\quad \sum_{k=0}^b \binom{a+k}{a} = \binom{a+b+1}{a+1}.}

Pour tout entier naturel $b$, vous notez $\mathscr{S}(b)$ la proposition suivante : « Pour tout entier naturel $a$, $\sum_{k=0}^b \binom{a+k}{a} = \binom{a+b+1}{a+1}.$ »

Initialisation. Pour $b=0.$

Soit $a$ un entier naturel.

D’une part, $\sum_{k=0}^0\binom{a+k}{a} = \binom{a}{a}=1.$

D’autre part, $\binom{a+0+1}{a+1} = \binom{a+1}{a+1} = 1.$

Du coup, $\mathscr{S}(0)$ est vérifiée.

Hérédité. Soit $b$ un entier naturel tel que $\mathscr{S}(b)$ soit vérifiée.

Soit $a$ un entier naturel. En séparant le dernier terme de la somme et en utilisant l’hypothèse de récurrence, il vient :

\begin{align*}
\sum_{k=0}^{b+1} \binom{a+k}{a} &= \sum_{k=0}^{b} \binom{a+k}{a} + \binom{a+b+1}{a}\\
&= \binom{a+b+1}{a+1}+ \binom{a+b+1}{a}.
\end{align*}

Or, d’après la relation de Pascal sur les coefficient binomiaux :

\binom{a+b+1}{a}+\binom{a+b+1}{a+1} = \binom{a+b+2}{a+1}.

Ainsi :

\sum_{k=0}^{b+1} \binom{a+k}{a} =  \binom{a+(b+1)+1}{a+1}.

La propriété $\mathscr{S}(b+1)$ est vérifiée.

Conclusion. Par récurrence, il a été démontré que pour tout entier naturel $b$, la propriété $\mathscr{S}(b)$ est vraie. Le résultat annoncé est bien démontré.

Passez au cas général

Bien que les dénombrements précédents aient été effectués avec des approches différentes, ils semblent tous converger vers un résultat qui va être démontré par récurrence, sur le nombre d’inconnues.

Pour tout entier naturel $n$ non nul, vous notez $\mathscr{P}(n)$ la proposition suivante : « Pour tout entier naturel $p$, le nombre de solutions positives et entières de l’équation $x_1+\dots+x_n = p$ est égal au coefficient binomial $\binom{n+p-1}{p}$. »

Initialisation. Pour $n=1.$ Soit $p$ un entier naturel. La résolution de l’équation à une inconnue positive entière $x_1=p$ possède une seule solution. Or, $\binom{1+p-1}{p} = \binom{p}{p}=1$ donc $\mathscr{P}(1)$ est vérifiée.

Hérédité. Soit $n$ un entier naturel tel que $\mathscr{P}(n)$ soit vérifiée.

Soit $p$ un entier naturel, vous cherchez le nombre de solutions positives et entières de l’équation $x_1+\dots+x_n+x_{n+1}=p.$

Lorsque $x_{n+1} = 0$, l’équation s’écrit $x_1+\dots+x_n=p$ elle possède $n$ variables positives et entières donc d’après l’hypothèse de récurrence, il y a $\binom{n+p-1}{p} = \binom{n+p-1}{n-1}$ solutions.

Plus généralement l’inconnue $x_{n+1}$ peut être égale à $k$, où $k\in\llbracket 0, p\rrbracket.$ l’équation à résoudre s’écrit $x_1+\dots+x_n=p-k$ et d’après l’hypothèse de récurrence, elle possède $\binom{n+p-k-1}{p-k} =\binom{n+p-k-1}{n-1}$ solutions.

D’après cette analyse, le nombre de solutions de l’équation $x_1+\dots+x_n+x_{n+1}=p$ est égal à la somme suivante :

\sum_{k=0}^p\binom{n+p-k-1}{n-1}.

En effectuant le changement d’indice $\ell = p-k$, vous obtenez :

\sum_{k=0}^p\binom{n+p-k-1}{n-1} = \sum_{\ell=0}^p\binom{n-1+\ell}{n-1}.

D’après le lemme, la somme $\sum_{\ell=0}^p\binom{n-1+\ell}{n-1}$ est égale au coefficient binomial $\binom{n+p}{n} = \binom{n+p}{p} = \binom{(n+1)+p-1}{p}.$

La propriété $\mathscr{P}(n+1)$ est vérifiée.

Conclusion. Par récurrence, il a été établi que pour tout entier naturel non nul $n$, $\mathscr{P}(n)$ est vérifiée.

Concluez

Pour tout entier naturel $n$ non nul et pour pour tout entier naturel $p$, le nombre de solutions positives et entières de l’équation $x_1+\dots+x_n = p$ est égal au coefficient binomial $\binom{n+p-1}{p}$.

Prolongements

Inéquation

Soit $n$ un entier naturel $n$ non nul et $p$ un entier naturel. Déterminez le nombre de solutions positives et entières de l’inéquation $x_1+\dots+x_n \leq p.$

Raccourci combinatoire

Pourriez-vous démontrer, en utilisant l’assertion « on obtient $n$ quantités à partir de $n-1$ piquets », que pour tout entier naturel $n$ non nul et pour pour tout entier naturel $p$, le nombre de solutions positives et entières de l’équation $x_1+\dots+x_n = p$ est égal au coefficient binomial $\binom{p+(n-1)}{n-1}$ ?

346. Un nombre est premier, si et seulement si, il divise tous les coefficients binomiaux de sa ligne dans le tableau de Pascal, excepté le premier et le dernier

Le but de cet article est de démontrer qu’un nombre entier $n\geq 2$ est premier, si et seulement si, pour tout entier $k$ compris entre $1$ et $n-1$, le coefficient binomial $\binom{n}{k}$ est divisible par $n.$

Visualisez le triangle de Pascal

Les premières lignes du tableau de Pascal sont les suivantes, à chaque fois est donnée la valeur du coefficient binomial $\binom{n}{k}.$

\begin{array}{|c|c|c|c|c|c|c|c|c|c|}
\hline
&k=0&k=1&k=2 & k=3 & k=4& k=5& k=6& k=7& k=8\\
\hline
n=0&1 & \\
\hline
n=1&1 & 1\\
\hline
n=2&1 & 2 & 1\\
\hline
n=3&1 & 3 & 3 & 1\\
\hline
n=4&1 & 4 & 6 & 4 & 1\\
\hline
n=5&1 & 5 & 10 & 10 & 5& 1\\
\hline
n=6&1 & 6 & 15 & 20 & 15& 6 & 1\\
\hline
n=7&1 & 7 & 21 & 35 & 35& 21 & 7 & 1\\
\hline
n=8&1 & 8 & 28 & 56 & 70& 56 & 28 & 8&1\\
\hline
\end{array}

En prenant un numéro de ligne qui est un nombre premier, par exemple lorsque $n=7$, vous constatez que les coefficients binomiaux $7$, $21$, $35$, $35$, $21$ et $7$ sont tous des multiples de $7.$ Autrement dit :

\forall k\in\llbracket 1, 6\rrbracket, \quad 7 \left| \binom{7}{k}\right..

Par contre, en prenant $n=6$ qui n’est pas un nombre premier, vous constatez, par exemple que $20$ n’est pas un multiple de $6$, ce qui s’écrit ainsi :

6 \not\left| \binom{6}{3}\right..

Autrement dit :

\exists k\in\llbracket 1, 5\rrbracket, \quad 6 \not\left| \binom{6}{k}\right..

Le premier sens comme conséquence du lemme d’Euclide

Soit $n$ un nombre entier supérieur ou égal à $2.$ Vous supposez que $n$ est un nombre premier.

Soit $k$ un nombre entier compris entre $1$ et $n-1.$ Le coefficient binomial $\binom{n}{k}$ se calcule avec une expression comportant des factorielles :

\binom{n}{k} = \frac{n!}{k! (n-k)!}.

Vous déduisez de ce qui précède que :

n! = k! (n-k)! \binom{n}{k}.

Comme $n! = n\times (n-1)!$ il s’ensuit que $n$ divise le produit $k! (n-k)! \binom{n}{k}.$

Supposez que $n$ ne divise pas le coefficient binomial $\binom{n}{k}.$ Comme $n$ est un nombre premier qui divise le produit des deux nombres $k! (n-k)!$ et $\binom{n}{k}$ le lemme d’Euclide (vous en trouverez une démonstration dans le contenu rédigé dans l'article 126) permet d’affirmer que $n$ divise $k! (n-k)!.$ Toujours d’après le même lemme d’Euclide, $n$ divise un des facteurs noté $i$ du produit $k! (n-k)!.$ Comme $k$ est compris entre $1$ et $n-1$, tous les facteurs du produit $k! (n-k)!$ sont des nombres entiers compris entre $1$ et $n-1.$ Il s’ensuit que $i$ lui-même est un entier compris entre $1$ et $n-1.$

Or, $n$ divise $i$ avec $i$ non nul impose d’avoir $n\leq i.$ Or il a été vu que $i \leq n-1$ ce qui aboutit à une contradiction.

Par l’absurde, il a été prouvé que $n$ divise le coefficient binomial $\binom{n}{k}.$

Ainsi, pour tout entier $n$ supérieur ou égal à $2$, l’implication ci-dessous est démontrée.

\boxed{n \text{ est premier }\implies \forall k\in\llbracket 1, n-1\rrbracket, \quad n \left| \binom{n}{k}\right..}

Le sens réciproque comme conséquence de la relation de Pascal et de l’arithmétique modulaire

Visualisez la situation lorsque $n=8$

Supposez que, pour $n=8$, vous ayez :

\forall k\in\llbracket 1, n-1\rrbracket, \quad n \left| \binom{n}{k}\right..

Vous raisonnez modulo $8$ et obtenez :

\forall k\in\llbracket 1, 7\rrbracket, \quad \binom{8}{k} \equiv 0 \mod 8.

En écrivant le triangle de Pascal modulo $8$ pour les lignes $n=7$ et $n=8$ il vient :

\begin{array}{|c|c|c|c|c|c|c|c|c|c|}
\hline
&k=0&k=1&k=2 & k=3 & k=4& k=5& k=6& k=7& k=8\\
\hline
n=7&1 &  &  &  & &  &  & \\
\hline
n=8&1 & 0 & 0 & 0 & 0& 0 & 0 & 0&1\\
\hline
\end{array}

Pour déterminer le résidu du coefficient binomial $\binom{7}{1}$ modulo $8$, vous utilisez la relation de Pascal :

\binom{7}{0}+\binom{7}{1} = \binom{8}{1}.

Ainsi :

\binom{7}{1} = \binom{8}{1} - \binom{7}{0}.

En raisonnant modulo $8$ cela donne :

\begin{align*}
\binom{7}{1} &\equiv  0 - 1 \mod 8\\
&\equiv  -1 \mod 8.
\end{align*}

En continuant ainsi, vous obtenez tous les résidus modulo $8$ de la ligne du triangle de Pascal pour $n=7$ et constatez une alternance de $1$ et de $-1.$

\begin{array}{|c|c|c|c|c|c|c|c|c|c|}
\hline
&k=0&k=1&k=2 & k=3 & k=4& k=5& k=6& k=7& k=8\\
\hline
n=7&1 & -1 & 1  & -1  &1 &-1  &1  &-1 \\
\hline
n=8&1 & 0 & 0 & 0 & 0& 0 & 0 & 0&1\\
\hline
\end{array}

Note. Vous ignorez le dernier résidu de la ligne pour $n=7$ qui est égal à $-1.$ En prenant une autre ligne, par exemple $n=9$, vous auriez trouvé à la ligne $n=8$ un résidu de $1$ et n’auriez pas pu conclure à une absurdité.

Comme $8$ n’est pas premier, il admet un diviseur propre, à savoir un nombre $d$ compris entre $2$ et $7$, tel que $d\mid 8.$

Vous vous intéressez au coefficient binomial $\binom{8}{d} = \binom{8}{2}$ et l’exprimez avec un coefficient binomial situé dans la ligne précédente du tableau de Pascal :

\begin{align*}
\binom{8}{2} &= \frac{8!}{2! 6!}\\
&=\frac{8 \times 7! }{2\times 1! 6!}\\
&=\frac{8}{2}\times \frac{7!}{1! 6!}\\
&= 4\times \binom{7}{1}.
\end{align*}

En prenant les résidus modulo $8$, vous obtenez :

\begin{align*}
\binom{8}{2} &\equiv 4\times (-1) \mod 8\\
&\equiv -4 \mod 8.
\end{align*}

Du coup, il vient :

0 \equiv-4 \mod 8.

Ceci est absurde.

Vous en déduisez qu’il est impossible que $8$ divise tous les coefficients binomiaux $\binom{8}{k}$ lorsque $k$ décrit l’intervalle d’entiers $\llbracket 1, 7\rrbracket.$

Traitez le cas général

Soit $n$ un entier supérieur ou égal à $2$, tel que :

\forall k\in\llbracket 1, n-1\rrbracket, \quad n \left| \binom{n}{k}\right..

Si $n = 2$, le nombre $n$ est un nombre premier et le résultat est démontré.

Supposez maintenant que $n\geq 3.$

Alors :

\forall k\in\llbracket 1, n-1\rrbracket, \quad \binom{n}{k} \equiv 0 \mod n.

Vous allez maintenant effectuer une récurrence limitée afin de déterminer les résidus modulo $n$ des coefficients binomiaux $\binom{n-1}{k}$ lorsque $k$ décrit l’intervalle $\llbracket 0, n-1\rrbracket.$

Pour tout entier $k\in \llbracket 0, n-1\rrbracket$ vous notez $\mathscr{P}(k)$ la propriété : « le résidu modulo $n$ du coefficient binomial $\binom{n-1}{k}$ est égal à $(-1)^k$ ».

Initialisation. Pour $k=0$, vous avez d’une part $(-1)^k = (-1)^0 = 1.$

D’autre part, $\binom{n-1}{0} = 1$ donc $\binom{n-1}{0} = (-1)^0$ ce qui donne :

\binom{n-1}{0} \equiv (-1)^0 \mod n.

La propriété $\mathscr{P}(0)$ est vérifiée.

Hérédité. Soit $k$ un entier naturel inférieur ou égal à $n-2$ tel que $\mathscr{P}(k)$ soit vérifiée.

Vous avez déjà :

\binom{n-1}{k} \equiv (-1)^k \mod n.

D’après la relation de Pascal :

\binom{n-1}{k} + \binom{n-1}{k+1} = \binom{n}{k+1}.
 \binom{n-1}{k+1} = \binom{n}{k+1} - \binom{n-1}{k}.

Comme $k+1$ est un entier supérieur ou égal à $1$ et inférieur ou égal à $n-1$, vous avez :

\binom{n}{k+1} \equiv 0 \mod n.

Du coup :

\begin{align*}
 \binom{n-1}{k+1} &\equiv 0 - (-1)^k \mod n \\
&\equiv  (-1)^{k+1} \mod n.
\end{align*}

Donc la propriété $\mathscr{P}(k+1)$ est vérifiée.

Conclusion. Par récurrence limitée, il a été établi que :

\forall k\in\llbracket 0, n-1\rrbracket, \quad\binom{n-1}{k} \equiv (-1)^k \mod n.

Supposez que $n$ ne soit pas un nombre premier.

Il existe deux diviseurs propres $d$ et $d’$ c’est-à-dire deux entiers compris entre $2$ et $n-1$ tels que $n = dd’.$

Vous exprimez le coefficient binomial $\binom{n}{d}$ de la façon suivante :

\begin{align*}
\binom{n}{d} &= \frac{n! }{d! (n-d!)}\\
&= \frac{n}{d}\times \frac{(n-1)!}{(d-1)! (n-d)!}\\
&=d' \times \binom{n-1}{d-1}.
\end{align*}

Maintenant, modulo $n$, vous avez :

\begin{align*}
0 &\equiv \binom{n}{d} \mod n\\
&\equiv d' \times \binom{n-1}{d-1} \mod n.
\end{align*}

Comme $d-1$ est compris entre $0$ et $n-1$, vous déduisez :

\binom{n-1}{d-1} \equiv (-1)^{d-1}\mod n.

Du coup :

0\equiv d'\times (-1)^{d-1}\mod n.

En multipliant ce résultat par $(-1)^{d-1}$ vous aboutissez à :

0\equiv d' \mod n.

Il en résulte que $n$ divise $d’$ qui est non nul, donc $n\leq d’ \leq n-1$ ce qui est absurde.

Donc $n$ est un nombre premier.

Ainsi, pour tout entier $n$ supérieur ou égal à $2$, l’implication ci-dessous est démontrée.

\boxed{n \text{ est premier }\impliedby \forall k\in\llbracket 1, n-1\rrbracket, \quad n \left| \binom{n}{k}\right..}

Concluez

Il a été démontré l’équivalence suivante :

\boxed{\forall n\geq 2, n \text{ est premier }\Longleftrightarrow \forall k\in\llbracket 1, n-1\rrbracket, \quad n \left| \binom{n}{k}\right..}

Prolongement

Pourriez-vous utiliser le résultat établi pour démontrer qu’un nombre entier $n\geq 2$ est premier, si et seulement si, pour tout entier $a$ premier avec $n$, $(X+a)^n\equiv X^n+a \mod n$ ?

345. Calculez les carrés d’un nombre comportant deux, trois chiffres ou plus

Des techniques efficaces permettent de calculer rapidement des carrés sans avoir recours à une calculatrice, en exploitant la structure des nombres pour simplifier les opérations.

Principe

Quels que soient les entiers $a$ et $b$, le développement de l’identité remarquable $(10a+b)^2$ fournit :

\begin{align*}
(10a+b)^2 &= 100a^2+20ab+b^2\\
&=100a^2+10\times (2ab)+b^2\\
&= (100a^2+b^2) + 10\times (2ab).
\end{align*}

Déterminez les carrés de nombres à deux chiffres

Exemple : calculez le carré de $37$

Lorsque $a = 3$ et $b=7$, vous obtenez $2ab = 42$ puis :

37^2 = (100\times 9 + 49) + 10\times 42 .

Cela peut fournit :

\begin{align*}
37^2&= 949 + 420.
\end{align*} 

Le nombre $949$ s’obtient en collant $3^2$ et $7^2$ qui sont des deux chiffres du nombre de départ.

Le $42$ s’obtient en multipliant $3\times 7$ puis en doublant par $2.$

Ce mécanisme peut être automatisé de la façon suivante, en écrivant :

\boxed{37^2 = 0 \overset{\scriptstyle 4}{9} \overset{\scriptstyle 2}{4} 9 = 1369.}

Exemple : calculez le carré de $67$

Vous calculez d’abord le produit $6\times 7$ puis vous doublez, ce qui fournit $6\times 7 = 42$ puis $42\times 2 = 84.$

Vous collez les résultats de $6^2$ et de $7^2$ ce qui fournit :

\boxed{67^2 = 3 \overset{\scriptstyle 8}{6} \overset{\scriptstyle 4}{4} 9 = 4489.}

Déterminez les carrés de nombres à trois chiffres

Exemple : calculez le carré de $678$

Vous calculez d’abord le carré de $67.$ Cela a été effectué précédemment. Il vient $67^2 =4489.$

Puis vous collez à ce nombre le carré du chiffres des unités de $678$ soit $8^2=64.$

Il reste à calculer $8\times 67 \times 2.$ Cette fois vous utilisez :

\begin{align*}
8\times 67\times 2 &= 8\times 134\\
&=1072.
\end{align*}

Il en résulte que :

\boxed{678^2 = 4 \overset{\scriptstyle 1}{4} \overset{\scriptstyle 0}{8} \overset{\scriptstyle 7}{9} \overset{\scriptstyle 2}{6}4=45\overset{\scriptstyle 1}{8} 684 = 459684.}

Exemple : calculez le carré de $348$

Vous calculez d’abord le carré de $34.$

Les opérations mentales sont les suivantes :

\begin{align*}
3^2 &= 09\\
4^2 &= 16\\
3\times 4\times 2 &= 24.
\end{align*}

Du coup :

\boxed{34^2 = 0 \overset{\scriptstyle 2}{9} \overset{\scriptstyle 4}{1} 6 = 1156.}

Pour le carré de $348$ les opérations deviennent :

\begin{align*}
34^2 &= 1156\\
8^2 &= 64\\
34\times 8\times 2 &= 272\times 2 = 544.
\end{align*}

Par conséquent :

\boxed{348^2 = 11\overset{\scriptstyle 5}{5} \overset{\scriptstyle 4}{6} \overset{\scriptstyle 4}{6} 4 = 1\overset{\scriptstyle 1}{1}\overset{\scriptstyle 1}{0}\overset{\scriptstyle 1}{0}04 = 121104.}

Pour aller plus loin

Soit à calculer le carré de $3482.$

Les opérations mentales sont les suivantes :

\begin{align*}
348^2 &= 121104\\
2^2 &= 04\\
348\times 2\times 2 &= 696 \times 2 = 1392.
\end{align*}

En définitive :

\boxed{3482^2 = 121\overset{\scriptstyle 1}{1}\overset{\scriptstyle 3}{0}\overset{\scriptstyle 9}{4}\overset{\scriptstyle 2}{0}4= 1212\overset{\scriptstyle 1}{3}324=12124324.}