Catégorie : Niveau Prépa

Vous allez justifier dans cet article que le polynôme à coefficients entiers suivant :

P = X^4-10X^2+1

est irréductible dans $\Q[X].$

Vous effectuez d’abord une analyse, en supposant que $P$ s’écrit comme produit de deux polynômes à coefficients rationnels, ces deux polynômes ayant un degré inférieur ou égal à $3.$

Analyse 1/4 : utilisez le lemme de Gauss

Comme $P$ est réductible dans $\Q[X]$ mais appartient aussi à $\Z[X]$ il s’ensuit, d’après le contenu rédigé dans l'article 314 que $P$ est réductible dans $\Z[X].$

$P$ s’écrit donc comme le produit de deux polynômes à coefficients entiers, ces deux polynômes ayant un degré inférieur ou égal à $3.$

Analyse 2/4 : éliminez les degrés $1$ et $3$ dans la décomposition du polynôme $P$

Supposez que l’un des deux polynômes soit de degré $1.$

Il existe $(a,b,r,s,t,u)\in\Z^6$ tel que $P = QR$ avec :

\begin{align*}
Q &= aX+b\\
R &= rX^3+sX^2+tX+u.
\end{align*}

Par identification du coefficient dominant de $QR$ vous déduisez :

ar = 1.

Du coup $a\mid 1$ et :

a\in\{-1,1\}.

Par identification du coefficient constant de $QR$ vous déduisez :

bu =1.

Du coup $b\mid 1$ et :

b\in\{-1,1\}.

De ce qui précède, quatre cas sont à examiner.

Cas n°1 : $Q = X+1$

Vous observez que $Q(-1) = 0$, donc $P(-1) = Q(-1)R(-1)=0.$

Or :

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

Vous obtenez une contradiction.

Cas n°2 : $Q = X-1$

Vous observez que $Q(1) = 0$, donc $P(1) = Q(1)R(1)=0.$

Or :

\begin{align*}
P(1) &= 1^4-10\times 1^2+1\\
&= 1-10+1\\
&=-8.
\end{align*}

Vous obtenez une contradiction.

Cas n°3 : $Q = -X+1$

Vous avez $Q(1)=0$ ce qui ramène au cas n°2 et à une contradiction.

Cas n°3 : $Q = -X-1$

Vous avez $Q(-1)=0$ ce qui ramène au cas n°1 et à une contradiction.

Vous déduisez que $P$, dans sa décomposition, ne peut admettre de polynôme de degré $1$ à coefficients entiers.

De même, supposez que l’un des deux polynômes soit de degré $3.$ Pour des questions de degré, l’autre polynôme est de degré $1$ ce qui est impossible.

Vous déduisez que $P$, dans sa décomposition, ne peut admettre de polynôme de degré $3$ à coefficients entiers.

Analyse 3/4 : le degré $2$ dans la décomposition du polynôme $P$

D’après ce qui précède, $P$ s’écrit comme produit de deux polynômes de degré $2$, à coefficients entiers.

Vous notez dans la suite par $Q$ l’un de ces deux polynômes, avec $Q\in\Z[X].$

Cette fois-ci la méthode précédente ne sera pas utilisée au profit d’une variante avec les polynômes de Lagrange. Bien que longue et réservée à du calcul formel par ordinateur, cette méthode sera ici détaillée afin d’en comprendre les principes essentiels.

Pour connaître les candidats possibles pour ce polynôme $Q$ qui est de degré $2$, il suffit d’en connaître les valeurs prises sur $3$ nombres.

Comme $Q \mid P$, vous déduisez immédiatement que :

\begin{align*}
Q(0)&\mid P(0) \\
Q(2)&\mid P(2) \\
Q(-2)&\mid P(-2).
\end{align*}

Vous évaluez le polynôme $P$ en ces valeurs.

\begin{align*}
P(0) &= 1\\
P(2) &= 16-40+1 = 17-40 = -23\\
P(-2) &= P(2)  = -23.
\end{align*}

Note. Vous auriez pu utiliser $P(1) = -8$ mais $-8$ admet beaucoup trop de diviseurs, ce qui augmente le nombre de cas à traiter.

Cela s’écrit :

\begin{align*}
Q(0)&\mid 1 \\
Q(2)&\mid 23 \\
Q(-2)&\mid 23.
\end{align*}

C’est-à-dire :

\begin{align*}
Q(0)&\in \{-1,1\} \\
Q(2)&\in \{-23,-1,1,23\} \\
Q(-2)&\in \{-23,-1,1,23\}.
\end{align*}

D’après la formule des polynômes interpolateurs de Lagrange, vous avez :

\begin{align*}
Q(X) &= Q(0)\frac{(X-2)(X+2)}{(0-2)(0+2)}+Q(2)\frac{X(X+2)}{2(2+2)}+Q(-2)\frac{X(X-2)}{-2(-2-2)}\\
 &= Q(0)\frac{(X-2)(X+2)}{-4}+Q(2)\frac{X(X+2)}{8}+Q(-2)\frac{X(X-2)}{8}\\
&= Q(0)\frac{X^2-4}{-4}+Q(2)\frac{X^2+2X}{8}+Q(-2)\frac{X^2-2X}{8}\\
&= Q(0)\frac{8-2X^2}{8}+Q(2)\frac{X^2+2X}{8}+Q(-2)\frac{X^2-2X}{8}\\
&= \frac{(-2Q(0)+Q(2)+Q(-2))X^2+(2Q(2)-2Q(-2))X+8Q(0)}{8}\\
&=\frac{-2Q(0) + Q(2)+Q(-2)}{8}X^2+\frac{Q(2)-Q(-2)}{4}X + Q(0).
\end{align*}

Cela vous donne un nombre fini de candidats pour le polynôme $Q.$

Analyse 4/4 : citez les candidats potentiels

Vous obtenez le tableau suivant :

\begin{array}{|c|c|c|c|}
\hline
Q(0) & Q(2) & Q(-2) & Q(X) \\
\hline
-1 & -23 & -23 &-\frac{11 X^2}{2}-1 \\
-1 & -23 & -1 & -\frac{11 X^2}{4}-\frac{11 X}{2}-1 \\
-1 & -23 & 1 & -\frac{5 X^2}{2}-6 X-1 \\
-1 & -23 & 23 &  \frac{X^2}{4}-\frac{23 X}{2}-1 \\
-1 & -1 & -23 &  -\frac{11 X^2}{4}+\frac{11 X}{2}-1 \\
-1 & -1 & -1 & -1 \\
-1 & -1 & 1& \frac{X^2}{4}-\frac{X}{2}-1 \\
-1 & -1 & 23 & 3 X^2-6 X-1 \\
-1 & 1 & -23 & -\frac{5 X^2}{2}+6 X-1 \\
-1 & 1 & -1 & \frac{X^2}{4}+\frac{X}{2}-1 \\
-1 & 1 & 1& \frac{X^2}{2}-1 \\
-1 & 1 & 23 & \frac{13 X^2}{4}-\frac{11 X}{2}-1 \\
-1 & 23 & -23 & \frac{X^2}{4}+\frac{23 X}{2}-1 \\
-1 & 23& -1 & 3 X^2+6 X-1 \\
-1 & 23 & 1& \frac{13 X^2}{4}+\frac{11 X}{2}-1 \\
-1 & 23 & 23 & 6 X^2-1 \\
\hline
1 & -23 & -23 & -6 X^2+1 \\
1 & -23 & -1 & -\frac{13 X^2}{4}-\frac{11 X}{2}+1\\
1 & -23 & 1 & -3 X^2-6 X+1\\
1 & -23 & 23 & -\frac{X^2}{4}-\frac{23 X}{2}+1 \\
1 & -1 & -23 & -\frac{13 X^2}{4}+\frac{11 X}{2}+1 \\
1 & -1 & -1 & 1-\frac{X^2}{2} \\
1 & -1 & 1& -\frac{X^2}{4}-\frac{X}{2}+1 \\
1 & -1 & 23 & \frac{5 X^2}{2}-6 X+1 \\
1 & 1 & -23 & -3 X^2+6 X+1 \\
1 & 1 & -1 & -\frac{X^2}{4}+\frac{X}{2}+1 \\
1 & 1 & 1& 1 \\
1 & 1 & 23 & \frac{11 X^2}{4}-\frac{11 X}{2}+1 \\
1 & 23 & -23 & -\frac{X^2}{4}+\frac{23 X}{2}+1 \\
1 & 23& -1 & \frac{5 X^2}{2}+6 X+1 \\
1 & 23 & 1& \frac{11 X^2}{4}+\frac{11 X}{2}+1 \\
1 & 23 & 23 & \frac{11 X^2}{2}+1 \\
\hline
\end{array}

Comme le polynôme $Q$ appartient à $\Z[X]$ et est de degré $2$, il ne reste que six possibilités.

\left|\begin{align*}
&Q = 3 X^2-6 X-1 \\
&\text{ou}\\
&Q = 3 X^2+6 X-1\\
&\text{ou}\\
&Q = 6 X^2-1\\
&\text{ou}\\
&Q = -6 X^2+1\\
&\text{ou}\\
&Q = -3 X^2-6 X+1\\
&\text{ou}\\
&Q = -3 X^2+6 X+1.
\end{align*}
\right.

Comme $Q$ est le premier polynôme dans la décomposition de $P$ qui est réductible, vous déduisez que le reste de la division euclidienne de $P$ par $Q$ est nul et que le quotient de cette division est un polynôme à coefficients entiers.

Synthèse

Supposez que $Q$ soit un polynôme de degré $2$ à coefficients dans $\Z[X]$ tel que :

Q\in\{3 X^2-6 X-1,  3 X^2+6 X-1, 6 X^2-1, -6 X^2+1, -3 X^2-6 X+1 , -3 X^2+6 X+1\}.

Supposez que $R$ soit un polynôme de degré $2$ à coefficients dans $\Z[X]$ tel que :

P = QR.

Cette relation, dans $\Q[X]$ s’écrit :

P = QR + 0.

Du coup, $R$ est le quotient de la division euclidienne de $P$ par $Q$ et le reste de cette division est nul.

Pour les 6 divisions, vous obtenez le tableau suivant.

\begin{array}{|c|c|c|c|}
\hline
P & Q & \text{quotient} & \text{reste} \\
\hline
X^4-10X^2+1 &  3 X^2-6 X-1 & \frac{X^2}{3}+\frac{2 X}{3}-\frac{17}{9} & -\frac{32 X}{3}-\frac{8}{9} \\
X^4-10X^2+1 &   3 X^2+6 X-1 & \frac{X^2}{3}-\frac{2 X}{3}-\frac{17}{9} & \frac{32 X}{3}-\frac{8}{9} \\ 
X^4-10X^2+1 &   6 X^2-1 & \frac{X^2}{6}-\frac{59}{36} &-\frac{23}{36}  \\
X^4-10X^2+1 & -6 X^2+1 & \frac{59}{36}-\frac{X^2}{6} & -\frac{23}{36}\\
X^4-10X^2+1 &  -3 X^2-6 X+1 & -\frac{X^2}{3}+\frac{2 X}{3}+\frac{17}{9} & \frac{32 X}{3}-\frac{8}{9} \\
X^4-10X^2+1 &  -3 X^2+6 X+1 & -\frac{X^2}{3}-\frac{2 X}{3}+\frac{17}{9} & -\frac{32 X}{3}-\frac{8}{9}\\
\hline
\end{array}

Vous constatez qu’aucun quotient n’est un polynôme de $\Z[X].$ A titre surabondant, aucun reste n’est nul.

Vous déduisez qu’aucun polynôme parmi les six proposés pour $Q$ ne convient.

Note. Vous auriez pu conclure plus rapidement en procédant par une identification du coefficient dominant de $P$, montrant que le coefficient dominant du quotient ne peut être un entier. Cependant la priorité a été mise sur une méthode certes longue mais qui fonctionne dans toutes les situations.

Concluez

La partie analyse montre que, si $P$ est un polynôme réductible dans $\Q[X]$, alors il existe un polynôme $Q$ à coefficients entiers tel que :

\begin{align*}
Q &\mid P\\
Q&\in\{3 X^2-6 X-1,  3 X^2+6 X-1, 6 X^2-1, -6 X^2+1, -3 X^2-6 X+1 , -3 X^2+6 X+1\}.
\end{align*}

De plus, le reste de la division de $P$ par $Q$ est nul.
Le quotient de cette division est un polynôme à coefficients entiers.

La partie synthèse montre que, quel que soit le polynôme

Q\in\{3 X^2-6 X-1,  3 X^2+6 X-1, 6 X^2-1, -6 X^2+1, -3 X^2-6 X+1 , -3 X^2+6 X+1\}

le reste de la division de $P$ par $Q$ est non nul, autrement dit :

Q \nmid P.

Par analyse-synthèse, il a été démontré que le polynôme $P = X^4-10X^2+1$ est irréductible dans $\Q[X].$

Vous allez démontrer le lemme suivant, attribué à Gauss, qui stipule que, si un polynôme non constant à coefficients entiers est réductible dans $\Q[X]$, alors il est aussi réductible dans $\Z[X].$

Plus précisément, si $P$ est un polynôme non constant, de degré $n\geq 1$, à coefficients entiers de sorte que $P$ soit réductible dans $\Q[X]$ à savoir :

\exists (R,S)\in\Q[X]^2, P = RS

avec $R$ et $S$ non constants de sorte que :

\left\{\begin{align*}
\deg R < \deg P\\
\deg S < \deg P\\
\end{align*}
\right.

alors, il existe un rationnel non nul $q$ tel que :

\left\{\begin{align*}
qR &\in\Z[X]\\
\frac{1}{q}S&\in\Z[X].
\end{align*}
\right.

En posant $R’ = qR$ et $S’ = \frac{1}{q}S$ vous avez $\deg R = \deg R’$ et $\deg S’ = \deg S.$ Les polynômes $R’$ et $S’$ sont à coefficients entiers, $P = R’S’$ avec $\deg R’ < \deg P $ et $\deg S’ < \deg P$ ce qui signifie que $P$ est réductible dans $\Z[X].$

Illustration du lemme

Posez :

\begin{align*}
R &= 6 X - \frac{3}{2}\\
S &= \frac{28}{3}X+4\\
P &= RS.
\end{align*}

Alors, en développant :

\begin{align*}
P &= 56X^2-14X+24X-6\\
&=56X^2+10X-6.
\end{align*}

D’après ce qui précède, le polynôme $P$ est réductible dans $\Q[X]$ et il est à coefficients entiers.

Or :

\begin{align*}
P &= RS\\ 
& =  \left(6 X - \frac{3}{2}\right)\left(\frac{28}{3}X+4\right)\\
& = \left[\frac{1}{2}\left(12 X - 3\right)\right]\left[\frac{1}{3}\left(28X+12\right)\right]\\
& = \left[\frac{3}{2}\left(4 X - 1\right)\right]\left[\frac{4}{3}\left(7X+3\right)\right]\\
& =\left[ \frac{3}{2}\times \frac{4}{3}\right] (4 X - 1)(7X+3)\\
& =2(4 X - 1)(7X+3)\\
& =(8 X - 4)(7X+3)\\
& =\left[\frac{4}{3}\left(6 X - \frac{3}{2}\right)\right]\left[\frac{3}{4}\left(\frac{28}{3}X+4\right)\right].
\end{align*}

Vous déduisez, en posant $q = \frac{4}{3}$ :

\begin{align*}
P &=  (qR)\left(\frac{1}{q}S\right)\\
&= (8X-4)(7X+3).
\end{align*}

Cela montre bien que $P$ est réductible dans $\Z[X].$

Cet exemple illustre la méthode : vous factorisez d’abord $R$ en utilisant le PPCM des dénominateurs de ses coefficients. Puis vous factorisez $12X-3$ qui est à coefficients entiers, par le PGCD de tous ses coefficients. Vous effectuez le même procédé sur le polynôme $S.$ Vous obtenez à la fin deux polynômes à coefficients entiers.

Dans ce qui suit, vous allez démontrer que la méthode fonctionne dans tous les cas.

Une preuve du lemme de Gauss

Soient $R$ et $S$ deux polynômes à coefficients rationnels et non constants. Vous formez le produit $P = RS$ et vous supposez que $P\in\Z[X].$

En notant $r$ le degré du polynôme $R$ et $s$ celui du polynôme $S$ vous déduisez déjà que $r\geq 1$ et que $s\geq 1$ et qu’il existe $(a_0,a_1,\dots,a_r)\in\Z^{r+1}$, $(b_0,b_1,\dots,b_r)\in (\NN)^{r+1}$, $(u_0,u_1,\dots,u_s)\in\Z^{s+1}$, $(v_0,v_1,\dots,v_s)\in (\NN)^{s+1}$ tels que :

\left\{\begin{align*}
R &= \sum_{k=0}^{r}\frac{a_k}{b_k} X^k \\
S &= \sum_{\ell=0}^{s}\frac{u_{\ell}}{v_{\ell}} X^{\ell}.
\end{align*}
\right.

Vous posez ensuite :

\left\{
\begin{align*}
b &= \mathrm{PPCM}(b_0,b_1,\dots, b_r) \\
v &= \mathrm{PPCM}(v_0,v_1,\dots, v_s).
\end{align*}
\right.

Alors $b\geq 1$ et $v\geq 1.$ De plus, pour tout $k\in\llbracket 0, r\rrbracket$ vous avez $\frac{b}{b_k} \in\NN.$ De même, pour tout $\ell \in\llbracket 0, s\rrbracket$ vous avez $\frac{v}{v_{\ell}} \in\NN.$

Il vient :

\left\{\begin{align*}
R &=\frac{1}{b} \sum_{k=0}^{r}\frac{b\ a_k}{b_k} X^k \\
S &= \frac{1}{v} \sum_{\ell=0}^{s}\frac{v\ u_{\ell}}{v_{\ell}} X^{\ell}.
\end{align*}
\right.

Pour tout $k\in\llbracket 0, r\rrbracket$ vous posez $c_k = \frac{b\ a_k}{b_k} \in\Z.$ De même, pour tout $\ell \in\llbracket 0, s\rrbracket$ vous posez $w_{\ell} = \frac{v\ u_{\ell}}{v_{\ell}} \in\Z.$ Dès lors :

\left\{\begin{align*}
R &=\frac{1}{b} \sum_{k=0}^{r}c_k X^k \\
S &= \frac{1}{v} \sum_{\ell=0}^{s} w_{\ell} X^{\ell}.
\end{align*}
\right.

Comme $c_r/b$ et $w_s/v$ sont les coefficients dominants respectifs des polynômes $R$ et $S$ qui sont non constants, vous avez $c_r \neq 0$ et $w_s\neq 0.$

Vous posez ensuite :

\left\{
\begin{align*}
c &= \mathrm{PGCD}(c_0,c_1,\dots, c_r) \\
w &= \mathrm{PGCD}(w_0,w_1,\dots, w_s).
\end{align*}
\right.

Vous notez que $c$ et $w$ sont deux entiers supérieurs ou égaux à $1.$

Pour tout $k\in\llbracket 0, r\rrbracket$ vous posez $c_k^{\#} = \frac{c_k}{c} \in\Z.$ De même, pour tout $\ell \in\llbracket 0, s\rrbracket$ vous posez $w_{\ell}^{\#} = \frac{w_{\ell}}{w} \in\Z.$

Notez que $c_r^{\#} = \frac{c_r}{c}$ donc $c_r^{\#} \neq 0.$ De même, $w_s^{\#} = \frac{w_s}{w}$ donc $w_s^{\#} \neq 0.$

Dès lors :

\left\{
\begin{align*}
 &\mathrm{PGCD}(c_0^{\#},c_1^{\#},\dots, c_r^{\#}) =1 \\
 &\mathrm{PGCD}(w_0^{\#},w_1^{\#},\dots, w_s^{\#}) =1.
\end{align*}
\right.

Les polynômes $R$ et $S$ sont enfin écrits sous la forme adéquate :

\left\{\begin{align*}
R &=\frac{c}{b} \sum_{k=0}^{r}c_k^{\#} X^k \\
S &= \frac{w}{v} \sum_{\ell=0}^{s} w_{\ell}^{\#} X^{\ell}.
\end{align*}
\right.

Par produit, il vient :

P = \frac{cw}{bv} \left( \sum_{k=0}^{r}c_k^{\#} X^k \right) \left(\sum_{\ell=0}^{s} w_{\ell}^{\#} X^{\ell}\right).

Il s’agit maintenant de comprendre pourquoi le rationnel $\frac{cw}{bv}$ est un nombre entier naturel non nul.

Il a été noté que les quatre nombres entiers $c$, $w$, $b$ et $v$ sont tous strictement positifs. Le rationnel $\frac{cw}{bv}$ est donc strictement positif.

Pour comprendre pourquoi c’est un entier, vous allez multiplier l’expression de $P$ par $bv$ pour obtenir ceci :

bvP = cw  \left( \sum_{k=0}^{r}c_k^{\#} X^k \right) \left(\sum_{\ell=0}^{s} w_{\ell}^{\#} X^{\ell}\right).

Dans la suite, vous notez $Q$ ce polynôme, qui est à coefficients entiers.

Pour tout $m\in\llbracket 0, r+s\rrbracket$ vous posez :

d_m = \sum_{\substack{k+\ell = m \\0\leq k \leq r \\0\leq \ell \leq s }} c_k^{\#}w_{\ell}^{\#}

de sorte qu’après développement :

\left( \sum_{k=0}^{r}c_k^{\#} X^k \right) \left(\sum_{\ell=0}^{s} w_{\ell}^{\#} X^{\ell}\right) = \sum_{m=0}^{r+s} d_m X^m.

Comme :

Q = bvP =  \sum_{m=0}^{r+s} (cwd_m) X^m

vous déduisez que tous les coefficients de $Q$ dont divisibles par l’entier $bv.$

Par identification des coefficients, vous déduisez :

\forall m\in \llbracket 0, r+s \rrbracket, bv \mid cwd_m.

Notez que par produit, $c_r^{\#} w_s^{\#} \neq 0.$ Ainsi, $d_{r+s} \neq 0$ et par suite $cw d_{r+s} \neq 0.$

Par conséquent :

\begin{align*}
&bv \mid \mathrm{PGCD}(cwd_0, cwd_1,\dots cwd_{r+s}) \\
&bv \mid  cw\times \mathrm{PGCD}(d_0, d_1,\dots d_{r+s}).
\end{align*}

Démontrez que $\mathrm{PGCD}(d_0, d_1,\dots d_{r+s}) = 1$

C’est le point clef de la démonstration du lemme de Gauss.

Raisonnez par l’absurde et supposez que $\mathrm{PGCD}(d_0, d_1,\dots d_{r+s}) \geq 2.$

Il existe donc un nombre premier $p$ tel que :

p\mid \mathrm{PGCD}(d_0, d_1,\dots d_{r+s}).

Notez que

\mathrm{PGCD}(c_0^{\#},c_1^{\#},\dots, c_r^{\#}) =1

Il est donc impossible d’avoir :

\forall k\in\llbracket 0, r\rrbracket, p\mid c_k^{\#}

sinon vous auriez :

p \mid \mathrm{PGCD}(c_0^{\#},c_1^{\#},\dots, c_r^{\#}) 

et donc $p=1$ ce qui contredit le fait que $p$ est premier.

L’ensemble suivant :

\{ k\in \llbracket 0, r\rrbracket, p \nmid c_k^{\#} \}

est non vide.

De même, l’ensemble suivant :

\{ \ell \in \llbracket 0, s\rrbracket, p \nmid w_{\ell}^{\#} \}

est aussi non vide.

Vous posez donc :

\begin{align*}
k' =\min \{ k\in \llbracket 0, r\rrbracket, p \nmid c_k^{\#} \} \\
\ell' =\min\{ \ell \in \llbracket 0, s\rrbracket, p \nmid w_{\ell}^{\#} \}.
\end{align*}

En calculant $d_{k’+\ell’}$ il vient :

\begin{align*}
d_{k'+\ell'} &= \sum_{\substack{k+\ell = k'+\ell'  \\0\leq k \leq r\\0\leq \ell \leq s }} c_k^{\#}w_{\ell}^{\#} \\
&=c_{k'}^{\#}w_{\ell'}^{\#}+ \sum_{\substack{k+\ell = k'+\ell'  \\ k\in\llbracket 0, r\rrbracket\setminus\{k'\}  \\  \ell\in\llbracket 0, s\rrbracket\setminus\{\ell'\} }} c_k^{\#}w_{\ell}^{\#}.
\end{align*}

Ainsi :

c_{k'}^{\#}w_{\ell'}^{\#} = d_{k'+\ell'} -  \sum_{\substack{k+\ell = k'+\ell'  \\ k\in\llbracket 0, r\rrbracket\setminus\{k'\}  \\  \ell\in\llbracket 0, s\rrbracket\setminus\{\ell'\} }} c_k^{\#}w_{\ell}^{\#}.

Comme $p\mid \mathrm{PGCD}(d_0, d_1,\dots d_{r+s})$ il vient $p \mid d_{k’+\ell’}.$

D’autre part par définition du minimum $k’$ :

\forall k\in\llbracket 0, k'-1\rrbracket, p\mid c_k^{\#}.

Donc :

\forall k\in\llbracket 0, k'-1\rrbracket, \forall \ell \in\llbracket 0, s\rrbracket, p\mid c_k^{\#}w_{\ell}^{\#}.

Vous déduisez que :

p \mid  \sum_{\substack{k+\ell = k'+\ell'  \\ k\in\llbracket 0, r\rrbracket\setminus\{k'\} \\ k < k'  \\  \ell\in\llbracket 0, s\rrbracket\setminus\{\ell'\} }} c_k^{\#}w_{\ell}^{\#}.

De même, par définition du minimum $\ell’$ :

\forall \ell \in\llbracket 0, \ell'-1\rrbracket, p\mid w_{\ell}^{\#}.

Soient maintenant $k$ et $\ell$ deux entiers tels que :

\left\{
\begin{align*}
 k+\ell = k'+\ell'\\
k\in\llbracket 0, r\rrbracket\setminus\{k'\}\\
k > k' \\
\ell\in\llbracket 0, s\rrbracket  \setminus\{\ell'\}.
\end{align*}
\right.

Il vient :

k-k' = \ell'-\ell.

Or $k-k’>0$ donc $k-k’ \geq 1$ donc $\ell’-\ell \geq 1$ donc $\ell \leq \ell’-1$ et du coup $p\mid w_{\ell}^{\#}$ et $p \mid c_k^{\#}w_{\ell}^{\#}.$

Vous déduisez que :

p \mid  \sum_{\substack{k+\ell = k'+\ell'  \\ k\in\llbracket 0, r\rrbracket \\ k > k'  \\  \ell\in\llbracket 0, s\rrbracket\setminus\{\ell'\} }} c_k^{\#}w_{\ell}^{\#}.

Ainsi :

\left\{\begin{align*}
&p\mid d_{k'+\ell'} \\
&p\mid  \sum_{\substack{k+\ell = k'+\ell'  \\ k\in\llbracket 0, r\rrbracket\setminus\{k'\}  \\  \ell\in\llbracket 0, s\rrbracket\setminus\{\ell'\} }} c_k^{\#}w_{\ell}^{\#}.
\end{align*}
\right.

Par différence, vous déduisez :

\left\{\begin{align*}
&p\mid d_{k'+\ell'} -  \sum_{\substack{k+\ell = k'+\ell'  \\ k\in\llbracket 0, r\rrbracket\setminus\{k'\}  \\  \ell\in\llbracket 0, s\rrbracket\setminus\{\ell'\} }} c_k^{\#}w_{\ell}^{\#} \\
&p\mid c_{k'}^{\#}w_{\ell'}^{\#}
\end{align*}
\right.

Via le lemme d’Euclide, il y a deux possibilités.

Soit $p\mid c_{k’}^{\#}$, mais cela contredit la définition de $k’$.

Soit $p\mid w_{\ell’}^{\#}$, mais cela contredit la définition de $\ell’$.

Il y a contradiction.

L’hypothèse $\mathrm{PGCD}(d_0, d_1,\dots d_{r+s}) \geq 2$ est donc fausse et par conséquent :

\mathrm{PGCD}(d_0, d_1,\dots d_{r+s}) =1.

Concluez

Du coup :

bv \mid  cw.

Le nombre $\frac{cw}{bv}$ est un entier strictement positif. Notez-le $\alpha$ dans la suite.

Alors vous avez l’égalité :

\begin{align*}
P &= \alpha \left( \sum_{k=0}^{r}c_k^{\#} X^k \right) \left(\sum_{\ell=0}^{s} w_{\ell}^{\#} X^{\ell}\right)\\
&= \left( \sum_{k=0}^{r}\alpha\ c_k^{\#} X^k \right) \left(\sum_{\ell=0}^{s} w_{\ell}^{\#} X^{\ell}\right).
\end{align*}

Cette égalité montre bien que le polynôme $P$ est réductible dans $\Z[X].$

Vous allez terminer en effectuant le lien avec les polynômes $R$ et $S$ de départ : il reste à définir un rationnel $q$ pour avoir $qR\in\Z[X]$ et $\frac{1}{q}S \in\Z[X].$ Remarquez que :

\begin{align*}
R &=\frac{c}{b} \sum_{k=0}^{r}c_k^{\#} X^k \\
&=\frac{c}{\alpha\ b} \sum_{k=0}^{r}\alpha\ c_k^{\#} X^k \\
\end{align*}

Posez $q = \frac{\alpha b }{c}$, vous avez :

qR = \sum_{k=0}^{r}\alpha\ c_k^{\#} X^k.

Donc $qR \in\Z[X].$

D’autre part :

\begin{align*}
\frac{1}{q}S &= \frac{c}{\alpha\ b}\frac{w}{v} \sum_{\ell=0}^{s} w_{\ell}^{\#} X^{\ell} \\
&=  \frac{cw}{\alpha\ bv} \sum_{\ell=0}^{s} w_{\ell}^{\#} X^{\ell}.
\end{align*}

Or : $\frac{cw}{bv} = \alpha$ donc $cw = \alpha bv$ et par suite :

\frac{1}{q}S = \sum_{\ell=0}^{s} w_{\ell}^{\#} X^{\ell}.

Donc $\frac{1}{q}S \in\Z[X].$

Il a été démontré que :

P = (qR)\left(\frac{1}{q}S\right).

Comme les polynômes $qR$ et $\frac{1}{q}S$ sont à coefficients entiers, le polynôme $P$ se réduit bien dans $\Z[X].$

Prolongement

Vous souhaitez utiliser le résultat établi pour démontrer qu’un polynôme précis est irréductible ? Allez jeter un oeil dans le contenu rédigé dans l'article 315.

Dans cet article, l’objectif est d’aboutir à la propriété suivante, traduisant la multiplicité du $\mathrm{PGCD}$ :

\forall (a,b)\in\Z^2\setminus\{(0,0)\}, \forall m\in \N^{*}, \mathrm{PGCD}(ma,mb) = m\times \mathrm{PGCD}(a,b).

Note. L’algorithme d’Euclide permet de démontrer ce résultat. Néanmoins, une autre approche sera utilisée, de façon à manipuler les autres propriétés du $\mathrm{PGCD}.$

Démontrez une première inégalité

Fixez le contexte

Soient $a$ et $b$ deux entiers non simultanément nuls et soit $m$ un entier naturel non nul.

Comme $(a,b)\neq (0,0)$ le $\mathrm{PGCD}$ des entiers $a$ et $b$ est bien défini et :

\mathrm{PGCD}(a,b) = \max\{n\in\N^{*}, n\mid a \text{ et }n\mid b\}.

Comme $m$ est non nul, vous avez aussi $(ma,mb)\neq (0,0)$ le $\mathrm{PGCD}$ des entiers $ma$ et $mb$ est bien défini et :

\mathrm{PGCD}(ma,mb) = \max\{n\in\N^{*}, n\mid ma \text{ et }n\mid mb\}.

Passez à la démonstration

Notez $d = \mathrm{PGCD}(a,b).$

Alors $d\mid a$ et $d\mid b.$

En multipliant par $m$, il vient :

$md\mid ma$ et $md \mid mb.$

Comme $d$ et $m$ sont non nuls, vous déduisez que $md$ est non nul. Par conséquent :

md\in \{n\in\N^{*}, n\mid ma \text{ et }n\mid mb\}.

Du coup, vous déduisez :

md \leq \mathrm{PGCD}(ma,mb).

Il a donc été démontré que :

\boxed{\forall (a,b)\in\Z^2\setminus\{(0,0)\}, \forall m\in \N^{*}, m\times \mathrm{PGCD}(a,b) \leq \mathrm{PGCD}(ma,mb).}

Démontrez une seconde inégalité

Cet autre passage est plus délicat, dans la mesure où il est choisi volontairement de ne pas utiliser l’algorithme d’Euclide.

Soient $a$ et $b$ deux entiers non simultanément nuls et soit $m$ un entier naturel non nul.

Vous posez $u = \mathrm{PGCD}(ma,mb).$

Alors :

\left\{\begin{align*}
u&\mid ma\\
u&\mid mb.
\end{align*}
\right.

Vous notez encore $d = \mathrm{PGCD}(a,b).$

Il existe donc deux entiers $a’$ et $b’$ tels que :

\left\{\begin{align*}
a&= da'\\
b&= db'.
\end{align*}
\right.

Remarquez que $(a’,b’)\neq (0,0)$ sinon vous auriez $(a,b)=(0,0)$ ce qui est exclu.

Démontrez que $a’$ et $b’$ sont premiers entre eux

D’après la première inégalité, il vient :

d\times \mathrm{PGCD}(a',b') \leq \mathrm{PGCD}(da',db').

Cela s’écrit :

d\times \mathrm{PGCD}(a',b') \leq \mathrm{PGCD}(a,b).

C’est-à-dire :

d\times \mathrm{PGCD}(a',b') \leq d.

Comme $d\neq 0$ il vient :

 \mathrm{PGCD}(a',b') \leq 1.

Or, $\mathrm{PGCD}(a’,b’)$ est un entier non nul, donc :

\boxed{\mathrm{PGCD}(a',b') = 1.}

Ramenez-vous au théorème de Gauss

Comme

\left\{\begin{align*}
u&\mid mda'\\
u&\mid mdb'
\end{align*}
\right.

Il existe deux entiers $a »$ et $b »$ tels que :

\left\{\begin{align*}
mda'   &= ua''\\
mdb' &= ub''.
\end{align*} 
\right.

Ainsi :

\left\{\begin{align*}
mda'b''   &= ua''b''\\
mdb'a'' &= ua''b''.
\end{align*} 
\right.

Ainsi, il vient $mda’b » = mdb’a ».$ Comme $m\neq 0$ et comme $d\neq 0$ il vient :

a'b'' = a''b'.

Premier cas : $a’ \neq 0.$ Comme :

a' \mid a''b'

et comme $\mathrm{PGCD}(a’,b’)=1$ le théorème de Gauss (dont une preuve directe se trouve dans le contenu rédigé dans l'article 310) fournit :

a' \mid a''.

Il existe un entier $k$ tel que :

a'' = ka'.

L’égalité $mda’ = ua »$ fournit $mda’ = uka’.$ Comme $a’$ est non nul, vous obtenez $md = uk$ ce qui donne $u \mid md.$

Second cas : $a’ = 0.$ Comme $(a’,b’)\neq (0,0)$ il vient $b’\neq 0.$

Vous utilisez le fait que :

b'\mid  a'b''.

Comme $\mathrm{PGCD}(a’,b’)=1$ le théorème de Gauss fournit :

b' \mid b''.

Il existe un entier $\ell$ tel que :

b'' = \ell b'

L’égalité $mdb’ = ub »$ fournit $mdb’ = u\ell b’.$ Comme $b’\neq 0$ vous déduisez encore que $md = u\ell.$ Donc $u\mid md.$

Il a été démontré que dans tous les cas :

\boxed{u\mid md.}

Comme $u$ et $md$ sont des entiers positifs, cela entraîne :

u\leq md

donc :

\boxed{ \mathrm{PGCD}(ma,mb)\leq m\times \mathrm{PGCD}(a,b) .}

Concluez

Compte tenu des deux inégalités précédentes, le caractère multiplicatif du $\mathrm{PGCD}$ est établi.

\boxed{\forall (a,b)\in\Z^2\setminus\{(0,0)\}, \forall m\in \N^{*}, \mathrm{PGCD}(ma,mb) = m\times \mathrm{PGCD}(a,b).}

Bonus : une autre démonstration de la seconde inégalité

Soient $a$ et $b$ deux entiers non simultanément nuls et soit $m$ un entier naturel non nul.

Vous posez $u = \mathrm{PGCD}(ma,mb).$ Vous avez $u\in\NN.$

Il existe deux entiers $a’$ et $b’$ tels que :

\left\{\begin{align*}
ma &= ua'\\
mb &= ub'.
\end{align*}
\right.

Vous allez considérer dans la suite le nombre $d=\mathrm{PGCD}(u,m)$ qui est bien défini puisque $m$ est non nul. Vous avez $d\in\NN.$

Alors il existe deux entiers $u’\in\NN$ et $m’\in\NN$, nécessairement premiers entre eux, d’après la première inégalité démontrée ci-dessus, tels que :

\left\{\begin{align*}
u &=du'\\
m &= dm'.
\end{align*}
\right.

Vous obtenez alors :

\left\{\begin{align*}
dm'a &= du'a'\\
dm'b &= du'b'.
\end{align*}
\right.

Du coup, en simplifiant par $d\neq 0$ vous obtenez :

\left\{\begin{align*}
m'a &= u'a'\\
m'b &=u'b'.
\end{align*}
\right.

Et vous déduisez :

\left\{
\begin{align*}
u'&\mid m'a\\
u'&\mid m'b.
\end{align*}
\right.

Notez que $u=du’$ avec $u\neq 0$ impose $u’\neq 0.$ Comme $\mathrm{PGCD}(u’,m’)=1$ vous déduisez, par le théorème de Gauss :

\left\{
\begin{align*}
u'&\mid a\\
u'&\mid b.
\end{align*}
\right.

Par définition du $\mathrm{PGCD}$ avec $u’\in\NN$ il vient :

u'\leq \mathrm{PGCD}(a,b).

Vous multipliez par $d$ qui est positif :

du'\leq d\times \mathrm{PGCD}(a,b).

Comme $u=du’$ :

u\leq d\times  \mathrm{PGCD}(a,b).

Or, $d = \mathrm{PGCD}(u,m)$, donc $d\mid m.$ Or $d\in\NN$ et $m\in\NN$ donc $d\leq m.$

Ainsi :

u\leq m\times  \mathrm{PGCD}(a,b).

Cela s’écrit :

\boxed{ \mathrm{PGCD}(ma,mb)\leq m\times \mathrm{PGCD}(a,b) .}

Dans cet article, vous allez démontrer que le théorème de Gauss directement, sans utiliser le théorème de Bézout, dont vous trouverez une démonstration directe dans le contenu rédigé dans l'article 308.

Le théorème de Gauss énonce que, quels que soient $a$, $b$ et $c$ trois entiers relatifs, $a$ étant non nul :

\left\{\begin{array}{l}
a\mid bc\\
\mathrm{PGCD}(a,b)=1
\end{array}
\right. \implies a \mid c.

Pour effectuer une démonstration directe, vous fixez trois entiers relatifs $a$, $b$ et $c$, avec $a\neq 0$ tels que :

\left\{\begin{array}{l}
a\mid bc\\
\mathrm{PGCD}(a,b)=1.
\end{array}
\right.

Introduisez une partie de l’ensemble des entiers naturels

Soit $A$ la partie de $\N$ définie par :

A=\{n\in\NN, a\mid nc\}.

Si $a$ est positif, alors $a>0$ et par suite :

\left\{\begin{array}{l}
a\mid ac\\
a\in\NN.
\end{array}
\right.

Vous en déduisez que $a\in A.$

Si $a$ est négatif vous posez $a’ = -a$ et $a’ >0.$ Il vient :

\left\{\begin{array}{l}
a\mid a' \mid a'c\\
a'\in\NN.
\end{array}
\right.

Donc $a’\in A.$

L’ensemble $A$ est non vide dans tous les cas. Comme $A\subset \N$, l’ensemble $A$ admet un plus petit élément que vous notez $m.$ L’entier $m$ vérifie les deux propriétés suivantes :

\boxed{\left\{\begin{array}{l}
a\mid mc\\
m\in\NN.
\end{array}
\right.}

Démontrez que $m$ divise $a$

Comme $m\in\NN$ vous effectuez la division euclidienne de $a$ par $m.$ Il existe un entier relatif $q$ et un entier $r\in\llbracket 0, m-1\rrbracket$ tels que :

a = mq+r.

Supposez que $r$ soit non nul.

Vous multipliez l’égalité précédente par $c$ :

ac = mcq+rc.

Comme :

\left\{\begin{array}{l}
a\mid ac\\
a\mid mc \mid mcq
\end{array}
\right.

vous déduisez que :

a\mid rc.

Or, $r\in\NN$ donc $r\in A$, donc $r\geq m$ puisque $m$ est le plus petit élément de $A$. Cela contredit l’inégalité $r\leq m-1.$

Donc $r=0$ et par suite $a=mq.$ Du coup :

\boxed{m\mid a.}

Démontrez que $m$ divise $b$

Comme $m\in\NN$ vous effectuez la division euclidienne de $b$ par $m.$ Il existe un entier relatif $q’$ et un entier $r’\in\llbracket 0, m-1\rrbracket$ tels que :

b = mq'+r'.

Supposez que $r’$ soit non nul.

Vous multipliez l’égalité précédente par $c$ :

bc = mcq'+r'c.

Par hypothèse :

a\mid bc.

Or :

a\mid mc \mid mcq'.

Vous en déduisez que :

a\mid r'c.

Or, $r’\in\NN$ donc $r’\in A$ donc $r’\geq m$ puisque $m$ est le plus petit élément de $A.$ Cela contredit l’inégalité $r’\leq m-1.$

Donc $r’=0$ et $b=mq’$ d’où :

\boxed{m\mid b.}

Concluez

L’entier $m$ strictement positif divise $a$ et $b$ à la fois. Par définition du $\mathrm{PGCD}$ il vient $m\leq \mathrm{PGCD}(a,b)$ d’où $m\leq 1.$ Comme $m>0$, vous déduisez $m=1.$

Comme $a\mid mc$ vous avez obtenu le résultat annoncé :

\boxed{a\mid c.}

Soient $n_1$ et $n_2$ deux entiers supérieurs ou égaux à $2$ premiers entre eux et soient $a_1$ et $a_2$ deux entiers relatifs.

Le théorème chinois énonce alors que le système de congruences $\mathscr{S}$ :

\left\{\begin{align*}
x \equiv a_1\quad [n_1]\\
x \equiv a_2\quad [n_2]
\end{align*}
\right.

où l’inconnue $x$ est un entier relatif, admet une infinité de solutions et que deux solutions quelconques de ce système sont congrues modulo le produit $n_1n_2.$

Un préalable avant l’analyse

Comme les entiers $n_1$ et $n_2$ sont premiers entre eux, il vient $\mathrm{PGCD}(n_1,n_2)=1.$

D’après le théorème de Bézout (une démonstration directe est donnée dans le contenu rédigé dans l'article 308), il existe deux entiers relatifs $u_1$ et $u_2$ tels que :

u_1n_1+u_2n_2 = 1.

Analysez le système

Supposez qu’il existe un entier relatif $x$ qui soit solution du système :

\left\{\begin{align*}
x \equiv a_1\quad [n_1]\\
x \equiv a_2\quad [n_2]
\end{align*}
\right.

il existe alors deux entiers relatifs $k_1$ et $k_2$ tels que :

\left\{\begin{align*}
x &= a_1+k_1n_1\\
x&= a_2+k_2n_2.
\end{align*}
\right.

Par soustraction, vous en déduisez les égalités suivantes :

\begin{align*}
0 &= a_2-a_1+k_2 n_2 - k_1n_1 \\
k_1n_1 - k_2 n_2 &= a_2-a_1.
\end{align*} 

Multipliez maintenant l’égalité $u_1n_1+u_2n_2 = 1$ par $a_2-a_1$, il vient :

(a_2-a_1)u_1n_1+(a_2-a_1)u_2n_2 = a_2-a_1.

Par soustraction, vous éliminez $a_2-a_1$ :

[k_1 - (a_2-a_1)u_1]n_1+[-k_2-(a_2-a_1)u_2]n_2 = 0.

Vous en déduisez que :

[k_1 - (a_2-a_1)u_1]n_1 = [k_2+(a_2-a_1)u_2]n_2.

Du coup :

n_1 \mid  [k_2+(a_2-a_1)u_2]n_2.

Comme $n_1$ et $n_2$ sont premiers entre eux avec $n_1\in\NN$, vous appliquez le théorème de Gauss (vous en trouverez une démonstration indépendante et directe, dans le contenu rédigé dans l'article 310) et déduisez que :

n_1 \mid  k_2+(a_2-a_1)u_2.

Il existe donc un entier relatif $t$ tel que :

k_2+(a_2-a_1)u_2 = tn_1.

Cela s’écrit :

k_2 = tn_1+(a_1-a_2)u_2.

Vous en déduisez que :

\begin{align*}
x &=  a_2+k_2n_2\\
&= a_2+( tn_1+(a_1-a_2)u_2)n_2\\
&=a_2+(a_1-a_2)u_2n_2+tn_1n_2\\
&=a_1u_2n_2+a_2(1-u_2n_2)+tn_1n_2\\
&=a_1u_2n_2+a_2(u_1n_1)+tn_1n_2.
\end{align*}

Ainsi vous avez démontré que :

\boxed{x \equiv u_1n_1a_2+ u_2n_2a_1\quad [n_1n_2].}

Note. L’analyse démontre que deux solutions du système de congruences $\mathscr{S}$ sont congrues entre-elles modulo $n_1n_2.$ En effet, soient $x_1$ et $x_2$ deux solutions quelconques de $\mathscr{S}$. Alors :

\begin{align*}
x_1 &\equiv u_1n_1a_2+ u_2n_2a_1\quad [n_1n_2]\\
x_2 &\equiv u_1n_1a_2+ u_2n_2a_1\quad [n_1n_2].
\end{align*}

Par soustraction, il vient :

\begin{align*}
x_1-x_2 \equiv 0 \quad [n_1n_2]\\
x_1 \equiv x_2 \quad [n_1n_2].
\end{align*}

Synthèse

Soit $t$ un entier relatif. Posez :

x = u_1n_1a_2+ u_2n_2a_1 + tn_1n_2.

Modulo $n_1$, il vient :

\begin{align*}
x&\equiv u_2n_2a_1\quad [n_1]\\
x &\equiv (1-u_1n_1)a_1 \quad [n_1]\\
x &\equiv a_1-u_1n_1a_1 \quad [n_1]\\
x &\equiv a_1 \quad [n_1].
\end{align*}

De même, modulo $n_2$ :

\begin{align*}
x&\equiv u_1n_1a_2\quad [n_2]\\
x &\equiv (1-u_2n_2)a_2 \quad [n_2]\\
x &\equiv a_2-u_2n_2a_2 \quad [n_2]\\
x &\equiv a_2 \quad [n_2].
\end{align*}

Ainsi, $x$ est bien solution du système de congruences $\mathscr{S}$.

Note. La synthèse démontre que le système de congruences $\mathscr{S}$ admet une infinité de solutions : à chaque valeur de l’entier $t$, l’entier $u_1n_1a_2+ u_2n_2a_1 + tn_1n_2$ est bien solution. D’autre part, l’ensemble

\{u_1n_1a_2+ u_2n_2a_1 + tn_1n_2, t\in\Z\}

est bien infini compte tenu de l’injectivité de l’application $t\mapsto u_1n_1a_2+ u_2n_2a_1 + tn_1n_2$ qui va de $\Z$ dans $\Z$.

Concluez

D’après l’analyse-synthèse effectuée, il vient d’être démontré que, pour tout entier relatif $x$ :

\boxed{\begin{align*}
 \begin{align*}
\left\{\begin{align*}
x \equiv a_1\quad [n_1]\\
x \equiv a_2\quad [n_2]
\end{align*}
\right. &\Longleftrightarrow \left(\exists t\in\Z, x = u_1n_1a_2+ u_2n_2a_1 + tn_1n_2\right) \\
&\Longleftrightarrow x\equiv  u_1n_1a_2+ u_2n_2a_1 \quad [n_1n_2].
\end{align*}
\end{align*}}

Le système de congruences $\mathscr{S}$ admet une infinité de solutions, toutes congrues entre elles modulo $n_1n_2.$
Le théorème chinois est ainsi démontré.

L’objectif de cet article est de construire une preuve directe du résultat suivant. Etant donnés deux nombres entiers relatifs $a$ et $b$ non simultanément nuls, il existe deux nombres entiers relatifs $u$ et $v$, appelés coefficients de Bézout, tels que :

\mathrm{PGCD}(a,b) = au+bv.

Ce résultat sera appelé théorème de Bézout. Très souvent, ce théorème est démontré à partir de l’algorithme d’Euclide. Une approche différente est proposée ici.

De façon formelle, ce théorème s’écrit ainsi :

\boxed{\forall (a,b)\in\Z^2\setminus\{(0,0)\}, \exists(u,v)\in\Z^2,\mathrm{PGCD}(a,b) =au+bv.}

Note. En aucun cas les nombres $u$ et $v$ ne sont uniquement déterminés par $a$ et $b.$ Seule l’existence de ces deux nombres importe dans le théorème susmentionné.

Note. Vous souhaitez calculer effectivement des coefficients de Bézout ? Reportez-vous au contenu rédigé dans l'article 174.

Vous vous rappelez que, quels que soient les entiers $a$ et $b$ non simultanément nuls, le $\mathrm{PGCD}$ de $a$ et de $b$, noté $\mathrm{PGCD}(a,b)$ désigne le maximum de l’ensemble suivant :

\{n\in\NN, n\mid a \text{ et } n\mid b\}.

Ainsi :

 \forall (a,b)\in\Z^2\setminus\{(0,0)\}, \mathrm{PGCD}(a,b) = \max \{n\in\NN, n\mid a \text{ et } n\mid b\}.

Note. Le $\mathrm{PGCD}$ de deux nombres nuls n’est pas défini, c’est la raison pour laquelle on suppose $(a,b)\neq (0,0).$

Dans toute la suite, $a$ et $b$ désignent deux entiers fixés, non simultanément nuls.

Etudiez un ensemble

Soit $A$ l’ensemble suivant :

A = \{n\in\NN, \exists(u,v)\in\Z^2, n=au+bv\}.

Vous allez dans un premier temps justifier que $A$ est non vide.

Supposez que $a$ soit non nul. Si $a$ est positif, en prenant $u=1$ et $v=0$ vous constatez que $au+bv\in\NN$ donc $au+bv\in A.$

Si $a$ est négatif, vous prenez $u=-1$ et $v=0.$ Vous constatez encore que $au+bv\in\NN$ donc $au+bv\in A.$

Si $a$ est nul, vous déduisez que $b\neq 0.$ Cela provient du fait que $(a,b)\neq (0,0).$ De même, si $b$ est positif, alors en posant $u=0$ et $v=1$, vous avez $au+bv\in\NN$ donc $au+bv\in A.$ Si $b$ est négatif, alors vous posez $u=0$ et $v=-1$ et il vient $au+bv\in\NN$ donc $au+bv\in A.$

Comme $A$ est une partie de $\N$ qui est non vide, elle admet un plus petit élément, qui sera noté $k.$

Justifiez que $k$ est le $\mathrm{PGCD}$ des nombres $a$ et $b$

Comme $k\in A$ vous déduisez que $k\in\NN$ et qu’il existe un couple $(u,v)\in\Z^2$ tel que $k=au+bv.$

Le nombre $k$ est un diviseur commun à $a$ et à $b$

Vous effectuez la division euclidienne de $a$ par $k.$ Il existe $q\in\Z$ et $r\in\llbracket 0, k-1\rrbracket$ tels que :

a = kq+r.

Si $r$ est différent de $0$, alors vous avez :

\begin{align*}
r &= a-kq\\
&=a-(au+bv)q\\
&=a(1-uq)+b(-vq).
\end{align*}

Comme $(1-uq, -vq)\in\Z^2$, avec $r>0$ vous déduisez que $r\in A.$ Or $r< k$ et $k$ est le plus petit élément de $A$ ce qui est impossible.

Donc $r = 0$ et par suite $a = kq$ donc $k\mid a.$

De même, vous effectuez la division euclidienne de $b$ par $k.$ Il existe $q’\in\Z$ et $r’\in\llbracket 0, k-1\rrbracket$ tels que :

b = kq'+r'.

Si $r’$ est différent de $0$, alors vous avez :

\begin{align*}
r' &= b-kq'\\
&=b-(au+bv)q'\\
&=a(-uq')+b(1-vq').
\end{align*}

Comme $(-uq’, 1-vq’)\in\Z^2$, avec $r’>0$ vous déduisez que $r’\in A.$ Or $r'< k$ et $k$ est le plus petit élément de $A$ ce qui est impossible.

Donc $r’ = 0$ et par suite $b = kq’$ donc $k\mid b.$

Comme $k\in\NN$ avec $k\mid a$ et $k\mid b$ vous déduisez $\boxed{k\leq \mathrm{PGCD}(a,b).}$

Le $\mathrm{PGCD}$ de $a$ et de $b$ est inférieur à $k$

Posez $m = \mathrm{PGCD}(a,b).$ Alors $m$ est nombre entier naturel non nul tel que $m\mid a $ et $m\mid b.$

Alors il existe deux entiers relatifs $a’$ et $b’$ tels que :

\begin{align*}
a &= ma'\\
b &= mb'.
\end{align*}

Or, la relation $k =au+bv$ fournit :

\begin{align*}
k &= ma'u+mb'v\\
&= m(a'u+b'v).
\end{align*}

La stricte positivité de $k$ et de $m$ fournit $a’u+b’v \in\NN.$

Cela s’écrit :

\begin{align*}
a'u+b'v &\geq 1\\
m(a'u+b'v) &\geq m\\
k &\geq m.
\end{align*}

Ainsi, $\boxed{\mathrm{PGCD}(a,b)\leq k.}$

Concluez

Il vient d’être démontré que $k = \mathrm{PGCD}(a,b)$ et que :

\mathrm{PGCD }(a,b)=\min \{n\in\NN, \exists(p,q)\in\Z^2, n=ap+bq\}.

En particulier :

\mathrm{PGCD}(a,b)\in\{n\in\NN, \exists(p,q)\in\Z^2, n=ap+bq\}.

Le théorème de Bézout est bien démontré.

\boxed{\forall (a,b)\in\Z^2\setminus\{(0,0)\}, \exists(u,v)\in\Z^2,\mathrm{PGCD}(a,b) =au+bv.}

Définissez une addition interne et une multiplication externe

L’ensemble $\R_{+}^{*}$ des nombres réels strictement positifs va être muni d’une opération interne notée $\oplus$ définie de la façon suivante :

 \begin{array}{lll}
\oplus: & \R_{+}^{*} \times \R_{+}^{*}  & \to \R_{+}^{*}\\
&(x,y) &\mapsto xy.
\end{array}

Tout élément de $\R_{+}^{*}$ va pouvoir être multiplié par un élément du corps $\R$, via la multiplication externe notée $\odot$ définie par :

 \begin{array}{lll}
\odot: & \R \times \R_{+}^{*}  & \to \R_{+}^{*}\\
&(\lambda ,x) &\mapsto x^{\lambda}.
\end{array}

Note. Les éléments du corps $\R$ sont appelés scalaires et ceux de l’ensemble $\R_{+}^{*}$ sont appelés vecteurs.

Vérifiez les quatre axiomes de l’addition interne

Associativité de l’addition

Soit $(x,y,z)\in(\R_{+}^{*})^3.$ D’une part :

\begin{align*}
(x\oplus y) \oplus z &= (xy) \oplus z \\
&= (xy)z\\
&=xyz.
\end{align*}

D’autre part :

\begin{align*}
x\oplus (y \oplus z) &= x \oplus (yz) \\
&= x(yz)\\
&=xyz.
\end{align*}

Vous déduisez :

\boxed{\forall (x,y,z)\in(\R_{+}^{*})^3, (x\oplus y) \oplus z = x\oplus (y \oplus z).}

Commutativité de l’addition

Soit $(x,y)\in(\R_{+}^{*})^2.$ Comme la multiplication usuelle de deux réels est commutative, vous déduisez successivement :

\begin{align*}
x\oplus y&= xy\\
&= yx\\
&=y\oplus x.
\end{align*}

\boxed{\forall (x,y)\in(\R_{+}^{*}),  x\oplus y = y\oplus x.}

Existence d’un élément neutre pour l’addition

Soit $x\in\R_{+}^{*}.$ Comme $1$ est neutre pour la multiplication usuelle des réels, vous avez :

\begin{align*}
1\oplus x &= 1x\\
&=x.
\end{align*}

\boxed{\forall x\in \R_{+}^{*},  1 \oplus x = x.}

Existence d’un opposé pour l’addition

Soit $x\in\R_{+}^{*}.$ Comme $x$ est non nul, il admet un inverse noté $\frac{1}{x}.$ Comme $x$ est strictement positif, $\frac{1}{x}$ l’est aussi. Dès lors :

\begin{align*}
x\oplus \left(\frac{1}{x}\right) &= x\times \frac{1}{x} \\
&= 1.
\end{align*}

\boxed{\forall x\in \R_{+}^{*}, \exists y\in\R_{+}^{*},   x \oplus y = 1.}

Vérifiez les quatre axiomes de la multiplication externe

Distributivité par rapport à l’addition des scalaires

Soit $(\lambda, \mu)\in\R^2$ et soit $x\in\R_{+}^{*}.$ Vous avez :

\begin{align*}
(\lambda + \mu)\odot x &= x^{\lambda+\mu}\\
&= x^{\lambda} x^{\mu}\\
&= (\lambda \odot x) (\mu \odot x)\\
&= (\lambda \odot x) \oplus (\mu \odot x).
\end{align*}

\boxed{\forall (\lambda, \mu)\in\R^2, \forall x\in\R_{+}^{*}, (\lambda+\mu)\odot x =( \lambda\odot x) \oplus (\mu \odot x).}

Distributivité par rapport à l’addition des vecteurs

Soit $\lambda\in\R$ et soit $(x,y)\in(\R_{+}^{*})^2.$ Vous avez :

\begin{align*}
\lambda \odot (x\oplus y) &= \lambda\odot (xy) \\
&= (xy)^{\lambda}\\
&= x^{\lambda} y^{\lambda}\\
&= (\lambda \odot x)(\lambda \odot y)\\
&= (\lambda \odot x)\oplus(\lambda \odot y).
\end{align*}

\boxed{\forall \lambda\in\R, \forall (x,y)\in(\R_{+}^{*})^2, \lambda \odot (x\oplus y) =  (\lambda \odot x)\oplus(\lambda \odot y).}

Compatibilité de la multiplication des réels avec la multiplication externe

Soit $(\lambda, \mu)\in\R^2$ et soit $x\in\R_{+}^{*}.$ Vous avez :

\begin{align*}
(\lambda \mu) \odot x &=x^{\lambda \mu}\\
&= (x^{\mu})^{\lambda}\\
&= (\mu \odot x)^\lambda\\
&= \lambda\odot(\mu \odot x).
\end{align*}

\boxed{\forall (\lambda, \mu)\in\R^2, \forall x\in\R_{+}^{*}, (\lambda \mu) \odot x = \lambda\odot(\mu \odot x).}

Compatibilité du neutre de la multiplication des réels

Soit $x\in\R_{+}^{*}.$

\begin{align*}
1 \odot x &= x^1\\
&= x.
\end{align*}

\boxed{\forall x\in\R_{+}^{*}, 1 \odot x =  x.}

Concluez

Comme les huit axiomes sont vérifiés, les deux opérations $\oplus$ et $\odot$ confèrent à l’ensemble $\R_{+}^{*}$ une structure de $\R$-espace vectoriel.

Notez $u$ le nombre réel défini par :

\boxed{u=2+\sqrt{2}.}

Le titre amène à rechercher tous les polynômes $P\in\Z[X]$ de degré 2 tels que :

P(u)=0.

Note. Vous remarquez que :

u-2 = \sqrt{2}.

En élevant au carré, vous obtenez :

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

Vous déduisez que $u$ est annulé par le polynôme $X^2-4X+2$ qui est de degré $2$ et à coefficients entiers.

La question qui se pose est la suivante : existe-t-il d’autres polynômes de degré $2$, à coefficients entiers, annulant le réel $2+\sqrt{2}$ ? Plusieurs approches sont possibles.

Dans la suite de cet article, vous procèderez comme si vous ne saviez pas précisément que $X^2-4X+2$ est un polynôme qui annule le réel $u.$ L’avantage de cette approche est de retrouver ce résultat autrement et de répondre à la question posée. La recherche des solutions entières d’un système d’équations linéaires à coefficients entiers sera effectuée avec le calcul matriciel.

Analysez le problème

Soit $P$ un polynôme à coefficients entiers, de degré $2$, tel que :

P(u)=0.

Obtenez un système d’équations

Il existe des nombres $a\in\ZZ$, $b\in\Z$ et $c\in\Z$ tels que :

\begin{align*}
au^2+bu+c&=0\\
a(4+2+4\sqrt{2})+b(2+\sqrt{2})+c&=0\\
(6a+2b+c)+(4a+b)\sqrt{2}&=0.
\end{align*}

Supposez un instant que $4a+b$ soit non nul.

Alors :

\sqrt{2}=-\frac{6a+2b+c}{4a+b}.

Cette écriture impliquerait que $\sqrt{2}\in\Q$, autrement dit $\sqrt{2}$ serait rationnel.

Ceci contredit le contenu rédigé dans l'article 122 dans lequel il est démontré que $\sqrt{2}\notin\Q.$

Vous déduisez que :

4a+b=0.

Comme :

(6a+2b+c)+(4a+b)\sqrt{2}=0

vous déduisez :

6a+2b+c=0.

Utilisez des matrices pour résoudre le système obtenu

D’après ce qui précède, vous avez obtenu :

\begin{pmatrix}
6 & 2 & 1\\
4 & 1 & 0 
\end{pmatrix}\begin{pmatrix}
a\\ b\\ c  
\end{pmatrix} = \begin{pmatrix}
0\\ 0  
\end{pmatrix}.

Vous posez maintenant :

\boxed{A = \begin{pmatrix}
6 & 2 & 1\\
4 & 1 & 0 
\end{pmatrix}
}

et vous cherchez à simplifier $A$ en la multipliant par des matrices inversibles, à coefficients entiers, dont les inverses restent à coefficients entiers. Il suffit d’utiliser des matrices de permutation et de transvection, en lien avec les opérations élémentaires sur les colonnes de la matrice $A.$

Simplifiez la matrice $A$ avec des multiplications

D’une part, vous échangez les colonnes $1$ et $3$ de la matrice $A$ vous obtenez :

A \begin{pmatrix}
0  & 0  & 1\\
0  & 1  & 0\\
1  & 0  & 0\\
\end{pmatrix} =  \begin{pmatrix}
1 & 2 & 6 \\
0 & 1 & 4 
\end{pmatrix}.

Vous remplacez la colonne $2$ par elle-même ôtée du double de la colonne $1$, vous obtenez :

A \begin{pmatrix}
0  & 0  & 1\\
0  & 1  & 0\\
1  & 0  & 0\\
\end{pmatrix} \begin{pmatrix}
1  & -2  & 0\\
0  & 1  & 0\\
0  & 0  & 1\\
\end{pmatrix} =  \begin{pmatrix}
1 & 0 & 6 \\
0 & 1 & 4 
\end{pmatrix}.

Cela s’écrit :

A \begin{pmatrix}
0  & 0  & 1\\
0  & 1  & 0\\
1  & -2  & 0\\
\end{pmatrix} =  \begin{pmatrix}
1 & 0 & 6 \\
0 & 1 & 4 
\end{pmatrix}.

Enfin, vous remplacez la colonne $3$ par elle-même à laquelle vous enlevez quatre fois la colonne $2$ et six fois la colonne $1$, pour conclure :

A \begin{pmatrix}
0  & 0  & 1\\
0  & 1  & 0\\
1  & -2  & 0\\
\end{pmatrix}
\begin{pmatrix}
1  & 0  & -6\\
0  & 1  & -4\\
0  & 0  & 1\\
\end{pmatrix}
 =  \begin{pmatrix}
1 & 0 & 0 \\
0 & 1 & 0 
\end{pmatrix}.

A 
\begin{pmatrix}
0  & 0  & 1\\
0  & 1  & -4\\
1 & -2 & 2
\end{pmatrix}
 =  \begin{pmatrix}
1 & 0 & 0 \\
0 & 1 & 0 
\end{pmatrix}.

Vous notez :

\boxed{P = \begin{pmatrix}
0  & 0  & 1\\
0  & 1  & -4\\
1 & -2 & 2
\end{pmatrix}
}

et remarquez que :

\boxed{AP = \begin{pmatrix}
1 & 0 & 0 \\
0 & 1 & 0 
\end{pmatrix}.}

Calculez l’inverse de la matrice $P$

Vous résolvez le système suivant :

\left\{\begin{align*}
x_3 &= y_1\\
x_2-4x_3&=y_2\\
x_1-2x_2+2x_3&=y_3.
\end{align*}\right.

\left\{\begin{align*}
x_3 &= y_1\\
x_2&=y_2+4x_3\\
x_1-2x_2+2x_3&=y_3.
\end{align*}\right.

\left\{\begin{align*}
x_3 &= y_1\\
x_2&=4y_1+y_2\\
x_1-2x_2+2x_3&=y_3.
\end{align*}\right.

\left\{\begin{align*}
x_3 &= y_1\\
x_2&=4y_1+y_2\\
x_1&=2x_2-2x_3+y_3.
\end{align*}\right.

\left\{\begin{align*}
x_3 &= y_1\\
x_2&=4y_1+y_2\\
x_1&=8y_1+2y_2-2y_1+y_3.
\end{align*}\right.

\left\{\begin{align*}
x_1&=6y_1+2y_2+y_3\\
x_2&=4y_1+y_2\\
x_3 &= y_1.

\end{align*}\right.

La matrice $P$ est inversible et :

\boxed{P^{-1} = \begin{pmatrix}
6  & 2  & 1\\
4  & 1  & 0\\
1 & 0 & 0
\end{pmatrix}.
}

Déduisez-en les valeurs possibles de $a$, $b$ et $c$

De l’égalité :

A\begin{pmatrix}
a\\ b\\ c  
\end{pmatrix} = \begin{pmatrix}
0\\ 0  
\end{pmatrix}

vous forcez l’apparition de la matrice $P$ et de son inverse :

APP^{-1}\begin{pmatrix}
a\\ b\\ c  
\end{pmatrix} = \begin{pmatrix}
0\\ 0  
\end{pmatrix}.

Cela fournit :

\begin{pmatrix}
1 & 0 & 0 \\
0 & 1 & 0 
\end{pmatrix}P^{-1}\begin{pmatrix}
a\\ b\\ c  
\end{pmatrix} = \begin{pmatrix}
0\\ 0  
\end{pmatrix}.

Soient alors $m$, $n$ et $p$ les trois entiers définis par :

\left\{\begin{align*}
 m &=6a+2b+c\\
n&=4a+b\\
p &=a.
\end{align*}
\right.

Vous avez :

\begin{pmatrix}
m\\ n\\ p  
\end{pmatrix} = P^{-1}\begin{pmatrix}
a\\ b\\ c  
\end{pmatrix}.

Donc :

\begin{pmatrix}
1 & 0 & 0 \\
0 & 1 & 0 
\end{pmatrix}\begin{pmatrix}
m\\ n\\ p  
\end{pmatrix} = \begin{pmatrix}
0\\ 0  
\end{pmatrix}.

Si bien que $m=n=0$, ce qui est logique vous retrouvez bien les équations satisfaites par $a$, $b$ et $c.$

Ainsi :

\begin{pmatrix}
0\\ 0\\ p  
\end{pmatrix} = P^{-1}\begin{pmatrix}
a\\ b\\ c  
\end{pmatrix}.

Cela fournit immédiatement :

\begin{pmatrix}
a\\ b\\ c  
\end{pmatrix} = P\begin{pmatrix}
0\\ 0\\ p  
\end{pmatrix} = \begin{pmatrix}
p\\ -4p\\ 2p \end{pmatrix} .

Comme $a = p$ et que $a$, coefficient dominant, est non nul, vous déduisez que $p\neq 0.$

En conclusion de cette analyse, il existe un entier $p$ non nul tel que :

P(X) = p(X^2-4X+2).

Synthèse

Il a été vu que $u^2-4u+2 = 0.$

Ainsi, quel que soit $p\in\ZZ$, $p(u^2-4u+2) = 0.$

Donc quel que soit $p\in\ZZ$ le polynôme $p(X^2-4X+2)$ est bien à coefficients entiers, de degré $2$ et annulateur du réel $2+\sqrt{2}.$

Concluez

Pour tout polynôme $P$ de degré $2$ à coefficients entiers, il y a équivalence entre les propositions suivantes :

• le polynôme $P$ annule le réel $2+\sqrt{2}$ ;
• il existe un entier $p$ non nul tel que $P(X) = p(X^2-4X+2).$

Soit à résoudre l’équation suivante :

4x+3y+2z+7t=15

où les inconnues $x$, $y$, $z$ et $t$ sont des nombres entiers.

Note. Une telle équation est qualifiée de diophantienne.

Utilisez des matrices pour limiter le nombre d’inconnues

Définissez la matrice ligne suivante :

A=\begin{pmatrix}
4& 3& 2& 7
\end{pmatrix}.

Pour tout $(x,y,z,t)\in\Z^4$ vous notez $X$ le vecteur colonne défini par :

X=\begin{pmatrix}
x\\y\\z\\t
\end{pmatrix}.

Enfin, vous notez $B$ la matrice suivante qui ne comporte qu’un seul coefficient :

B = \begin{pmatrix}
15
\end{pmatrix}.

L’équation à quatre inconnues de départ revient à résoudre l’équation suivante :

\boxed{AX=B}

où la seule inconnue est $X.$

Exprimez la matrice $A$ avec des matrices élémentaires

Un objectif premier : faire apparaître le $\mathrm{PGCD}$ des coefficients

Le plus grand diviseur commun des entiers $4$, $3$, $2$ et $7$ est $1.$

Démonstration. En effet, soit $d$ un diviseur commun des entiers $4$, $3$, $2$ et $7.$

Comme $d\mid 7$ et que $7$ est premier vous avez $d\in\{1,7\}.$ Si $d=7$, alors $7\mid 2$ donc $7\leq 2$ ce qui est absurde.

Du coup, $d=1.$

$1$ étant le seul diviseur commun aux quatre entiers $4$, $3$, $2$ et $7$ il vient :

\mathrm{PGCD}(4,3,2,7)=1.\ \blacksquare

Ce PGCD va être placé en haut à gauche, puis va être utilisé pour mettre des zéros.

Une transvection pour le $\mathrm{PGCD}$

Vous souhaitez passer de la matrice $A$ à la matrice suivante :

\begin{pmatrix}
1& 3& 2& 7
\end{pmatrix}.

Cela revient à remplacer la colonne $C_1$ par $C_1-C_2$ au niveau de la matrice $A.$

En effet :

\begin{pmatrix} 4&3&2&7 \end{pmatrix}\begin{pmatrix}
1 & 0 & 0 & 0\\
-1 & 1 & 0 & 0\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1
\end{pmatrix} = \begin{pmatrix} 1&3&2&7 \end{pmatrix}.

Vous déduisez que vous pouvez passer de la matrice $\begin{pmatrix} 1&3&2&5 \end{pmatrix}$ à la matrice $\begin{pmatrix} 4&3&2&7 \end{pmatrix}$, en remplaçant la colonne $C_1$ par la colonne $C_1+C_2.$

En effet :

\begin{pmatrix} 1&3&2&7 \end{pmatrix}\begin{pmatrix}
1 & 0 & 0 & 0\\
1 & 1 & 0 & 0\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1
\end{pmatrix} = \begin{pmatrix} 4&3&2&7 \end{pmatrix}.

Ainsi :

A = \begin{pmatrix} 1&3&2&7 \end{pmatrix}\begin{pmatrix}
1 & 0 & 0 & 0\\
1 & 1 & 0 & 0\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1
\end{pmatrix}.

Une transvection et un premier zéro

Vous allez dans la suite passer de la matrice $\begin{pmatrix} 1&3&2&7 \end{pmatrix}$ à la matrice $\begin{pmatrix} 1&0&2&7 \end{pmatrix}$, ce qui revient à remplacer la colonne $C_2$ par la colonne $C_2-3C_1.$

En effet :

\begin{pmatrix} 1&3&2&7 \end{pmatrix}\begin{pmatrix}
1 & -3 & 0 & 0\\
0 & 1 & 0 & 0\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1
\end{pmatrix} = \begin{pmatrix} 1&0&2&7 \end{pmatrix}.

Vous déduisez que vous pouvez passer de la matrice $\begin{pmatrix} 1&0&2&7 \end{pmatrix}$ à la matrice $\begin{pmatrix} 1&3&2&7 \end{pmatrix}$, en remplaçant la colonne $C_2$ par la colonne $C_2+3C_1.$

Cela donne :

\begin{pmatrix} 1&0&2&7 \end{pmatrix}\begin{pmatrix}
1 & 3 & 0 & 0\\
0 & 1 & 0 & 0\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1
\end{pmatrix} = \begin{pmatrix} 1&3&2&7 \end{pmatrix}.

Du coup :

\begin{align*}
A
&=  

 \begin{pmatrix} 1&3&2&7 \end{pmatrix}\begin{pmatrix}
1 & 0 & 0 & 0\\
1 & 1 & 0 & 0\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1
\end{pmatrix}
\\
&=\begin{pmatrix} 1&0&2&7 \end{pmatrix}\begin{pmatrix}
1 & 3 & 0 & 0\\
0 & 1 & 0 & 0\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1
\end{pmatrix}\begin{pmatrix}
1 & 0 & 0 & 0\\
1 & 1 & 0 & 0\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1
\end{pmatrix}\\
&=\begin{pmatrix} 1&0&2&7 \end{pmatrix}\begin{pmatrix}
4 & 3 & 0 & 0\\
1 & 1 & 0 & 0\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1
\end{pmatrix}. 
\end{align*}

Une transvection et un deuxième zéro

Vous déduisez que vous pouvez passer de la matrice $\begin{pmatrix} 1&0&0&7 \end{pmatrix}$ à la matrice $\begin{pmatrix} 1&0&2&7 \end{pmatrix}$, en remplaçant la colonne $C_3$ par la colonne $C_3+2C_1.$

\begin{pmatrix} 1&0&0&7 \end{pmatrix}\begin{pmatrix}
1 & 0 &2 & 0\\
0 & 1 & 0 & 0\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1
\end{pmatrix} = \begin{pmatrix} 1&0&2&7 \end{pmatrix}.

Du coup :

\begin{align*}
A
&=\begin{pmatrix} 1&0&2&7 \end{pmatrix}\begin{pmatrix}
4 & 3 & 0 & 0\\
1 & 1 & 0 & 0\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1
\end{pmatrix}\\
&=\begin{pmatrix} 1&0&0&7 \end{pmatrix}\begin{pmatrix}
1 & 0 &2 & 0\\
0 & 1 & 0 & 0\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1
\end{pmatrix}\begin{pmatrix}
4 & 3 & 0 & 0\\
1 & 1 & 0 & 0\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1
\end{pmatrix}\\
&=\begin{pmatrix} 1&0&0&7 \end{pmatrix}\begin{pmatrix}
4 & 3 &2 & 0\\
1 & 1 & 0 & 0\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1
\end{pmatrix}.
\end{align*}

Une transvection et un troisième zéro

Vous déduisez que vous pouvez passer de la matrice $\begin{pmatrix} 1&0&0&0 \end{pmatrix}$ à la matrice $\begin{pmatrix} 1&0&0&7 \end{pmatrix}$, en remplaçant la colonne $C_4$ par la colonne $C_4+7C_1.$

\begin{pmatrix} 1&0&0&0 \end{pmatrix}\begin{pmatrix}
1 & 0 &0 & 7\\
0 & 1 & 0 & 0\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1
\end{pmatrix} = \begin{pmatrix} 1&0&0&7 \end{pmatrix}.

Du coup :

\begin{align*}
A
&=\begin{pmatrix} 1&0&0&7 \end{pmatrix}\begin{pmatrix}
4 & 3 &2 & 0\\
1 & 1 & 0 & 0\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1
\end{pmatrix}\\
&=\begin{pmatrix} 1&0&0&0 \end{pmatrix}\begin{pmatrix}
1 & 0 &0 & 7\\
0 & 1 & 0 & 0\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1
\end{pmatrix} \begin{pmatrix}
4 & 3 &2 & 0\\
1 & 1 & 0 & 0\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1
\end{pmatrix}\\
&=\begin{pmatrix} 1&0&0&0 \end{pmatrix}\begin{pmatrix}
4 & 3 &2 & 7\\
1 & 1 & 0 & 0\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1
\end{pmatrix}.
\end{align*}

Pour la suite, vous posez :

\boxed{\begin{align*}
S &= \begin{pmatrix} 1&0&0&0 \end{pmatrix}\\
Q &= \begin{pmatrix}
4 & 3 & 2 & 7\\
1 & 1 & 0 & 0\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1
\end{pmatrix}.
\end{align*}
}

Alors :

\boxed{A = SQ.}

Montrez que la matrice $Q$ est inversible et que les coefficients de $Q^{-1}$ sont des entiers

La matrice $Q$ est le produit de quatre matrices de transvection qui ont pour déterminant $1.$ Ainsi, par produit des déterminants, $\det Q = 1.$ Comme $\det Q \neq 0$, la matrice $Q\in M_4(\Q)$ est inversible.

Comme $\det (Q)\times \det(Q^{-1}) = 1$ il vient $\det(Q^{-1})=1.$ Utilisant la comatrice de $Q$ notée $Q^{*}$, vous avez :

Q^{-1} = \det (Q^{-1})\  ^{t}(Q^{*}) = ^{t}(Q^{*}).

Or, comme $Q$ est à coefficients entiers, il en est de même de $Q^{*}$ donc de $^{t} Q^{*}.$

Donc $Q^{-1}$ est à coefficients entiers.

Calculez la matrice $Q^{-1}$

Quels que soit $(x_1,x_2,x_3,x_4)\in\Q^4$ et quels que soit $(y_1,y_2,y_3,y_4)\in\Q^4$ :

\begin{align*}

Q\begin{pmatrix}
x_1\\
x_2\\
x_3\\
x_4
\end{pmatrix}=
\begin{pmatrix}
y_1\\
y_2\\
y_3\\
y_4
\end{pmatrix}
&\Longleftrightarrow
\left\{\begin{array}{lllll}
4x_1 &+3x_2 &+2x_3 &+ 7x_4 &= y_1\\
\hphantom{4}x_1&+\hphantom{3}x_2&&&=y_2\\
&&\hphantom{+2}x_3&&=y_3\\
&&&\hphantom{+7}x_4&=y_4\\
\end{array}
\right.
\\
&\Longleftrightarrow
\left\{\begin{array}{lllll}
\hphantom{4}x_1&+\hphantom{3}x_2&&&=y_2\\
4x_1 &+3x_2 &+2x_3 &+ 7x_4 &= y_1\\
&&\hphantom{+2}x_3&&=y_3\\
&&&\hphantom{+7}x_4&=y_4\\
\end{array}
\right.
\\
&\Longleftrightarrow
\left\{\begin{array}{lllll}
\hphantom{4}x_1&+\hphantom{3}x_2&&&=y_2\\
 &-\hphantom{3}x_2 &+2x_3 &+ 7x_4 &= y_1-4y_2\\
&&\hphantom{+2}x_3&&=y_3\\
&&&\hphantom{+7}x_4&=y_4\\
\end{array}
\right.
\\
&\Longleftrightarrow
\left\{\begin{array}{ll}
x_1&=y_2-x_2\\
x_2&=2x_3+7x_4-y_1+4y_2 \\
x_3&=y_3\\
x_4 &= y_4
\end{array}
\right.
\\
&\Longleftrightarrow
\left\{\begin{array}{ll}
x_1&=y_2-x_2\\
x_2&=2y_3+7y_4-y_1+4y_2 \\
x_3&=y_3\\
x_4 &= y_4
\end{array}
\right.
\\
&\Longleftrightarrow
\left\{\begin{array}{ll}
x_1&=y_2-x_2\\
x_2&=-y_1+4y_2+2y_3+7y_4 \\
x_3&=y_3\\
x_4 &= y_4
\end{array}
\right.
\\
&\Longleftrightarrow
\left\{\begin{array}{ll}
x_1&=y_2+y_1-4y_2-2y_3-7y_4\\
x_2&=-y_1+4y_2+2y_3+7y_4 \\
x_3&=y_3\\
x_4 &= y_4
\end{array}
\right.
\\
&\Longleftrightarrow
\left\{\begin{array}{ll}
x_1&=y_1-3y_2-2y_3-7y_4\\
x_2&=-y_1+4y_2+2y_3+7y_4 \\
x_3&=y_3\\
x_4 &= y_4
\end{array}
\right.
\\
&\Longleftrightarrow
\begin{pmatrix}
x_1\\
x_2\\
x_3\\
x_4
\end{pmatrix}=\begin{pmatrix}
1&-3&-2&-7\\
-1 & 4 & 2 & 7\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1
\end{pmatrix}
\begin{pmatrix}
y_1\\
y_2\\
y_3\\
y_4
\end{pmatrix}
\end{align*}

Du coup :

Q^{-1} = \begin{pmatrix}
1&-3&-2&-7\\
-1 & 4 & 2 & 7\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1
\end{pmatrix}.

Résolvez l’équation $4x + 3y + 2z + 7t = 15$ pour $(x,y,z,t)\in\Z^4$

Analyse

Soit $(x,y,z,t)\in\Z^4$ tel que $4x+3y+2z+7t=15.$

Vous posez :

X'=QX=\begin{pmatrix}
4x+3y+2z+7t\\x+y\\z\\t
\end{pmatrix}.

Posez encore :

\left\{\begin{align*}
x' &= 4x+3y+2z+7t\\
y'&=x+y\\
z'&=z\\
t'&=t.
\end{align*}\right.

Remarquez que $(x’,y’,z’,t’)\in\Z^4.$

Vous déduisez successivement :

\begin{array}{l}
AX=B\\
SQX=B\\
SX'=B\\
\begin{pmatrix}
1 & 0 & 0 & 0
\end{pmatrix}\begin{pmatrix}
x'\\y'\\z'\\t'
\end{pmatrix} = \begin{pmatrix}
15
\end{pmatrix}
\\
x'=15
\\
X'=\begin{pmatrix}
15\\y'\\z'\\t'
\end{pmatrix}
\\
QX=\begin{pmatrix}
15\\y'\\z'\\t'
\end{pmatrix}\\
X = Q^{-1} \begin{pmatrix}
15\\y'\\z'\\t'
\end{pmatrix}
\\
X = \begin{pmatrix}
1&-3&-2&-7\\
-1 & 4 & 2 & 7\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1
\end{pmatrix}\begin{pmatrix}
15\\y'\\z'\\t'
\end{pmatrix}
\\
X = \begin{pmatrix}
15-3y'-2z'-7t'\\
-15+4y'+2z'+7t'\\
z'\\
t'
\end{pmatrix}.
\end{array}

En définitive, il existe trois entiers relatifs $m$, $n$ et $p$ tels que :

\left\{\begin{align*}
x&=15-3m-2n-7p\\
y&=-15+4m+2n+7p\\
z&=n\\
t&=p.
\end{align*}
\right.

Synthèse

Soit $(m,n,p)\in\Z^3.$

Vous posez :

\left\{\begin{align*}
x&=15-3m-2n-7p\\
y&=-15+4m+2n+7p\\
z&=n\\
t&=p.
\end{align*}
\right.

Alors :

\begin{align*}
4x+3y+2z+7t &= 4(15-3m-2n-7p)\\
&\qquad+3(-15+4m+2n+7p)\\
&\qquad +2n+7p\\
&=60-12m-8n-28p\\
&\qquad -45+12m+6n+21p\\
&\qquad+2n+7p\\
&=15.
\end{align*}

Concluez

\boxed{\forall (x,y,z,t)\in\Z^4,\ 4x+3y+2z+7t=15 \Longleftrightarrow 
\left[
\exists(m,n,p)\in\Z^3, \left\{\begin{align*}
x&=15-3m-2n-7p\\
y&=-15+4m+2n+7p\\
z&=n\\
t&=p
\end{align*}
\right.
\right].
}

Grâce aux contenus rédigés dans l'article 298 et dans l'article 297, il est possible d’aborder la méthode de Toepler qui date de 1865.

Vous vous attachez dans cet article à trouver le reste et la racine carrée entière du nombre suivant :

a=352621.

Afin de limiter le nombre de soustractions il est commode d’écrire $a$ par paquet de deux chiffres :

a=35\ 26\ 21.

Vous allez déterminer le reste et la racine carrée entière de $35$ puis de $35\ 26$ et enfin de $35\ 26\ 21.$

Première étape : racine carrée entière et reste de $35$

Vous effectuez la série de soustractions suivantes :

\begin{align*}
35 - 1 &= 34\\
34- 3&= 31\\
31-5&= 26\\
26-7&=19\\
19-9&=10\\
10-11 &= -1.
\end{align*}

Vous prenez l’avant-dernière ligne et repérez le nombre impair $9$ qui est retranché. Vous effectuez :

\frac{9+1}{2} = 5.

Remarquez aussi que ce nombre correspond au nombre de soustractions effectuées avant d’obtenir un résultat strictement négatif.

Donc la racine carrée entière de $35$ est $5.$ Le reste apparaît comme étant le dernier résultat positif des soustractions. Vous le lisez à l’avant-dernière ligne, il vaut $10.$

Ainsi :

\begin{align*}
35 &= 5^2+10\\
10&\in\llbracket 0, 10\rrbracket.
\end{align*}

Deuxième étape : racine carrée entière et reste de $35\ 26$

Vous utilisez le fait que :

\begin{align*}
35\ 26 &= 35\times 100+26 \\
&=(5^2+10)\times 100+26\\
&=5^2\times 100 + 10\times 100+26\\
&=5^2\times 10^2+ 1026\\
&=50^2+1026.
\end{align*}

Comme $1026\notin \llbracket 0, 100\rrbracket$, vous déduisez que $50$ n’est pas la racine carrée entière de $3526.$

Il a été vu dans le contenu rédigé dans l'article 298 que, si vous considérez la suite $(u_n)_{n\geq 0}$ définie par :

\begin{array}{l}
u_0 = 3526\\
\forall n\in\N, u_{n+1} = u_n-(2n+1)
\end{array}

alors il existe un entier $q$ non nul qui est le rang minimum à partir duquel vous avez $u_q<0.$

La racine carrée entière de $3526$ est alors égale à $q-1.$

Or, la suite $(u_n)_{n\geq 0}$ vérifie la propriété suivante :

\forall n\in\N, 3526=n^2+u_n.

En effectuant $n=50$, vous déduisez :

3526=50^2+u_{50}.

Or :

3526 = 50^2+1026.

Vous déduisez donc :

u_{50} = 1026.

Vous avez donc économisé un grand nombre de soustractions sur la suite $(u_n)_{n\geq 0}.$

Vous poursuivez maintenant les soustractions.

Comme $u_{51} = u_{50} – 101$ il vient ce qui suit.

\begin{align*}
1026 - 101 &=925\\
925 - 103 &=822\\
822-105 &=717\\
717-107 &=610\\
610-109 &=501\\
501-111 &=390\\
390-113&=277\\
277-115&=162\\
162-117&=45\\
45-119&=-74.
\end{align*}

L’avant-dernier nombre impair est $117.$

\frac{117+1}{2}=\frac{118}{2}=59.

Cela revient à dire que $u_{59} = 45.$

Donc :

3526 = 59^2+45.

Comme $45\in \llbracket 0, 118\rrbracket$ vous déduisez que $59$ est la racine carrée entière de $3526$ et que $45$ est le reste.

Dernière étape : racine carrée entière et reste de $35\ 26\ 21$

Vous reprenez le raisonnement de la deuxième étape.

\begin{align*}
35\ 26\ 21 &= 3526\times 100 + 21\\
&=(59^2+45)\times 100+21\\
&=59^2\times 10^2+4521\\
&=590^2+4521.
\end{align*}

Afin de ne pas alourdir les notations, vous redéfinissez la suite $(u_n)_{n\geq 0}$ en posant :

\begin{array}{l}
u_0 = 352621\\
\forall n\in\N, u_{n+1} = u_n-(2n+1).
\end{array}

L’égalité précédente prouve que $u_{590} = 4521.$

Vous avez donc $u_{591} = u_{590}- 1181.$

Vous aurez remarqué que le nombre impair $1181$ s’obtient en doublant le nombre $59$ soit $118$, et en « collant » le chiffre $1$ à droite. Cela revient à effectuer l’opération $59\times 2\times 10+1$ ce qui est exactement $2\times 590+1.$

Vous calculez les termes suivants de la suite $(u_n)_{n\geq 0}$ à partir du rang $591$ :

\begin{align*}
4521 - 1181 &= 3340\\
3340 - 1183 &=2157\\
2157-1185 &= 972\\
972-1187&=-215.
\end{align*}

Pour trouver le rang de la suite $(u_n)_{n\geq 0}$ associé au terme $972$, il suffit de prendre le nombre impair retranché à l’avant-dernière ligne, puis d’effectuer ce calcul :

\frac{1185+1}{2} = \frac{1186}{2}=593.

Ainsi, $u_{593} = 785.$

Vous déduisez donc :

352621=593^2+972.

Comme $972\in\llbracket 0, 1186\rrbracket$ vous concluez.

La racine carrée entière de $352621$ est égale à $593$ et son reste est $972.$

Un exemple amélioré

Soit à calculer la racine carrée entière de $p = 7569.$

Vous exprimez ce nombre par tranche de deux chiffres : $p=75\ 69.$

Connaissant la liste de vos carrés de $1$ à $10$ vous notez que $7^2 = 49$, $8^2 = 64$ et $9^2 = 81.$

Donc $75 = 8^2+r$ où $r = 75-64 = 11.$ Comme $r\in\llbracket 0, 16\rrbracket$ vous avez trouvé la racine carrée entière ainsi que le reste de $75$ :

75 = 8^2+11.

En multipliant par $100$ vous déduisez :

7500 = 80^2+1100.

En ajoutant $69$ il vient :

7569 = 80^2+1169.

Vous effectuez maintenant des soustractions en partant du double de $80$ auquel vous ajoutez $1$ ce qui donne $161.$

\begin{array}{l|l}
1169 - 161 = 1008 & 7569 = 81^2+1008\\
1008 - 163 =845& 7569 = 82^2+845\\
845-165 =680& 7569 = 83^2+680\\
680-167=513& 7569 = 84^2+513\\
513-169=344& 7569 = 85^2+344\\
344-171=173& 7569 = 86^2+173\\
173-173=0 & 7569 = 87^2.
\end{array}

Le nombre $7569$ est un carré parfait puisque le reste est nul. C’est le carré de $87.$