Auteur/autrice : Yannis TRIANTAPHYLIDES

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}$ ?

Dans cet article, les notions d’anneaux et d’ensemble-quotient ne seront pas abordées. L’approche choisie consiste à démontrer le résultat de l’indicatrice d’Euler en travaillant principalement dans l’ensemble $\Z$ des entiers relatifs.

Notations

Pour tout entier naturel $a$ et tout entier naturel $n$ non nul, la notation $(a \mod n)$ désignera le reste de la division euclidienne de $a$ par $n.$

Pour tout entier naturel $n$ non nul, vous notez $\varphi(n)$ le nombre d’éléments de l’ensemble :

U_n = \{k\in\Z, \mathrm{PGCD}(k,n)=1\text{ et } 0\leq k\leq n-1\}.

Il s’agit de démontrer que si $m$ et $n$ sont deux entiers naturels non nuls tels que $\mathrm{PGCD}(m,n)=1$, alors :

\varphi(mn)=\varphi(m)\varphi(n).

Dans toute la suite de cet article, vous fixez deux entiers $m$ et $n$ non nuls fixés, tels que $\mathrm{PGCD}(m,n)=1.$

Construisez une application de l’ensemble $U_{mn}$ vers le produit $U_m\times U_n$

Soit $x$ un élément de $U_{mn}.$

Pour être certain d’obtenir un entier de l’ensemble $U_m$ et un entier de l’ensemble $U_n$ vous effectuez la division euclidienne de $x$ par $m$ et $n$ respectivement. Il existe quatre entiers uniques $q_n, r_n, q_m, r_m$ avec $0\leq r_n\leq n-1$ et $0\leq r_m\leq m-1$ tels que :

\left\{\begin{align*}
x&=q_m m+r_m\\
x&=q_n n+r_n.
\end{align*}
\right.

Il s’agit maintenant de comprendre pourquoi le couple $(r_m,r_n)$ est un élément de l’ensemble $U_m\times U_n.$

Notez $d = \mathrm{PGCD}(r_m,m).$ Comme $d$ divise $m$, $d$ divise le produit $q_m m.$ Comme $d$ divise aussi $r_m$, il divise la somme $q_m m + r_m.$ Par suite, $d$ divise $x.$

Comme $d$ divise $m$ et que $m$ divise le produit $mn$ vous déduisez que $d$ divise $mn.$ Comme $d$ divise $mn$ et $x$, c’est un diviseur commun à $x$ et à $mn.$ Or, $x\in U_{mn}$ donc $ \mathrm{PGCD}(x,mn) = 1.$ Il en résulte que $d=1.$

Il est ainsi démontré que $\mathrm{PGCD}(r_m,m) = 1.$ Vu que $0\leq r_m\leq m-1$ vous déduisez $\boxed{r_m\in U_m.}$

Un raisonnement identique permet d’aboutir à la conclusion $\boxed{r_n\in U_n.}$

Par le procédé décrit ci-dessus, vous avez défini une application $f$ qui va de $U_{mn}$ dans $U_m\times U_n.$ Elle est définie, pour tout entier $k\in U_{mn}$ par :

f(k) = ((k\mod m) , (k\mod n)).

Démontrez l’injectivité de cette application

Soient $x$ et $y$ deux éléments de $U_{mn}$ tels que $f(x) = f(y).$

Alors :

\begin{align*}
(x\mod m) &= (y\mod m)\\
(x\mod n) &= (y\mod n).
\end{align*}

Quand vous effectuez la division euclidienne de $x$ par $m$, puis celle de $y$ par $m$, vous constatez qu’il existe un couple $(q_n,q_m)$ d’entiers tel que :

x = q_x m+(x\mod m)\\
y = q_y m + (y\mod m).

Comme $(x\mod m) = (y\mod m)$ par soustraction, vous déduisez :

x-y = q_xm-q_ym = m(q_x-q_y).

Ainsi l’entier $m$ divise la différence $x-y.$

En suivant un raisonnement similaire pour $n$, vous aboutissez au fait que $n$ divise aussi la différence $x-y.$

D’après ces constats, il existe deux entiers $m’$ et $n’$ tels que :

\begin{align*}
x-y &= mm'\\
x-y&=nn'.
\end{align*}

Vous déduisez $mm’ = nn’$ puis $n \mid mm’.$ Comme $\mathrm{PGCD}(m,n)=1$ le théorème de Gauss fournit $n \mid m’.$ Donc il existe un entier $k$ tel que $m’ = kn.$

L’égalité $x-y = mm’$ devient $x-y = mkn$ si bien que le produit $mn$ divise $x-y.$

Vous allez supposer que $k$ n’est pas nul, ce qui implique $\vert k \vert \geq 1.$

Du coup, $\vert x-y \vert = \vert k \vert \times mn$ d’où $\vert x-y\vert \geq mn.$

Or, $x$ et $y$ sont deux éléments de $U_{mn}$ donc $0\leq x \leq mn -1$ et $0\leq y \leq mn-1.$

Par suite, $1-mn\leq -y \leq 0$ et par somme avec $0\leq x\leq mn-1$ il vient $1-mn \leq x-y \leq mn-1.$

Cette double inégalité fournit $\vert x-y \vert \leq mn-1.$ Or, $mn\leq \vert x-y\vert$ du coup $mn\leq mn-1$ ce qui est une contradiction.

Ainsi, $k=0$ et $x-y=0$ et $x=y.$ L’injectivité de la fonction $f$ est ainsi démontrée.

Démontrez la surjectivité de cette application

Soit $(u,v)$ un couple de l’ensemble $U_m\times U_n.$

Grâce au théorème chinois dont une preuve se trouve dans le contenu rédigé dans l'article 309, il existe un entier $x$ tel que :

\left\{\begin{align*}
x&\equiv u\text{ modulo }m\\
x&\equiv v\text{ modulo }n.
\end{align*}
\right.

Sans utiliser le symbôle de la congruence, cela signifie qu’il existe un entier $r$ et un entier $s$ tels que :

\left\{\begin{align*}
x = u +rm\\
x = v+ sn.
\end{align*}
\right.

A priori, on n’est pas sûr que $x$ soit compris entre $0$ et $mn-1.$

Vous allez considérer $y = x\mod mn$, le reste de la division de $x$ par le produit $mn.$

Il existe un entier $q$ tel que $x = qmn + y$ et l’inégalité $0\leq y \leq mn-1$ est vérifiée.

D’une part :

\begin{align*}
y &= x-qmn\\
&=u+rm-qmn\\
&=(r-qn)m+u.
\end{align*}

Comme $r-qn$ est un entier et que $u$ est compris entre $0$ et $m-1$, l’entier $u$ est de reste de la division de $y$ par $m$, donc $u = (y\mod m).$

D’autre part :

\begin{align*}
y &= x-qmn\\
&=v+sn-qmn\\
&=(s-qm)n+v.
\end{align*}

Comme $s-qm$ est un entier et que $v$ est compris entre $0$ et $n-1$, l’entier $v$ est de reste de la division de $y$ par $n$, donc $v = (y\mod n).$

Notez maintenant $d$ le plus grand diviseur commun des entiers $y$ et $m.$

Comme $d\mid m$ il vient $d\mid qmn.$ Or, $x = y+qmn$ donc $d\mid x.$ Comme $\mathrm{PGCD}(x,m)=1$ et que $d$ est un diviseur commun à $x$ et à $m$, vous déduisez $d = 1$ et par suite $\mathrm{PGCD}(y,m)=1.$

Notez maintenant $f$ le plus grand diviseur commun des entiers $y$ et $n.$

Comme $f\mid n$ il vient $f\mid qmn.$ Or, $x = y+qmn$ donc $f\mid x.$ Comme $\mathrm{PGCD}(x,m)=1$ et que $f$ est un diviseur commun à $x$ et à $m$, vous déduisez $f = 1$ et par suite $\mathrm{PGCD}(y,n)=1.$

Il s’agit de comprendre maintenant pourquoi $\mathrm{PGCD}(y,mn)=1.$ Si tel n’est pas le cas, $\mathrm{PGCD}(y,mn)\geq 2$ et il existe un nombre premier $p$ tel que $p$ divise $\mathrm{PGCD}(y,mn).$ Comme $\mathrm{PGCD}(y,mn)$ divise $mn$ vous déduisez que $p$ divise $mn.$

Par le lemme d’Euclide, soit $p$ divise $m$, soit $p$ divise $n.$
Supposez que $p$ divise $m$ alors $p$ divisant $\mathrm{PGCD}(y,mn)$ qui divise $y$, vous déduisez $p\mid y.$ Du coup $p$ est un diviseur commun à $y$ et à $m.$ Comme $\mathrm{PGCD}(y,m)=1$ vous déduisez $p\leq 1$ ce qui est impossible, puisque $p$ en tant que nombre premier est supérieur ou égal à $2.$
Supposez que $p$ divise $n.$ Alors le raisonnement est similaire. En effet, vous trouvez $p\mid y$ et $p\mid n.$ Comme $\mathrm{PGCD}(y,n)=1$ cela entraîne $p\leq 1$ ce qui est impossible.

Du coup $\mathrm{PGCD}(y,mn)=1$ avec $0\leq y \leq mn-1.$ Donc $y$ est un élément de $U_{mn}.$

Il vient alors :

\begin{align*}
f(y) &= ((y\mod m), (y\mod n))\\
&= (u,v).
\end{align*}

La surjectivité de $f$ est ainsi démontrée.

Concluez

L’application $f$ est une bijection de $U_{mn}$ dans $U_m\times U_n.$

Les ensembles de départ et d’arrivée de $f$ ont donc le même nombre d’éléments, ce qui fournit le résultat :

\varphi(mn)=\varphi(m)\times \varphi(n).

Dans cet article, vous notez $\mathscr{P}$ l’ensemble des nombres premiers.

Un nombre $p$ sera qualifié de premier, si et seulement si, il est entier et supérieur ou égal à $2$ et si, quels que soient les entiers naturels $a$ et $b$ non nuls :

\boxed{p = ab \implies \left(\left\{\begin{align*}a&=1\\ b&=p\end{align*}\right. \quad \text{ ou }\quad  \left\{\begin{align*}a&=p\\ b&=1.\end{align*}\right.\right)}

Un nombre entier supérieur ou égal à $2$ qui n’est pas premier sera qualifié de nombre composé.

Caractérisez un nombre entier composé

Soit $n$ un nombre entier supérieur ou égal à $2.$ Supposez que $n$ ne soit pas premier. Alors il existe deux entiers naturels $a$ et $b$ non nuls tels que $p=ab$ et ils vérifient ce qui suit :

(*):\left\{\begin{align*}
a&\neq 1 \text{ ou } b\neq n\\
a&\neq n \text{ ou } b\neq 1.
\end{align*}\right.

Si $a=1$, alors $b\neq n$ d’après la première ligne de $(*).$ Or, la condition $n=ab$ devient $n=b$ ce qui amène à une contradiction. Donc $a\geq 2.$

Si $a=n$, alors $b\neq 1$ d’après la deuxième ligne de $(*).$ Or, la condition $n=ab$ devient $n=nb$ et comme $n\neq 0$ vous déduisez $b=1$ ce qui amène à une contradiction.

Si $a>n$, alors en multipliant par $b$ qui est strictement positif, il vient $ab>nb$ et la condition $n=ab$ fournit $n>nb$ et en divisant par $n>0$ il vient $1>b$ ce qui contredit le fait que $b$ et un entier naturel non nul.

Vous déduisez de cette analyse que $2\leq a \leq n-1.$

Le raisonnement est strictement identique pour $b.$

Il est ainsi établi que, pour tout nombre naturel $n$ supérieur ou égal à $2$, si $n$ n’est pas premier, alors il existe deux entiers $a$ et $b$ tels que :

\left\{\begin{align*}
&n=ab\\
&2\leq a \leq n-1\\
&2\leq b \leq n-1.
\end{align*}\right.

Réciproquement, soit $n$ un nombre entier supérieur ou égal à $2$ tel qu’il existe deux entiers $a$ et $b$ vérifiant les conditions suivantes :

(**): \left\{\begin{align*}
&n=ab\\
&2\leq a \leq n-1\\
&2\leq b \leq n-1.
\end{align*}\right.

Si $n$ était premier, alors soit $a$ serait égal à $1$, ce qui contredit la deuxième ligne de $(**)$ soit $a$ serait égal à $n$, ce qui contredit encore la deuxième ligne de $(**).$

La caractérisation est ainsi établie.

Pour tout nombre naturel $n$ supérieur ou égal à $2$, $n$ n’est pas premier, si et seulement si, il existe deux entiers $a$ et $b$ tels que :

\boxed{\left\{\begin{align*}
&n=ab\\
&2\leq a \leq n-1\\
&2\leq b \leq n-1.
\end{align*}\right.}

Le lemme d’Euclide à partir du raisonnement par l’absurde

Vous cherchez à démontrer le lemme d’Euclide qui stipule que quel que soit le nombre premier $p$ et quels que soient les entiers naturels non nuls $a$ et $b$, si $p$ divise le produit $ab$, alors $p$ divise $a$ ou $p$ divise $b.$

Les deux arguments de minimalité

Vous supposez que le lemme d’Euclide n’est pas vérifié.

Vous en concluez qu’il existe un nombre $p_0$ premier et ainsi que deux entiers naturels non nuls $a_0$ et $b_0$ tels que :

\left\{\begin{align*}
&p_0 \mid a_0b_0\\
&p_0 \nmid a_0\\
&p_0 \nmid b_0.
\end{align*} 
\right.

Vous introduisez alors l’ensemble suivant afin d’utiliser un premier argument de minimalité :

\boxed{A = \{u\in\mathscr{P}, \exists(a,b)\in(\NN)^2, u\mid ab \text{ et }u\nmid a \text{ et }u\nmid b\}.}

Comme $p_0\in A$, l’ensemble $A$ est non vide.

Les inclusions $A\subset \mathscr{P} \subset \N$ montrent que $A$ est une partie non vide de $\N.$ Elle admet donc un plus petit élément que vous notez $p.$

Par définition de $p$ vous avez $p\in A.$ De plus, $p$ est un nombre premier et il existe deux entiers naturels non nuls $a$ et $b$ tels que :

\left\{\begin{align*}
&p \mid ab\\
&p \nmid a\\
&p \nmid b.
\end{align*} 
\right.

Vous effectuez la division euclidienne de $a$ par $p.$ Il existe un quotient $q_a\in\N$ et un reste $r_a\in\N$ avec $0\leq r_a\leq p-1$ tels que $a = q_a p + r_a.$

Notez que si $r_a = 0$ alors $a = q_a p$ donc $p\mid a$ ce qui est absurde. Donc :

1\leq r_a\leq p-1.

De même, vous effectuez la division euclidienne de $b$ par $p.$ Il existe un quotient $q_b\in\N$ et un reste $r_b\in\N$ avec $0\leq r_b\leq p-1$ tels que $b = q_b p + r_b.$

Notez que si $r_b = 0$ alors $b = q_b p$ donc $p\mid b$ ce qui est absurde. Donc :

1\leq r_b\leq p-1.

Vous calculez maintenant le produit $ab$ ce qui fournit :

\begin{align*}
ab &= ( q_a p + r_a)( q_b p + r_b)\\
&=( q_a p + r_a) q_b p + ( q_a p + r_a) r_b\\
&=( q_a q_b p + r_a q_b)  p +  q_a r_b p + r_a r_b\\
&=( q_a q_b p + r_a q_b+  q_a r_b)  p   + r_a r_b.
\end{align*}

Ainsi :

   r_a r_b = ab -( q_a q_b p + r_a q_b+  q_a r_b)  p.

Or, $p$ divise $ab.$

Comme $p$ divise le produit $( q_a q_b p + r_a q_b+ q_a r_b) p$ vous concluez par différence que :

p\mid r_ar_b.

Vous posez $r = r_a+r_b$ et définissez l’ensemble $B$ suivant pour préparer le second argument de minimalité :

\boxed{B=\{u\in\N, \exists(h,k)\in \llbracket 1, p-1\rrbracket ^2, u=h+k \text{ et } p\mid hk\}.}

D’après ce qui précède, $r\in B.$

L’ensemble $B$ est une partie non vide de $\N$ elle admet donc un plus petit élément que vous notez $s.$

Aboutissez à une contradiction

Par définition de l’entier $s$, il existe deux entiers $h$ et $k$, compris entre $1$ et $p-1$ tels que $s = h+k$ et $p\mid hk.$

Comme les nombres $p$ puis $h$ et $k$ sont des entiers naturels non nuls, il existe un entier naturel $q$ non nul tel que :

hk = pq.

Si $q$ est égal à $1$, alors $hk = pq$ s’écrit $hk = p.$ Comme $h$ et $k$ sont des entiers naturels non nuls et que $p$ est premier, cela entraîne :

\left\{\begin{align*}h&=1\\ k&=p\end{align*}\right. \text{ ou } \left\{\begin{align*}h&=p\\ k&=1.\end{align*}\right.

Dans le premier cas, $k = p$ c’est absurde puisque $k \leq p-1.$ Dans le second cas, $h = p$ mais c’est encore absurde puisque $h \leq p-1.$

Vous en déduisez que $q\geq 2.$

Comme $1\leq h < p$ et comme $1\leq k < p$ par produit il vient $1\leq hk < p^2.$ Comme $hk = pq$ il vient $pq < p^2.$ En divisant par $p$ qui est strictement positif vous déduisez $q<p.$

L’entier $q$ vérifie l’encadrement suivant : $2\leq q \leq p-1.$

Or, tout entier naturel supérieur ou égal à $2$ est divisible par un nombre premier.

Soit $p’\in\mathscr{P}$ tel que $p’ \mid q.$ Comme $q\mid pq$ et comme $hk = pq$ vient $q\mid hk.$ Finalement, vous avez $p’\mid q \mid hk.$

Donc $p’$ est un nombre premier divisant le produit $hk$ avec $h$ et $k$ entiers naturels non nuls. Comme $p’\leq q \leq p-1$ vous avez $p'<p.$ Or $p$ est le plus petit élément de $A$ du coup $p’\notin A.$ Il en résulte que, soit $p’ \mid h$ soit $p’\mid k.$

Supposez que $p’\mid h.$ $h$ étant non nul, il existe un entier naturel non nul $h’$ tel que $h = p’h’.$
Comme $p’\mid q$ et que $q$ est non nul, il existe un entier naturel non nul $q’$ tel que $q = p’q’.$

L’égalité $hk = pq$ s’écrit $p’h’k = pp’q’.$ Comme $p’$ est non nul, il vient $h’k = pq’$ du coup $p\mid h’k.$

Vous posez maintenant $s’ = h’+k.$ L’égalité $h=p’h’$ avec $p’\geq 2$ entraîne $h'<h.$ Or $h\leq p-1$ donc $1\leq h’\leq p-1.$
Comme vous avez déjà $k\in\llbracket 1, p-1\rrbracket$ vous déduisez que $s’\in B.$

Le second argument de minimalité est utilisé ici. $s$ est le minimum de $B$ donc $s\leq s’$ si bien que $h+k\leq h’+k$ d’où $h\leq h’.$ Cela est contradictoire avec $h'<h.$

Il en résulte $p’\mid k.$ $k$ étant non nul, il existe un entier naturel non nul $k’$ tel que $k = p’k’.$
Comme $p’\mid q$ et que $q$ est non nul, il existe un entier naturel non nul $q’$ tel que $q = p’q’.$

L’égalité $hk = pq$ s’écrit $hp’k’ = pp’q’.$ Comme $p’$ est non nul, il vient $hk’ = pq’$ du coup $p\mid hk’.$

Vous posez maintenant $s » = h+k’.$ L’égalité $k=p’k’$ avec $p’\geq 2$ entraîne $k'<k.$ Or $k\leq p-1$ donc $1\leq k’\leq p-1.$
Comme vous avez déjà $h\in\llbracket 1, p-1\rrbracket$ vous déduisez que $s »\in B.$

Le second argument de minimalité est encore utilisé ici. $s$ est le minimum de $B$ donc $s\leq s »$ si bien que $h+k\leq h+k’$ d’où $k\leq k’.$ Cela est contradictoire avec $k'<k.$

L’hypothèse de départ est ainsi fausse, ce qui prouve que le lemme d’Euclide est démontré.

Il s’agit de démontrer dans cet article l’identité suivante :

\boxed{\tan 9°−\tan27°−\tan 63°+\tan 81°=4.}

Utilisant la symétrie par rapport à $45°$, vous constatez que $63° = 45°+18°$ et que $27° = 45°-18°.$

Vous posez, pour l’intégralité de cet article, $x=\frac{\pi}{10}.$
C’est le réel qui mesure en radians un angle de $18°.$ Vous effectuez le calcul d’une première somme.

Calculez la somme $\tan 27°+\tan 63°$

\begin{align*}
\tan 27°+\tan63° &= \tan\left(\frac{\pi}{4}-x\right)+\tan\left(\frac{\pi}{4}+x\right)\\
&=\frac{ \tan\left(\frac{\pi}{4}\right) - \tan\left(x\right) }{1+\tan\left(\frac{\pi}{4}\right) \tan\left(x\right) } + \frac{ \tan\left(\frac{\pi}{4}\right) + \tan\left(x\right) }{1-\tan\left(\frac{\pi}{4}\right) \tan\left(x\right) }.
\end{align*}

Utilisant l’égalité $\tan\left(\frac{\pi}{4}\right) = 1$ vous obtenez :

\begin{align*}
\tan 27°+\tan 63° 
&=\frac{ 1 - \tan\left(x\right) }{1+ \tan\left(x\right) } + \frac{ 1 + \tan\left(x\right) }{1- \tan\left(x\right) } \\
&=\frac{(1-\tan x)^2+(1+\tan x)^2}{1-\tan^2 x}\\
&=\frac{1-2\tan x + \tan^2 x+1+2\tan x+\tan^2x}{1-\tan^2 x}\\
&=\frac{2 + 2\tan^2 x}{1-\tan^2 x}\\
&=\frac{2( 1+ \tan^2 x) }{1-\tan^2 x}.
\end{align*}

Calculez la somme $\tan 9°+\tan 81°$

Comme précédemment, utilisez la symétrie autour de $45°$.
Partant de $81° = 45° + 2\times 18°$ et de $81° = 45° + 2\times 18°$ vous obtenez :

\begin{align*}
\tan 9°+\tan 81° &= \tan\left(\frac{\pi}{4}-2x\right)+\tan\left(\frac{\pi}{4}+2x\right)\\
&=\frac{ \tan\left(\frac{\pi}{4}\right) - \tan\left(2x\right) }{1+\tan\left(\frac{\pi}{4}\right) \tan\left(2x\right) } + \frac{ \tan\left(\frac{\pi}{4}\right) + \tan\left(2x\right) }{1-\tan\left(\frac{\pi}{4}\right) \tan\left(2x\right) }\\
 &=\frac{ 1 - \tan\left(2x\right) }{1+ \tan\left(2x\right) } + \frac{ 1 + \tan\left(2x\right) }{1- \tan\left(2x\right) } \\
&= \frac{2(1 + \tan^2 (2x)) }{1-\tan^2 (2x)}.
\end{align*}

Exprimez $\frac{ 1+ \tan^2 u}{1-\tan^2 u}$ en fonction de $\cos (2u)$

Soit $u\in\{x, 2x\}.$ Vous utilisez les égalités $1+\tan^2 u = \frac{1}{\cos ^2 u}$ et $\cos^2 u = \frac{1+\cos 2u}{2}$ et obtenez ce qui suit :

\begin{align*}
\tan^2 u &= (1+\tan^2 u) -1\\
&=\frac{1}{\cos^2 u}-1\\
&=\frac{1}{\frac{1+\cos (2u)}{2}}-1\\
&=\frac{2}{1+\cos 2u}-1.
\end{align*}

Par suite :

\begin{align*}
1-\tan^2u &= 1-\frac{2}{1+\cos 2u}+1\\
&=2-\frac{2}{1+\cos 2u}\\
&=\frac{2+2\cos 2u-2}{1+\cos 2u}\\
&=\frac{2\cos 2u}{1+\cos 2u}.
\end{align*}

Vous déduisez :

\begin{align*}
\frac{ 1+ \tan^2 u}{1-\tan^2 u} &= \frac{\frac{1}{\cos^2 u}}{\frac{2\cos 2u}{1+\cos 2u}}\\
&=\frac{1+\cos 2u}{2\cos 2u \cos^2u}\\
&=\frac{1+\cos 2u}{2\cos 2u\times \frac{1+\cos 2u}{2}}\\
&=\frac{1+\cos 2u}{\cos 2u(1+\cos 2u) }\\
&=\frac{1}{\cos 2u}.
\end{align*}

Note. Il y a des moyens plus rapides d’aboutir à ce résultat, le lecteur est invité à proposer une autre solution.

Concluez

D’après ce qui précède :

\begin{align*}
\tan 9°−\tan 27° −\tan 63°+\tan 81° &= (\tan 9°+\tan81°)-(\tan 27°+\tan 63°)\\
&=\frac{2 }{\cos 4 x}-\frac{2}{\cos 2x}\\
&=\frac{2 }{\cos 72°}-\frac{2}{\cos 36°}\\
\end{align*}

Or, le contenu rédigé dans l'article 106 a permis de montrer que :

\left\{\begin{align*}
\cos 72° &= \frac{-1+\sqrt{5}}{4}\\
\cos 36° &= \frac{1+\sqrt{5}}{4}.
\end{align*} 
\right.

Vous finissez ainsi le calcul comme suit :

\begin{align*}
\tan 9°−\tan 27° −\tan 63°+\tan 81° &= \frac{8}{\sqrt{5}-1}-\frac{8}{\sqrt{5}+1}\\
&=\frac{8\sqrt{5}+8-8\sqrt{5}+8}{(\sqrt{5}-1)(\sqrt{5}+1) }\\
&=\frac{16}{5-1}\\
&=4.
\end{align*}

En définitive, il a bien été montré que :

\boxed{\tan 9°−\tan27°−\tan 63°+\tan 81°=4.}