Catégorie : Niveau Prépa

Cet exposé fournit la suite de l’analyse se trouvant dans le contenu rédigé dans l'article 367 il en est la synthèse.

Vous fixez un nombre entier $b$ supérieur ou égal à $2.$ Soit $x$ un nombre réel strictement compris entre $0$ et $1.$

Vous définissez une suite $(c_i)_{i\geq 1}$ en posant :

\left\{\begin{align*}
&c_1 =  \lfloor bx \rfloor\\
&\forall n\in \N \setminus \{0,1\}, \quad c_n = \lfloor b^n x \rfloor - b \lfloor b^{n-1} x \rfloor.
\end{align*}
\right.

Démontrez que pour tout $i\geq 1, 0\leq c_i\leq b-1$

Le cas de $c_1$

Comme $x$ et $b$ sont positifs, vous avez $0\leq bx.$ Comme $0$ est un entier inférieur ou égal à $bx$ il est nécessairement inférieur à $\lfloor b x \rfloor$ ce qui donne $0\leq \lfloor b x \rfloor$ et $0\leq c_1.$

La partie entière de $bx$ est inférieure ou égale à $bx$ d’où :

\lfloor b x \rfloor \leq bx.

Or, $x$ est strictement inférieur à $1$ et $b$ est strictement positif, donc $bx < b.$ Du coup $\lfloor b x \rfloor < b.$ Comme $\lfloor b x \rfloor$ et $b$ sont deux entiers, il vient $\lfloor b x \rfloor \leq b-1$ et finalement $c_1\leq b-1.$

La double inégalité $\boxed{0\leq c_1\leq b-1}$ est satisfaite.

Le cas de $c_n$ lorsque $n\geq 2$

Soit $n$ un entier supérieur ou égal à $2.$

Par définition :

c_n = \lfloor b^n x \rfloor- b \lfloor b^{n-1} x \rfloor.

D’une part $\lfloor b^{n-1} x \rfloor \leq b^{n-1}x.$ En multipliant par $b$ qui est strictement positif, vous déduisez :

b \lfloor b^{n-1} x \rfloor \leq b^nx.

Le nombre entier $b \lfloor b^{n-1} x \rfloor$ est inférieur ou égal à $b^nx$ donc il vient :

b \lfloor b^{n-1} x \rfloor\leq \lfloor b^n x \rfloor.

Vous en déduisez que $0\leq c_n.$

D’autre part vous avez :

\left\{\begin{align*}
&\lfloor b^n x \rfloor \leq b^nx \\
 &b^{n-1}x < \lfloor b^{n-1} x \rfloor +1.
\end{align*}
\right.

Cela devient :

\left\{\begin{align*}
&\lfloor b^n x \rfloor \leq b^nx \\
 &- \lfloor b^{n-1} x \rfloor   < 1-b^{n-1}x.
\end{align*}
\right.

En multipliant la seconde inégalité par $b$ qui est strictement positif :

\left\{\begin{align*}
&\lfloor b^n x \rfloor \leq b^nx \\
 &- b \lfloor b^{n-1} x \rfloor   < b-b^n x.
\end{align*}
\right.

Par somme de deux inégalités dont l’une est stricte, vous obtenez une inégalité stricte :

\lfloor b^n x \rfloor- b \lfloor b^{n-1} x \rfloor < b.

Comme $\lfloor b^n x \rfloor- b \lfloor b^{n-1} x$ et $b$ sont deux entiers, vous avez :

\lfloor b^n x \rfloor- b \lfloor b^{n-1} x \rfloor \leq b-1.

Du coup, $c_n \leq b-1.$

En définitive :

\boxed{\forall n\in\N, n\geq 2 \implies 0\leq c_n\leq b-1.}

Vers la série $\sum_{i\geq 1}\frac{c_i}{b^i}$

ll a été vu que la série $\sum_{i\geq 1}\frac{c_i}{b^i}$ est à termes positifs et que, d’après le calcul effectué dans le contenu rédigé dans l'article 367, toutes ses sommes partielles sont majorées par $1.$ La série précitée est bien convergente.

Une double inégalité avec $c_1$

Vous avez $c_1 = \lfloor b x \rfloor.$

L’encadrement $\lfloor b x \rfloor \leq bx < \lfloor b x \rfloor +1$ fournit :

c_1 \leq bx < c_1+1.

En divisant par $b$ qui est strictement positif, vous avez :

\frac{c_1}{b}\leq x < \frac{c_1}{b}+\frac{1}{b}.

Une double inégalité avec $c_2$

Comme $c_1 = \lfloor b x \rfloor$ donc après multiplication par $b$ qui est strictement positif :

b c_1 =b\lfloor b x \rfloor.

Vous avez :

c_2 = \lfloor b^2 x \rfloor - b\lfloor b x \rfloor

Par somme :

\begin{align*}
bc_1+c_2= \lfloor b^2 x \rfloor.
\end{align*} 

Or, vous avez la double inégalité :

\lfloor b^2 x \rfloor \leq b^2x < \lfloor b^2 x \rfloor+1.

Il en résulte que :

bc_1+c_2 \leq b^2 x < bc_1+c_2+1.

En divisant par $b^2$ qui est strictement positif, il vient :

\frac{c_1}{b} +\frac{c_2}{b^2}\leq x< \frac{c_1}{b}+\frac{c_2}{b^2}+\frac{1}{b^2}

Une double inégalité dans le cas général

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

\begin{align*}
\sum_{k=1}^n b^{n-k}c_k &= b^{n-1}c_1+\sum_{k=2}^n b^{n-k}c_k\\
&= b^{n-1}c_1+\sum_{k=2}^n b^{n-k}\left(\lfloor b^k x \rfloor - b\lfloor b^{k-1} x \rfloor\right)\\
&= b^{n-1}\lfloor b x \rfloor+\sum_{k=2}^n b^{n-k}\lfloor b^k x \rfloor - \sum_{k=2}^n b^{n-k+1}\lfloor b^{k-1} x \rfloor\\
&= b^{n-1}\lfloor b x \rfloor+\sum_{k=2}^n b^{n-k}\lfloor b^k x \rfloor - \sum_{k=1}^{n-1} b^{n-k}\lfloor b^{k} x \rfloor\\
&= b^{n-1}\lfloor b x \rfloor+\lfloor b^n x \rfloor+\sum_{k=2}^{n-1} b^{n-k}\lfloor b^k x \rfloor - \sum_{k=2}^{n-1} b^{n-k}\lfloor b^{k} x \rfloor - b^{n-1}\lfloor b x \rfloor\\
&=\lfloor b^n x \rfloor.
\end{align*}

Vous avez :

\lfloor b^n x \rfloor \leq b^n x < \lfloor b^n x \rfloor+1.

Du coup :

\sum_{k=1}^n b^{n-k}c_k \leq b^n x < \sum_{k=1}^n b^{n-k}c_k+1.

En divisant par $b^n$ qui est strictement positif, vous avez :

\sum_{k=1}^n b^{-k}c_k \leq x < \sum_{k=1}^n b^{-k}c_k+\frac{1}{b^n}.

Autrement dit :

\sum_{k=1}^n \frac{c_k}{b^k} \leq x < \sum_{k=1}^n \frac{c_k}{b^k}+\frac{1}{b^n}.

Concluez

Il a été démontré que :

\forall n\in\NN, \sum_{k=1}^n \frac{c_k}{b^k} \leq x < \sum_{k=1}^n \frac{c_k}{b^k}+\frac{1}{b^n}.

Comme $b>1$ vous avez $\lim_{n\to +\infty} \frac{1}{b^n} = 0.$

De l’encadrement $\forall n\in\NN, 0\leq x – \sum_{k=1}^n \frac{c_k}{b^k} < \frac{1}{b^n}$ et du théorème des gendarmes, vous avez $\lim_{n\to +\infty} \sum_{k=1}^n \frac{c_k}{b^k} = x.$

Autrement dit $\boxed{x = \sum_{k=1}^{+\infty} \frac{c_k}{b^k}.}$

Le nombre $x$ a été développé en base $b.$ Il reste encore un point à démontrer.

Justifiez que le développement obtenu est propre

Vous raisonnez par l’absurde en supposant qu’il existe un entier $N\in\NN$ tel que pour tout $n\geq N, c_n = b-1.$

Vous avez $x = \sum_{k=1}^{+\infty} \frac{c_k}{b^k}.$

Le cas où $N=1$

Vous avez $\forall n\in\NN, c_n = b-1$ du coup :

\begin{align*}
x &= \sum_{k=1}^{+\infty} \frac{b-1}{b^k}\\
&= (b-1) \sum_{k=1}^{+\infty} \left(\frac{1}{b}\right)^k\\
&=\frac{b-1}{b} \sum_{k=0}^{+\infty} \left(\frac{1}{b}\right)^k\\
&= \frac{b-1}{b} \times \frac{1}{1-\frac{1}{b}}\\
&=\frac{b-1}{b}\times \frac{b}{b-1}\\
&=1.
\end{align*} 

Ce est absurde puisque $x$ est strictement inférieur à $1.$

Le cas où $N\geq 2$

Vous calculez $x$ et observez ce qui suit :

\begin{align*}
x &= \sum_{k=1}^{N-1} \frac{c_k}{b^k} + \sum_{k=N}^{+\infty} \frac{c_k}{b^k}\\
&=\sum_{k=1}^{N-1} \frac{c_k}{b^k} + \sum_{k=N}^{+\infty} \frac{b-1}{b^k}\\
&=\sum_{k=1}^{N-1} \frac{c_k}{b^k} + (b-1) \sum_{k=N}^{+\infty} \frac{1}{b^k}\\
&=\sum_{k=1}^{N-1} \frac{c_k}{b^k} + (b-1) \sum_{k=N}^{+\infty} \left(\frac{1}{b}\right)^k\\
&=\sum_{k=1}^{N-1} \frac{c_k}{b^k} + \frac{b-1}{b^N} \sum_{k=0}^{+\infty} \left(\frac{1}{b}\right)^k\\
&=\sum_{k=1}^{N-1} \frac{c_k}{b^k} + \frac{b-1}{b^N} \times \frac{1}{1-\frac{1}{b}}\\
&=\sum_{k=1}^{N-1} \frac{b^{N-1-k}c_k}{b^{N-1}} +  \frac{b-1}{b^N} \times \frac{b}{b-1}\\
&= \frac{\sum_{k=1}^{N-1} b^{N-1-k}c_k}{b^{N-1}} +  \frac{1}{b^{N-1}} \\
&= \frac{1+\sum_{k=1}^{N-1} b^{N-1-k}c_k}{b^{N-1}}.
\end{align*} 

Vous posez $A = 1+\sum_{k=1}^{N-1} b^{N-1-k}c_k$ qui est un nombre entier et vous avez $x = \frac{A}{b^{N-1}}.$

Par définition :

\begin{align*}
c_N &= \lfloor b^N x \rfloor - b \lfloor b^{N-1} x \rfloor\\
&= \lfloor b\times b^{N-1} x \rfloor - b \lfloor b^{N-1} x \rfloor.
\end{align*} 

Comme $b^{N-1}x = A$ vous avez :

c_N =  \lfloor b\times A  \rfloor - b \lfloor A \rfloor.

Comme $A$ est entier, $A = \lfloor A \rfloor.$ De même $b\times A$ est entier donc $\lfloor b\times A \rfloor = bA.$

Du coup :

c_N = bA - bA = 0.

Or, $c_N = b-1$ d’où $b-1 = 0$ et $b=1$ contradiction, vu que la base $b$ est un entier supérieur ou égal à $2.$

Conclusion finale

Soit $b$ un entier supérieur ou égal à $2$ appelé base.

Tout réel $x$ strictement compris entre $0$ et $1$ admet un développement propre en base $b$. Il a été justifié dans le contenu rédigé dans l'article 367 qu’un tel développement, s’il existe pour un tel $x$ est unique.

Plus précisément, soit $x$ un réel tel que $0<x<1.$

Vous posez :

\boxed{\left\{\begin{align*}
&c_1 =  \lfloor bx \rfloor\\
&\forall n\in \N \setminus \{0,1\}, \quad c_n = \lfloor b^n x \rfloor - b \lfloor b^{n-1} x \rfloor.
\end{align*}
\right.}

Alors vous avez ce qui suit :

\boxed{\left\{\begin{align*}
&\forall i\in \NN, 0\leq c_i \leq b-1 \\
&\forall N\in\NN, \exists n\geq N, c_n\neq b-1.
\end{align*}
\right.}

De plus, la série $\sum_{i\geq 1}\frac{c_i}{b^i}$ est convergente et sa somme est égale à ce qui suit :

\boxed{\sum_{i=1}^{+\infty}\frac{c_i}{b^i}=x.}

Dans cet exposé, $x$ désigne un nombre réel strictement compris entre $0$ et $1$ et $b$ un nombre entier supérieur ou égal à $2$ appelé base. Pour tout réel $t$ la notation $\lfloor t \rfloor$ désigne la partie entière de $t$, à savoir le plus grand entier inférieur ou égal à $t.$

Le cas où $b=10$

Certains nombres réels « tombent juste », autrement dit ils peuvent s’écrire avec un nombre fini de chiffres après la virgule.

C’est le cas par exemple de $\frac{1}{4}$ qui admet $0,25$ en écriture décimale. Cela signifie qu’il est égal à deux dixièmes plus cinq centièmes, soit :

\frac{1}{4} = \frac{2}{10}+\frac{5}{100}.

D’autres nombres réels ne pourront jamais s’écrire avec une écriture décimale finie. C’est le cas par exemple de $\frac{1}{3}.$

Note. Le lecteur est invité à démontrer ce résultat.

On note cependant que, pour tout entier $k\geq 3$, la somme $S_k$ ci-dessous forme une somme de termes en progression géométrique de raison $\frac{1}{10}$ où :

S_k = \frac{3}{10}+\frac{3}{100}+\dots+\frac{3}{10^{k-1}}+\frac{3}{10^k}.

Or, $10S_k$ est égal à :

10S_k = 3+\frac{3}{10}+\cdots+\frac{3}{10^{k-1}}.

Vous obtenez donc par différence :

\begin{align*}
10S_k-S_k &= 3-\frac{3}{10^k}\\
9S_k &= 3-\frac{3}{10^k}\\
S_k &= \frac{1}{3}-\frac{1}{3\times 10^k}.
\end{align*} 

Il en résulte que :

\lim_{k\to +\infty} S_k = \frac{1}{3}.

Autrement dit :

\lim_{k\to +\infty} \sum_{i=1}^k\frac{3}{10^i} = \frac{1}{3}.

Cette écriture se note aussi :

\boxed{\frac{1}{3} = \sum_{i=1}^{+\infty}\frac{3}{10^i}.}

Plus généralement, vous allez démontrer dans ce qui suit que, même si la base $b$ n’est pas égale à $10$, $x$ admet nécessairement un développement propre dans cette base.

Analyse du cas général

Vous supposez que $x$ admet un développement propre en base $b$, autrement dit vous supposez qu’il existe une suite $(c_i)_{i\geq 1}$ telle que :

\left\{\begin{align*}
&\forall i\in \NN, 0\leq c_i \leq b-1 \\
&\forall N\in\NN, \exists n\geq N, c_n\neq b-1\\
&x = \sum_{i=1}^{+\infty}\frac{c_i}{b^i}.
\end{align*}
\right.

Note. La condition $\forall i\in \NN, 0\leq c_i \leq b-1$ signifie que le développement décimal en base $b$ se fait uniquement avec des chiffres. En base $10$, le développement décimal n’utilise que les chiffres $0, 1, \dots, 9.$

Note. La condition $\forall N\in\NN, \exists n\geq N, c_n\neq b-1$ signifie qu’il est impossible que le développement proposé soit impropre : autrement dit, il existe une infinité de chiffres différents de $b-1$ dans le développement. Si cette condition n’était pas remplie, il existerait un rang à partir duquel tous les chiffres seraient égaux à $b-1.$ En base $10$, le nombre $\frac{1}{4}$ admet le développement décimal impropre $0,249999\dots$ avec une infinité de $9$ ce que vous souhaitez éviter.

Note. Avant d’écrire que $x = \sum_{i=1}^{+\infty}\frac{c_i}{b^i}$ vous allez expliquer pourquoi la série $\sum_{i\geq 1} \frac{c_i}{b^i}$ est convergente sous l’hypothèse des deux conditions précédentes.

La série $\sum_{i\geq 1} \frac{c_i}{b^i}$ est à termes positifs. Pour tout entier $i\geq 1$ vous avez $c_i\leq b-1.$ Pour tout entier $N\geq 1$ vous avez la majoration :

\begin{align*}
\sum_{i= 1}^N \frac{c_i}{b^i} &\leq (b-1) \sum_{i= 1}^N \frac{1}{b^i} \\
& \leq (b-1) \sum_{i= 1}^N b^{-i} \\
& \leq \frac{b-1}{b^N} \sum_{i= 1}^N b^{N-i} \\
& \leq \frac{b-1}{b^N} \sum_{j= 0}^{N-1} b^{j} \\
& \leq \frac{b-1}{b^N}\times \frac{1-b^N}{1-b} \\
& \leq \frac{b^N-1}{b^N} \\
&< \frac{b^N}{b^N}\\
&\leq 1.
\end{align*}

Les sommes partielles de cette série étant majorées par $1$, cette série est bien convergente.

Vous allez démontrer dans cette analyse que pour tout $i\geq 1$, $c_i$ ne dépend que de $x$ et de $b.$

Le cas de $c_1$

Comme $x = \sum_{i=1}^{+\infty}\frac{c_i}{b^i}$ vous déduisez en isolant le premier terme de cette somme que :

x =\frac{c_1}{b} + \sum_{i=2}^{+\infty}\frac{c_i}{b^i}.

En multipliant par $b$, vous obtenez :

\begin{align*}
bx& = c_1 + \sum_{i=2}^{+\infty}\frac{bc_i}{b^i}\\
& = c_1 + \sum_{i=2}^{+\infty}\frac{c_i}{b^{i-1}}\\
& = c_1 + \sum_{i=1}^{+\infty}\frac{c_{i+1}}{b^{i}}.
\end{align*}

Pour tout $i\geq 1$, $c_{i+1}$ est positif ou nul donc $c_1\leq bx.$ $c_1$ est donc un entier inférieur ou égal à $bx.$ Comme $\lfloor bx \rfloor$ est le plus grand entier inférieur ou égal à $bx$, il vient $c_1 \leq \lfloor bx \rfloor.$

Etudiez maintenant la somme $\sum_{i=1}^{+\infty}\frac{c_{i+1}}{b^{i}}.$ Notez tout d’abord qu’il existe un entier $m\geq 3$ tel que $c_{m} \neq b-1$ donc $c_m \leq b-2.$ Vous posez $n = m-1$ si bien que $n\geq 2$ et $c_{n+1} \leq b-2.$

Vous avez l’égalité :

\sum_{i=1}^{+\infty}\frac{c_{i+1}}{b^{i}}  =  \sum_{i=1}^{n-1}\frac{c_{i+1}}{b^{i}} + \frac{c_{n+1}}{b^n} + \sum_{i=n+1}^{+\infty}\frac{c_{i+1}}{b^{i}}

En majorant :

\begin{align*}
\sum_{i=1}^{+\infty}\frac{c_{i+1}}{b^{i}}  &\leq  \sum_{i=1}^{n-1}\frac{b-1}{b^{i}} + \frac{b-2}{b^n} + \sum_{i=n+1}^{+\infty}\frac{b-1}{b^{i}} \\
&<  \sum_{i=1}^{n-1}\frac{b-1}{b^{i}} + \frac{b-1}{b^n} + \sum_{i=n+1}^{+\infty}\frac{b-1}{b^{i}} \\
&\leq  (b-1)\sum_{i=1}^{+\infty}\frac{1}{b^{i}} \\
&\leq  \frac{b-1}{b}\times \sum_{i=0}^{+\infty}\left(\frac{1}{b}\right)^i \\
&\leq  \frac{b-1}{b}\times \frac{1}{1-\frac{1}{b}} \\
&\leq  \frac{b-1}{b}\times \frac{b}{b-1} \\
&\leq 1.
\end{align*}

Il a été obtenu, en tenant compte de l’inégalité stricte présente, que :

\sum_{i=1}^{+\infty}\frac{c_{i+1}}{b^{i}}<1.

Donc :

bx < c_1+1.

Il a été établi que $c_1 \leq \lfloor bx \rfloor.$ Si $c_1\neq \lfloor bx \rfloor$ alors $c_1 < \lfloor bx \rfloor$ du coup $1+c_1 \leq \lfloor bx \rfloor$ vu que $c_1$ et $\lfloor bx \rfloor$ sont des entiers. D’autre part $\lfloor bx \rfloor$ est inférieur ou égal à $bx$ d’où $1+c_1 \leq bx$ ce qui contredit le résultat obtenu avec l’analyse de la somme infinie.

Du coup, comme annoncé, $c_1$ ne dépend que de $x$ et de $b$ et vous avez :

\boxed{c_1 = \lfloor bx \rfloor.}

Le cas de $c_2$

Comme $x = \sum_{i=1}^{+\infty}\frac{c_i}{b^i}$ vous obtenez :

b^2x =bc_1+c_2+ \sum_{i=1}^{+\infty}\frac{c_{i+2}}{b^i}.

En reprenant une démarche similaire à celle adoptée précédemment, vous avez $0\leq \sum_{i=1}^{+\infty}\frac{c_{i+2}}{b^i} < 1$ vu que le développement décimal est propre.

Du coup, $bc_1+c_2 = \lfloor b^2x \rfloor$ si bien que $c_2 = \lfloor b^2x \rfloor – bc_1 $ et finalement :

\boxed{c_2 =  \lfloor b^2x \rfloor - b \lfloor bx \rfloor.}

Le cas de $c_3$

Comme $x = \sum_{i=1}^{+\infty}\frac{c_i}{b^i}$ vous obtenez :

b^3x =b^2c_1+bc_2+ c_3+\sum_{i=1}^{+\infty}\frac{c_{i+3}}{b^i}.

En reprenant une démarche similaire à celle adoptée précédemment, vous avez $0\leq \sum_{i=1}^{+\infty}\frac{c_{i+3}}{b^i} < 1$ vu que le développement décimal est propre.

Du coup, $b^2c_1+bc_2 +c_3 = \lfloor b^3x \rfloor$ si bien que :

\begin{align*}
c_3 &= \lfloor b^3x \rfloor- b^2c_1-bc_2\\
&=  \lfloor b^3x \rfloor - b^2 \lfloor bx \rfloor - b( \lfloor b^2x \rfloor - b \lfloor bx \rfloor)\\
&=   \lfloor b^3x \rfloor- b^2 \lfloor bx \rfloor - b \lfloor b^2x \rfloor + b^2 \lfloor bx \rfloor\\
&=  \lfloor b^3x \rfloor - b \lfloor b^2x \rfloor.
\end{align*} 

Ainsi $\boxed{c_3 = \lfloor b^3x \rfloor – b \lfloor b^2x \rfloor.}$

Cette écriture va se généralise sans effectuer de récurrence.

Le cas général de $c_n$

Soit $n$ un entier supérieur ou égal à $2.$

D’une part, comme $x = \sum_{i=1}^{+\infty}\frac{c_i}{b^i}$ vous obtenez :

\begin{align*}
b^nx &=b^{n-1}c_1+\cdots+ c_n+\sum_{i=1}^{+\infty}\frac{c_{i+n}}{b^i}\\
 &=\sum_{k=1}^n b^{n-k}c_k+\sum_{i=1}^{+\infty}\frac{c_{i+n}}{b^i}.
\end{align*} 

En reprenant une démarche similaire à celle adoptée précédemment, vous avez $0\leq \sum_{i=1}^{+\infty}\frac{c_{i+n}}{b^i} < 1$ vu que le développement décimal est propre, ce qui entraîne :

\begin{align*}
 \lfloor b^n x \rfloor &= \sum_{k=1}^n b^{n-k}c_k\\
&= \sum_{k=1}^{n-1} b^{n-k}c_k +c_n\\
&= b\left(\sum_{k=1}^{n-1} b^{n-1-k}c_k\right) +c_n.
\end{align*}

D’autre part, comme $x = \sum_{i=1}^{+\infty}\frac{c_i}{b^i}$ vous obtenez aussi :

\begin{align*}
b^{n-1}x &=b^{n-2}c_1+\cdots+ c_{n-1}+\sum_{i=1}^{+\infty}\frac{c_{i+n-1}}{b^i}\\
 &=\sum_{k=1}^{n-1} b^{n-1-k}c_k+\sum_{i=1}^{+\infty}\frac{c_{i+n-1}}{b^i}.
\end{align*} 

En reprenant une démarche similaire à celle adoptée précédemment, vous avez $0\leq \sum_{i=1}^{+\infty}\frac{c_{i+n-1}}{b^i} < 1$ vu que le développement décimal est propre, ce qui entraîne :

 \lfloor b^{n-1} x \rfloor = \sum_{k=1}^{n-1} b^{n-1-k}c_k.

Ainsi vous avez obtenu :

\begin{align*}
c_n &= \lfloor b^n x \rfloor - b\left(\sum_{k=1}^{n-1} b^{n-1-k}c_k\right)\\
&= \lfloor b^n x \rfloor - b \lfloor b^{n-1} x \rfloor.
\end{align*}

Ainsi il a été démontré que :

\boxed{\forall n\in\N, n\geq 2 \implies c_n = \lfloor b^n x \rfloor - b \lfloor b^{n-1} x \rfloor.}

Si $x$ est un réel strictement compris entre $0$ et $1$ qui admet un développement propre en base $b$, alors celui-ci est unique.

Application pour $x=1/8$ en base $b=10$

Vous calculez tout d’abord quelques parties entières :

\begin{align*}
&c_1 =  \lfloor b x \rfloor  = \lfloor 10/8 \rfloor = \lfloor 5/4 \rfloor = 1\\
&\lfloor b^2 x \rfloor =  \lfloor 100/8 \rfloor = \lfloor 50/4 \rfloor = \lfloor 25/2 \rfloor = 12\\
&c_2 =  \lfloor b^2 x \rfloor - b\lfloor b x \rfloor = 12-10\times 1 = 2\\
&\lfloor b^3 x \rfloor =  \lfloor 1000/8 \rfloor = \lfloor 500/4 \rfloor = \lfloor 250/2 \rfloor = \lfloor 125 \rfloor = 125 \\
&c_3 =  \lfloor b^3 x \rfloor - b\lfloor b^2 x \rfloor = 125-10\times 12\times 1 = 5\\
&\lfloor b^4 x \rfloor =  \lfloor 10000/8 \rfloor = \lfloor 5000/4 \rfloor = \lfloor 2500/2 \rfloor = \lfloor 1250 \rfloor = 1250 \\
&c_4 =  \lfloor b^4 x \rfloor - b\lfloor b^3 x \rfloor = 1250-10\times 125\times 1 = 0.
\end{align*} 

Pour tout $n\geq 3$, vous établissez que $\lfloor b^n x \rfloor = 125\times 10^{n-3}$ si bien que, pour tout $n\geq 4$ vous avez :

\begin{align*}
c_n &=  \lfloor b^n x \rfloor - b \lfloor b^{n-1} x \rfloor \\
&= 125\times 10^{n-3} - 10\times 125\times 10^{n-1-3}\\
&= 125\times 10^{n-3} - 125\times 10^{n-3}\\
&=0.
\end{align*} 

Vous retrouvez que $1/8$ admet pour développement décimal propre $0,12500000\dots$ avec une infinité de $0$ ce qui s’écrit $1/8 =0,125.$

Prolongement

Soit $b$ une base, c’est-à-dire un nombre entier supérieur ou égal à $2.$ Soit $x$ un nombre réel quelconque.

Pourriez-vous proposer un énoncé concernant le développement de ce réel $x$ en base $b$ ?

La suite de Fibonacci a ses deux premiers termes égaux à $1.$ Ensuite, chaque terme est égale à la somme des deux précédents. Avec les notations, cela définit une suite $(f_n)_{n\geq 0}$ comme suit :

\left\{\begin{align*}
&f_0 = 1\\
&f_1 = 1\\
&\forall n\in\N, f_{n+2} = f_{n+1}+f_n.
\end{align*}
\right.

Calculez les premiers termes

Vous obtenez successivement :

\left\{\begin{align*}
f_2 &= f_1+f_0 = 1+1=2\\
f_3 &= f_2+f_1 = 2+1=3\\
f_4 &= f_3+f_2 = 3+2 = 5\\
f_5 &= f_4+f_3 = 5+3 = 8\\
f_6 &= f_5+ f_4 = 8+5 = 13.
\end{align*}
\right.

Calculez les sommes des carrés deux nombres consécutifs de Fibonacci pour quelques valeurs :

\left\{\begin{align*}
&f_0^2+f_1^2 = 1^2+1^2 = 2 = f_2\\
&f_1^2+f_2^2 = 1^2+2^2 = 5 = f_4\\
&f_2^2+f_3^2 = 2^2+3^2 =13 = f_6.
\end{align*}
\right.

Vu les résultats obtenus, vous allez procéder par récurrence et démontrer la validité du titre de cet exposé, grâce aux suggestions obtenues via les égalités susmentionnées.

Construisez une démonstration par récurrence double

Pour tout entier naturel $n$ vous notez $\mathscr{P}(n)$ la propriété : « $f_n^2+f_{n+1}^2 = f_{2n+2}.$ »

Initialisation double. Pour $n=0$ vous avez :

\left\{\begin{align*}
&f_{2n+2} = f_2 = 2\\
&f_n^2+f_{n+1}^2 = f_0^2+f_1^2 = 1^2+1^2=2.
\end{align*}
\right.

Comme $f_0^2+f_1^2 = f_2$ la propriété $P(0)$ est vérifiée.

Pour $n=1$ vous avez :

\left\{\begin{align*}
&f_{2n+2} = f_4 = 5\\
&f_n^2+f_{n+1}^2 = f_1^2+f_2^2 = 1^2+2^2=5.
\end{align*}
\right.

Comme $f_1^2+f_2^2 = f_4$ la propriété $\mathscr{P}(1)$ est vérifiée.

Hérédité. Soit $n$ un entier naturel pour lequel $\mathscr{P}(n)$ et $\mathscr{P}(n+1)$ sont vérifiées.

Vous avez donc :

\left\{\begin{align*}
&f_n^2+f_{n+1}^2 = f_{2n+2}\\
&f_{n+1}^2+f_{n+2}^2 = f_{2n+4}.
\end{align*}
\right.

Vous cherchez à évaluer $f_{2n+6}$ et à l’exprimer en fonction des nombres $f_{n+2}$ et $f_{n+3}.$ Cela étant pour l’instant trop délicat, vous allez exprimer $f_{2n+6}$ en fonction de $f_{2n+4}$ et de $f_{2n+2}.$ Cela donne ce qui suit :

\begin{align*}
f_{2n+6} &= f_{2n+5}+f_{2n+4}.
\end{align*}

Comme $f_{2n+4}$ convient, vous exprimez $f_{2n+5}$ en fonction des termes qui le précèdent, soit $f_{2n+5} = f_{2n+4}+f_{2n+3}.$ Du coup :

\begin{align*}
f_{2n+6} &= (f_{2n+4}+f_{2n+3})+f_{2n+4}\\
&=2f_{2n+4}+f_{2n+3}.
\end{align*}

Il serait tentant d’écrire $f_{2n+3} = f_{2n+2}+f_{2n+1}$ mais cela ferait apparaître $f_{2n+1}$ qui n’est pas souhaité. A la place vous utilisez $f_{2n+4} = f_{2n+3}+f_{2n+2}$ ce qui fournit $f_{2n+3} = f_{2n+4}-f_{2n+2}.$ Ainsi :

\begin{align*}
f_{2n+6} &=2f_{2n+4}+f_{2n+3}\\
&= 2f_{2n+4}+(f_{2n+4}-f_{2n+2})\\
&=3f_{2n+4}-f_{2n+2}.
\end{align*}

Le premier objectif a été rempli. Vous allez donc maintenant remplacer $f_{2n+4}$ par $f_{n+1}^2+f_{n+2}^2$ et $f_{2n+2}$ par $f_n^2+f_{n+1}^2.$ Cela aboutit à ce qui suit :

\begin{align*}
f_{2n+6} &=3f_{2n+4}-f_{2n+2}\\
&=3(f_{n+1}^2+f_{n+2}^2) - (f_n^2+f_{n+1}^2)\\
&=3f_{n+2}^2+2f_{n+1}^2-f_n^2.
\end{align*}

L’apparition de $f_{n+2}$ est satisfaisante. Par contre celles de $f_n$ et de $f_{n+1}$ ne conviennent pas car l’objectif principal est d’exprimer $f_{2n+6}$ en fonction de $f_{n+2}$ et de $f_{n+3}.$

Vous allez éliminer $f_n$ en utilisant le fait que $f_n = f_{n+2}-f_{n+1}.$ Du coup :

\begin{align*}
f_{2n+6} &=3f_{n+2}^2+2f_{n+1}^2-f_n^2\\
&=3f_{n+2}^2+2f_{n+1}^2-(f_{n+2}-f_{n+1})^2\\
&=3f_{n+2}^2+2f_{n+1}^2-f_{n+2}^2-f_{n+1}^2+2f_{n+1}f_{n+2}\\
&=2f_{n+2}^2+f_{n+1}^2+2f_{n+1}f_{n+2}.
\end{align*}

Il vous reste à éliminer $f_{n+1}$ en vous rappelant que $f_{n+1}=f_{n+3}-f_{n+2}.$ Les éliminations finales aboutissent à ce qui suit :

\begin{align*}
f_{2n+6} &=2f_{n+2}^2+f_{n+1}^2+2f_{n+1}f_{n+2}\\
&=2f_{n+2}^2+(f_{n+3}-f_{n+2})^2+2(f_{n+3}-f_{n+2})f_{n+2}\\
&=2f_{n+2}^2+f_{n+3}^2+f_{n+2}^2-2f_{n+2}f_{n+3}+2f_{n+2}f_{n+3}-2f_{n+2}^2\\
&=f_{n+3}^2+f_{n+2}^2.
\end{align*}

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

Conclusion. Il a été montré par récurrence double que :

\boxed{\forall n\in\N,  f_{2n+2} = f_n^2+f_{n+1}^2.}

Dans cet exposé, vous désignez par $e$ un nombre entier naturel non nul et par $p$ un nombre premier.

Lorsque $a$ et $b$ sont deux entiers relatifs avec $PGCD(a,p)=1$, vous vous intéressez à la résolution de l’équation suivante où l’inconnue $x$ est un nombre entier relatif :

\boxed{ax\equiv b\mod p^e.}

Pour tout entier naturel $n$, les propositions $PGCD(n,p^e)=1$ et $PGCD(n,p)=1$ sont équivalentes

Soit $n$ un entier naturel.

Supposez que $PGCD(n,p^e)=1.$ Comme $p$ est un nombre premier, $PGCD(n,p)\in\{1,p\}.$ Si $PGCD(n,p)=p$, alors $p$ divise $n.$ Or $p$ divise $p^e.$ Donc $p$ est un diviseur commun à $n$ et à $p^e$ donc $PGCD(n,p^e)\geq p > 1$ contradiction. Donc $PGCD(n,p)=1.$

Réciproquement, supposez que $PGCD(n,p)=1.$ Si $PGCD(n,p^e)> 1$ alors $PGCD(n,p^e)$ est un entier supérieur ou égal à $2$. Il est donc divisible par un nombre premier $q.$ D’une part $q$ divise $n.$ D’autre part, $q$ divise $p^e.$ D’après le lemme d’Euclide, $q$ divise $p.$ Comme $p$ est un nombre premier, il n’admet que deux diviseurs $1$ et $p.$ Comme $q$ est premier vous avez $q\neq 1$ vous obtenez donc $q=p.$ Il en résulte que $p$ divise $n.$ Comme $p$ divise $p$, vous déduisez que $PGCD(n,p)\geq p$ donc $1\geq p$ ce qui est impossible. Donc $PGCD(n,p^e)=1.$

Est ainsi prouvé le lemme suivant :

\boxed{\forall n\in\N, PGCD(n,p^e)=1 \Longleftrightarrow PGCD(n,p)=1.}

Une première équation équivalente

Vous notez $a’$ le résidu modulo $p^e$ du nombre $a$ pour obtenir :

\left\{\begin{align*}
&0\leq a'< p^e\\
&a\equiv a'\mod p^e.
\end{align*}\right.

Examinez $PGCD(a’,p).$ Si $PGCD(a’,p)=p$ vous déduisez que $p$ divise $a’.$ Comme $p^e$ divise $a-a’$ et que $p$ divise $p^e$ vous en tirez que $p$ divise $a-a’.$ Par somme, il en résulte que $p$ divise $a’+(a-a’)$ donc $p$ divise $a$ et donc $PGCD(a,p)\geq p$ ce qui implique $PGCD(a,p)\neq 1$ contradiction. Comme $PGCD(a’,p)\in\{1,p\}$ vous obtenez $PGCD(a’,p)=1.$

En posant $b’=b$ par souci de cohérence des notations, l’équation de départ a été ramenée à une équation de la forme $a’x\equiv b’ \mod p^e$ avec :

L’équation $ax\equiv b\mod p^e$ est équivalente à une équation de la forme $a’x \equiv b’\mod p^e$ avec les conditions suivantes :

\left\{\begin{align*}
&0\leq a' < p^e\\
&PGCD(a',p)=1
\end{align*}\right.

Le cas où $a’=0$ fait disparaître la variable $x$ et l’équation est résolue : soit il n’y a pas de solution, soit tous les entiers sont solutions. Le cas $a’=1$ est directement résolu. Il sera supposé dans la suite que :

2\leq a' < p^e.

Déterminez une autre équation équivalente

Vous cherchez à montrer que l’équation $a’x\equiv b’ \mod p^e$ va se ramener à une équation équivalente de la forme $a »x\equiv b » \mod p^e$ où $1\leq a » < a’$ et $PGCD(a »,p)=1.$

Effectuez la division euclidienne de $p^e$ par $a’$

Comme $p^e$ et $a’$ sont positifs, il existe un entier naturel $q$ et un entier positif ou nul $r$ tel que $r<a’$ avec $p^e = a’q+r.$

Si $r=0$ alors $p^e = a’q.$ Donc $p^e$ divise $a’ q.$ Or, $PGCD(a’,p)=1$ donc $PGCD(a’,p^e)=1.$ Par le théorème de Gauss, $p^e$ divise $q.$ Donc $p^e \leq q.$ Or $a’\geq 2$ donc $a’q \geq 2q$ et $p^e \geq 2q.$ donc $q\geq p^e \geq 2q$ et $q\geq 2q$ d’où $0\geq q$ donc $q=0$ et par suite $p^e = 0$ et $p=0$ contradiction. Donc $r\geq 1.$

Premier cas : $q$ n’est pas un multiple de $p$

Supposez $PGCD(r,p)> 1$ alors $PGCD(r,p)=p$ car $p$ est un nombre premier. Donc $p$ divise $r.$ Comme $a’q = p^e-r$ vous déduisez que $p$ divise $a’q.$ Or $PGCD(a’,p)=1$ donc par le théorème de Gauss $p$ divise $q$ ce qui est absurde. Donc $PGCD(r,p)=1.$

Vous posez $a » = r$ et vous avez bien $PGCD(a »,r)=1.$ Vous obtenez $1\leq a »< a’.$ Comme $p^e = a’q+r$ vous avez $r\equiv -a’q \mod p^e.$

Soit maintenant $x$ un entier relatif tel que $a’x\equiv b’ \mod p^e.$ En multipliant cette relation par $q$, vous obtenez $a’qx\equiv b’q \mod p^e.$ Vous remplacez $a’q$ par $-r$ étant entendu que $a’q\equiv -r \mod p^e.$ D’où $-rx\equiv b’q \mod p^e.$ Du coup, $rx\equiv -b’q \mod p^e.$ En posant $b » = -b’q$ vous avez obtenu $a »x\equiv b » \mod p^e.$

Réciproquement, soit $x$ un entier relatif tel que $a »x\equiv b » \mod p^e.$ Alors $rx\equiv -b’q \mod p^e.$ Du coup, $-a’qx \equiv -b’q \mod p^e$ et $a’qx\equiv b’q \mod p^e$ si bien que $p^e$ divise $q(a’x-b’).$ Supposez en raisonnant par l’absurde que $PGCD(p,q) > 1.$ Comme $p$ est un nombre premier vous obtenez $PGCD(p,q) = p$ donc $p$ divise $q$ ce qui est absurde. Donc $PGCD(p,q)=1.$ Du coup, $PGCD(p^e,q)=1.$ Via le théorème de Gauss vous déduisez que $p^e$ divise $a’x-b’$ et finalement $a’x\equiv b’\mod p^e.$

Second cas : $q$ est un multiple de $p$

L’égalité $p^e = a’q+r$ s’écrit $p^e = a'(q+1) + r-a’.$ Comme $1\leq r < a’$ vous avez $1\leq r \leq a’-1$ donc $1\leq a’-r< a’.$ Vous posez $a » = a’-r$ et vous avez $p^e = a'(q+1)-a ».$ Modulo $p^e$ cela fournit $a'(q+1)\equiv a » \mod p^e.$

Si $p$ divisait $q+1$ par différence $p$ diviserait $1$ ce qui est absurde. Donc $p$ ne divise pas $q+1.$ Par suite $PGCD(p,q+1)$ ne peut être égal à $p.$ Comme $p$ est premier vous déduisez que $PGCD(p,q+1)=1.$

Soit maintenant $x$ un entier relatif tel que $a’x\equiv b’ \mod p^e.$ En multipliant cette relation par $q+1$, vous obtenez $a'(q+1)x\equiv b'(q+1) \mod p^e.$ Vous remplacez $a'(q+1)$ par $a »$ compte tenu de la congruence $a'(q+1)\equiv a » \mod p^e.$ D’où $a »x\equiv b'(q+1) \mod p^e.$ En posant $b » = b'(q+1)$ vous avez obtenu $a »x\equiv b » \mod p^e.$

Réciproquement, soit $x$ un entier relatif tel que $a »x\equiv b » \mod p^e.$ Alors $a'(q+1)x\equiv b'(q+1) \mod p^e$ si bien que $p^e$ divise $(q+1)(a’x-b’).$ Comme $PGCD(p,q+1) =1$ vous déduisez $PGCD(p^e, q+1)=1.$ Via le théorème de Gauss vous déduisez que $p^e$ divise $a’x-b’$ et finalement $a’x\equiv b’\mod p^e.$

Il reste à examiner $PGCD(a »,p) = PGCD(a’-r,p).$ Si ce nombre est strictement supérieur à $1$ comme $p$ est premier vous avez $PGCD(a’-r,p)=p$ et $p$ divise $a’-r.$ Comme $a'(q+1)=p^e+(a’-r)$ vous déduisez que $p$ divise $a'(q+1).$ Comme $PGCD(a’,p)=1$ via le théorème de Gauss vous obtenez $p \mid q+1.$ Donc $PGCD(q+1,p) \geq p$ ce qui contredit $PGCD(q+1,p)=1.$ Ainsi, $PGCD(a »,p)=1.$

Conclusion

En notant $q$ le quotient de la division euclidienne de $p^e$ par $a’$, il suffit de multiplier l’équation $a’x\equiv b’\mod p^e$ par $q$ ou par $q+1$ pour obtenir une nouvelle équation $a »x\equiv b »\mod p^e$ équivalente à la précédente, avec le fait que $1\leq a » < a’.$ Si $q$ est un multiple de $p$ vous multipliez par $q+1$ et si $q$ n’est pas multiple de $p$ vous multipliez par $q.$

Si $a »=1$ l’équation est alors résolue. Sinon, il suffit de recommencer.

Un exemple d’application

Soit à résoudre $39x\equiv 13\mod 32$ où $x$ est un entier relatif.

$32= 2^5$ donc $32$ est bien une puissance d’un nombre premier ce qui va permettre d’appliquer successivement la méthode développée ci-dessus.

Vous remarquez que $39\equiv 7 \mod 32$ donc vous avez l’équivalence :

\forall x\in\Z, (39x\equiv 13\mod 32) \Longleftrightarrow (7x\equiv 13 \mod 32).

Vous déterminez le quotient de $32$ par $7$ il est égal à $4.$ Comme $4$ est un multiple de $2$, vous allez multiplier l’équation obtenue par $5$ ce qui fournit :

\begin{align*}
\forall x\in\Z,  (7x\equiv 13 \mod 32) &\Longleftrightarrow  (35x\equiv 65 \mod 32)\\
 &\Longleftrightarrow  (3x\equiv 1 \mod 32).
\end{align*}

Le quotient de la division euclidienne de $32$ par $3$ est $10.$ Comme $10$ est un multiplie de $2$, vous multipliez la dernière équation obtenue par $11.$

\begin{align*}
\forall x\in\Z,  (3x\equiv 1 \mod 32) &\Longleftrightarrow  (33x\equiv 11 \mod 32)\\
 &\Longleftrightarrow  (x\equiv 11 \mod 32).
\end{align*}

L’équation de départ est ainsi résolue.

\boxed{\forall x\in\Z, (39x\equiv 13\mod 32) \Longleftrightarrow (x\equiv 11 \mod 32).}

Soit $k$ un entier naturel non nul. Dans cette section, vous vous intéressez à la résolution de l’équation :

x^2\equiv 1\mod 2^k.

Traitez le cas où $k=1$

Comme $2^k = 2$ vous calculez tous les carrés modulo $2.$

\begin{array}{|c|c|c|}
\hline
x \mod 2 & 0 & 1\\
\hline
x^2 \mod 2 & 0 & 1\\
\hline
\end{array}

Vous obtenez donc :

\boxed{\forall x\in\Z, (x^2\equiv 1\mod 2) \Longleftrightarrow (x\equiv 1 \mod 2).}

Traitez le cas où $k=2$

Comme $2^2 = 4$ vous calculez tous les carrés modulo $4.$

\begin{array}{|c|c|c|c|c|}
\hline
x \mod 4 & 0 & 1 & 2 & -1\\
\hline
x^2 \mod 4 & 0 & 1 & 0 & 1\\
\hline
\end{array}

Vous obtenez donc :

\boxed{\forall x\in\Z, (x^2\equiv 1\mod 4) \Longleftrightarrow (\exists a\in\{-1,1\}, x\equiv a \mod 4).}

Traitez le cas où $k=3$

Comme $2^3 = 8$ vous calculez tous les carrés modulo $8.$

\begin{array}{|c|c|c|c|c|c|c|c|c|}
\hline
x \mod 8  &-1 & 0 & 1 & 2 & 3 & 4  & 5 & 6\\
\hline
x^2 \mod 8 & 1 & 0 & 1 & 4 & 1& 0  & 1  & 4\\
\hline
\end{array}

Vous obtenez donc :

\boxed{\forall x\in\Z, (x^2\equiv 1\mod 8) \Longleftrightarrow (\exists a\in\{-1,1, 3, 5\}, x\equiv a \mod 8).}

Et après, que se passe-t-il modulo $16$ dans le cas où $k=4$ ?

Vous pourriez penser que le nombre de solutions modulo $2^4=16$ serait égal à $8$ comme le suggère cette analyse.

Analyse. Soit $x$ un nombre entier relatif tel que :

x^2\equiv 1 \mod 16.

Comme $8\mid 16$ et que $16 \mid x^2-1$ il vient $8\mid x^2-1$ et du coup :

x^2\equiv 1 \mod 8.

En appliquant le résultat précédent, vous déduisez qu’il existe $a\in\{-1, 1, 3,5\}$ tel que $x^2\equiv a \mod 8.$

Cas n°1. $x\equiv -1\mod 8.$ Il existe un entier relatif $t$ tel que $x=-1+8t.$ Si $t$ est pair, il existe un entier relatif $k$ tel que $t=2k$ et par suite $x=-1+16k$ et $x\equiv -1\mod 16.$ Si $t$ est impair, il existe un entier relatif $\ell$ tel que $t = 2\ell+1$ et par suite $x = -1+8(2\ell+1) = 7+16\ell$ et $x\equiv 7\mod 16.$

Cas n°2. $x\equiv 1\mod 8.$ En reprenant la démarche du cas précédent, vous déduisez que soit $x\equiv 1\mod 16$ soit $x\equiv 9\mod 16.$

Cas n°3. $x\equiv 3\mod 8.$ De même, vous déduisez que soit $x\equiv 3\mod 16$ soit $x\equiv 11\mod 16.$

Cas n°4. $x\equiv 5\mod 8$ en vous avez : soit $x\equiv 5\mod 16$ soit $x\equiv 13\mod 16.$

Le résultat suivant est ainsi établi :

\boxed{\forall x\in\Z, (x^2\equiv 1\mod 16) \implies (\exists a\in\{-1,1, 3, 5, 7, 9, 11, 13\}, x\equiv a \mod 16).}

Il y a huit candidats potentiels.

Synthèse. Soit $x$ un entier relatif.

Si $x\equiv -1\mod 16$, alors $x^2\equiv 1\mod 16.$

Si $x\equiv 1\mod 16$, alors $x^2\equiv 1\mod 16.$

Si $x\equiv 3\mod 16$, alors $x^2\equiv 9\mod 16.$

Si $x\equiv 5\mod 16$, alors $x^2\equiv 25\mod 16$ et $x^2\equiv 9\mod 16.$

Si $x\equiv 7\mod 16$, alors $x^2\equiv 49 \mod 16$ et $x^2\equiv 1 \mod 16.$

Si $x\equiv 9\mod 16$, alors $x\equiv -7\mod 16$ donc $x^2\equiv 49 \mod 16$ et $x^2\equiv 1 \mod 16.$

Si $x\equiv 11\mod 16$, alors $x\equiv -5\mod 16$ alors $x^2\equiv 25 \mod 16$ et $x^2\equiv 9 \mod 16.$

Si $x\equiv 13\mod 16$, alors $x\equiv -3\mod 16$ alors $x^2 \equiv 9 \mod 16.$

Parmi les 8 candidats, il n’y en a que quatre qui conviennent.

Conclusion. Par analyse-synthèse, il vient d’être démontré que :

\boxed{\forall x\in\Z, (x^2\equiv 1\mod 16) \Longleftrightarrow (\exists a\in\{-1,1, 7, 9\}, x\equiv a \mod 16).}

Le nombre de solutions modulo $16$ reste finalement égal à $4.$ Vous allez montrer que cela se généralise.

Passez au cas général en étudiant la situation pour $k\geq 3$

Dans cette section, vous supposez que $k$ est un entier supérieur ou égal à $3.$

Pour tout entier $n\geq 3$ vous notez $\mathscr{P}(n)$ la propriété suivante :

\boxed{\forall x\in\Z, (x^2\equiv 1\mod 2^n) \Longleftrightarrow (\exists a\in\left\{-1,1, -1+2^{n-1}, 1+2^{n-1}\right\}, x\equiv a \mod 2^n).}

Initialisation. Il a été démontré ci-dessus que :

\forall x\in\Z, (x^2\equiv 1\mod 8) \Longleftrightarrow (\exists a\in\{-1,1, 3, 5\}, x\equiv a \mod 8).

Comme $3 = -1+2^{3-1}$ et $5 = 1+2^{3-1}$ vous en déduisez que $\mathscr{P}(3)$ est vérifiée.

Hérédité. Soit $n$ un entier supérieur ou égal à $3.$ Supposez $\mathscr{P}(n).$

Soit $x$ un entier relatif tel que $x^2\equiv 1 \mod 2^{n+1}.$

Comme $2^n \mid 2^{n+1}$ vous déduisez $x^2\equiv 1 \mod 2^n.$ D’après l’hypothèse de récurrence, il existe un entier $a\in \left\{-1,1, -1+2^{n-1}, 1+2^{n-1}\right\}$ tel que $x\equiv a\mod 2^n.$

Cas n°1. $a\in\{-1,1\}.$ De $x\equiv a \mod 2^n$ vous déduisez l’existence d’un entier relatif $t_1$ tel que $x = a+2^n t_1.$ Si $t_1$ est pair, il existe un entier relatif $k_1$ tel que $t_1 = 2k_1$ et par suite $x=a+2^{n+1}k_1$ et $x\equiv a\mod 2^{n+1}.$

Si $t_1$ est impair il existe un entier relatif $\ell_1$ tel que $t_1 = 1+2\ell_1$ et par suite $x = a+2^n(1+2\ell_1)$ d’où $x=a+2^n+2^{n+1}\ell_1$ et $x\equiv a+2^n \mod 2^{n+1}.$

Cas n°2. $a\in\{-1+2^{n-1}, 1+2^{n-1}\}.$ Il existe $b\in\{-1,1\}$ tel que $a = b+2^{n-1}.$ Comme $x\equiv a \mod 2^n$ vous déduisez qu’il existe un entier relatif $t$ tel que $x = a+2^n t$ ce qui donne $x = b+2^{n-1}+2^n t.$ En élevant au carré, il vient :

\begin{align*}
x^2 &= b^2+2^{2n-2}+t^2\times 2^{2n}+b2^{n}+bt\times2^{n+1}+t\times 2^{2n}\\
&= b^2+2^{n+1}2^{n-3}+t^2\times 2^{n+1}2^{n-1}+b\times 2^n+bt\times 2^{n+1}+t\times 2^{n+1}2^{n-1}.
\end{align*}

Comme $n\geq 3$ tous les exposants qui apparaissent dans les puissances de $2$ sont positifs ou nuls. Modulo $2^{n+1}$ vous obtenez :

x^2\equiv b^2+b\times 2^n\mod 2^{n+1}.

Or, $b^2=1$ donc :

x^2\equiv 1+b\times 2^n\mod 2^{n+1}.

Comme $x^2\equiv 1 \mod 2^{n+1}$ vous déduisez :

\begin{align*}
1 \equiv 1+b\times 2^n \mod 2^{n+1}\\
b\times 2^n \equiv 0 \mod 2^{n+1}.
\end{align*}

Il existe un entier relatif $k$ tel que $b\times 2^n = k\times 2^{n+1}.$ En divisant par $2^n$ vous obtenez $b = 2k$ donc $b$ est pair. Or, $b\in\{-1,1\}$ d’où une contradiction. Ainsi le cas n°2 ne peut se produire.

Vous déduisez l’implication suivante :

\forall x\in\Z, (x^2\equiv 1\mod 2^{n+1}) \implies (\exists u\in\left\{-1,1, -1+2^{n}, 1+2^{n}\right\}, x\equiv u \mod 2^{n+1}).

Il reste à montrer la réciproque.

Soit $x$ un entier relatif.

S’il existe $a\in\{-1,1\}$ tel que $x\equiv a \mod 2^{n+1}$ alors $x^2\equiv a^2\mod 2^{n+1}.$ Or $a^2=1$ donc $x^2\equiv 1 \mod 2^{n+1}.$

S’il existe $a\in\{-1,1\}$ tel que $x\equiv a+2^n \mod 2^{n+1}$ alors :

\begin{align*}
x^2\equiv a^2+2^{2n}+a\times 2^{n+1} \mod 2^{n+1}\\
x^2\equiv a^2+2^{n+1}2^{n-1}+a\times 2^{n+1} \mod 2^{n+1}\\
x^2 \equiv a^2 \mod 2^{n+1}.
\end{align*} 

Comme $a^2=1$ vous obtenez encore $x^2\equiv 1 \mod 2^{n+1}.$

Vous avez démontré ce qui suit :

\forall x\in\Z, (x^2\equiv 1\mod 2^{n+1}) \impliedby (\exists u\in\left\{-1,1, -1+2^{n}, 1+2^{n}\right\}, x\equiv u \mod 2^{n+1}).

De ces deux implications, il en résulte que $\mathscr{P}(n+1)$ est vraie.

Conclusion. Par récurrence vous avez montré que pour tout entier $n$ supérieur ou égal à $3$, vous avez :

\forall x\in\Z, (x^2\equiv 1\mod 2^{n}) \Longleftrightarrow (\exists u\in\left\{-1,1, -1+2^{n-1}, 1+2^{n-1}\right\}, x\equiv u \mod 2^{n}).

Comme l’entier $k$ est supérieur ou égal à $3$, le résultat final est ainsi établi :

\boxed{\forall x\in\Z, (x^2\equiv 1\mod 2^{k}) \Longleftrightarrow (\exists a\in\left\{-1,1, -1+2^{k-1}, 1+2^{k-1}\right\}, x\equiv a \mod 2^{k}).}

Prolongement

Vous pouvez aussi regrouper les solutions en visant une approche qui conserve les opposés.

Adaptez alors la démonstration précédemment effectuée pour justifier que :

\forall x\in\Z, (x^2\equiv 1\mod 2^{k}) \Longleftrightarrow (\exists a\in\left\{1, 1+2^{k-1}\right\}, x\equiv \pm a \mod 2^{k}).

Dans le contenu rédigé dans l'article 352 une méthode permettant de résoudre une équation linéaire avec congruences a été développée.

Sera présentée ici une méthode alternative qui ne fait pas appel au $PGCD$ directement.

Soit $a$ un entier naturel non nul, $b$ un entier relatif et $n$ un entier naturel non nul.

Vous souhaitez résoudre l’équation suivante d’inconnue $x$ entière :

ax\equiv b\mod n.

Remarquez que vous pouvez remplacer $a$ et $b$ respectivement par leurs résidus modulo $n.$

Autrement dit, dans la suite, vous supposez que $a$ est un entier naturel non nul strictement inférieur à $n$, que $b$ est un entier naturel strictement inférieur à $n.$

Le théorème fondamental

Vous effectuez la division euclidienne de $n$ par $a$, il existe un quotient $q\in\N$ et un reste $r\in\N$ avec $0\leq r \leq a-1$ tels que $n = aq+r.$

Vous allez établir que l’équation $ax\equiv b\mod n$ d’inconnue $x\in\Z$ admet au moins une solution, si et seulement si, l’équation $ry \equiv -b \mod a$ d’inconnue $y\in \Z$ admet au moins une solution.

Premier sens

Soit $x\in\Z$ tel que $ax\equiv b \mod n.$

Il existe un entier relatif $k$ tel que $ax = b+ nk.$ Vous remplacez $n$ par $aq+r$ du coup :

\begin{align*}
ax &= b +(aq+r)k\\
ax &= b +aqk+rk\\
a(x-qk) - b &= rk.
\end{align*}

Cela prouve que $rk \equiv -b \mod a.$

Donc l’équation $ry \equiv -b \mod a$ d’inconnue $y\in \Z$ admet au moins une solution qui est $k.$

Second sens

Soit $y\in\Z$ tel que $ry \equiv -b \mod a.$

Il existe un entier relatif $t$ tel que $ry = -b+at.$ Vous utilisez le fait que $r = n-aq$ ce qui fournit :

\begin{align*}
(n-aq)y = -b+at\\
ny-aqy = -b+at\\
ny+b = a(t+qy).
\end{align*}

Cela prouve que $a(t+qy) \equiv b \mod n.$ Or, $t+qy\in\Z.$

Donc l’équation $ax\equiv b\mod n$ d’inconnue $x\in\Z$ admet au moins une solution qui est $t+qy.$

Déduisez une solution de l’équation $ax\equiv b\mod n$ à partir d’une solution de l’équation $ry\equiv -b\mod a$

Soit $y$ un entier relatif tel que $ry\equiv -b \mod a.$

Alors $a$ divise $ry+b.$ Donc $t = \frac{ry+b}{a}$ est un nombre entier et $ry = -b+at.$

D’après le calcul effectué à la section précédente, si vous posez $x = t+qy$, alors $x$ est un entier relatif et $ax\equiv b\mod n.$

Vous trouvez maintenant une expression de $x$ qui ne fait pas intervenir le quotient $q.$ En effet :

\begin{align*}
x &= t+qy\\
&=\frac{ry+b}{a}+\frac{aqy}{a}\\
&=\frac{(aq+r)y+b}{a}\\
&=\frac{ny+b}{a}.
\end{align*}

Vous utiliserez dans la suite :

\boxed{x=\frac{ny+b}{a}.}

En définitive, si $k$ est une solution de l’équation $ry \equiv -b \mod a$, alors $\frac{nk+b}{a}$ est une solution de l’équation $ax\equiv b\mod n.$

Note. Au passage, comme $x$ est un entier relatif, vous constatez que le nombre $a$ divise $ny+b.$ Cela peut se voir depuis le début. Comme $ry\equiv -b \mod a$ vous avez $(n-aq)y \equiv -b \mod a$ si bien que $ny\equiv -b \mod a$ et $ny+b\equiv 0 \mod a.$

Application

L’équation $143x\equiv 44 \mod 231$ d’inconnue $x\in\Z$ admet-elle au moins une solution ? Si oui, en déterminer une.

Vous appliquez le théorème fondamental précité pour le savoir.

Vous effectuez la division euclidienne de $231$ par $143.$ Comme $231 = 1\times 143+88$ Vous trouvez un reste égal à $88.$

Il s’agit maintenant de savoir si l’équation $88 y_1\equiv -44 \mod 143$ d’inconnue $y_1\in\Z$ admet au moins une solution.

Vous effectuez la division euclidienne de $143$ par $88.$ Comme $143 = 1\times 88+55$ Vous trouvez un reste égal à $55.$

Il s’agit maintenant de savoir si l’équation $55 y_2 \equiv 44 \mod 88$ d’inconnue $y_2\in\Z$ admet au moins une solution.

En divisant par $11$ cette équation est équivalente à $5y_2\equiv 4 \mod 8.$

Vous effectuez la division euclidienne de $8$ par $5.$ Comme $8 = 1\times 5+3$ Vous trouvez un reste de $3.$

Il s’agit maintenant de savoir si l’équation $3 y_3 \equiv -4 \mod 5$ d’inconnue $y_3\in\Z$ admet au moins une solution.

Vous effectuez la division euclidienne de $5$ par $3.$ Comme $5= 1\times 3+2$ Vous trouvez un reste de $2.$

Il s’agit maintenant de savoir si l’équation $2 y_4 \equiv 4 \mod 3$ d’inconnue $y_4\in\Z$ admet au moins une solution.

Vous effectuez la division euclidienne de $3$ par $2.$ Comme $3= 1\times 2+1$ Vous trouvez un reste de $1.$

Vous tombez alors sur l’équation $y_5 \equiv -4 \mod 2$ d’inconnue $y_5\in\Z$ qui admet au moins une solution, il suffit de prendre $y_5 = 0.$ Il s’ensuit que toutes les équations précitées admettent au moins une solution. Pour chacune d’entre elles, vous en calculez une.

Il vient successivement :

\begin{align*}
y_4 &= \frac{3y_5+4}{2} = \frac{4}{2} = 2
\\
y_3 &= \frac{5y_4-4}{3} = \frac{10-4}{3} = 2
\\
y_2 &= \frac{8y_3+4}{5} = \frac{16+4}{5} = 4
\\
y_1 &= \frac{143y_2-44}{88} = \frac{572-44}{88} = \frac{528}{88} = 6
\\
x&=\frac{231y_1+44}{143} = \frac{1386+44}{143}=10.
\end{align*} 

En définitive, $10$ est une solution de l’équation $143x\equiv 44 \mod 231$ d’inconnue $x\in\Z.$

Prolongement

Déterminez toutes les solutions de l’équation $143x\equiv 44 \mod 231$ d’inconnue $x\in\Z$ en les décrivant modulo $231.$

Cet exposé complète le contenu rédigé dans l'article 361.

Soit $n$ un entier naturel non nul.

Pour toute partie $A$ de $\Z$ vous direz que $A$ constitue un ensemble d’entiers non congruents modulo $n$ si et seulement si :

\forall (x,y)\in A^2,  (x \equiv y \mod n) \implies x=y.

Un système complet de congruences modulo $n$ est nécessairement un ensemble d’entiers non congruents modulo $n$

Soit $A$ un système complet de congruences modulo $n.$

Il est rappelé que l’ensemble $A$ vérifie la propriété $\mathscr{P}$ qui est : « pour tout entier relatif $x$, il existe un unique $a\in A$ tel que $x\equiv a \mod n.$ »

Soient maintenant $(x,y)\in A^2$ un couple d’éléments de $A$ tels que $x\equiv y \mod n.$

$y$ est un élément de $A$ vérifiant $x\equiv y \mod n.$

Or, $x$ est aussi un élément de $A$ tel que $x\equiv x \mod n.$

D’après la propriété $\mathscr{P}$ appliquée à $x$, vous déduisez par unicité que $x=y.$

Tout ensemble d’entiers non congruents modulo $n$ qui possède exactement $n$ éléments est un système complet de congruences modulo $n$

Soit $A$ une partie de $\Z$ comportant exactement $n$ éléments, vous les notez $a_1, \dots, a_n$ avec $a_1<\cdots<a_n.$ Supposez de plus que $A$ soit un ensemble d’entiers non congruents modulo $n.$

Soit $x$ un entier relatif fixé.

Vous raisonnez par l’absurde et supposez qu’il n’existe aucun élément $a\in A$ tel que $x\equiv a \mod n.$

Vous utilisez le fait que l’ensemble $\llbracket 0, n-1\rrbracket$ est un système complet de congruences modulo $n.$ Pour tout $i\in\llbracket 1, n\rrbracket$ il existe un unique $r_i\in\llbracket 0, n-1\rrbracket$ tel que $a_i\equiv r_i \mod n.$ De même, il existe un unique $r\in\llbracket 0,n-1\rrbracket$ tel que $x\equiv r\mod n.$

Notez que s’il existe $i\in\llbracket 1, n\rrbracket$ tel que $r = r_i$ alors $x \equiv r \equiv r_i \equiv a_i \mod n$ ce qui fournit, par transitivité de la congruence, $x\equiv a_i\mod n.$ Or, cela est une contradiction.

Par conséquent, pour tout $i\in\llbracket 1, n\rrbracket, r_i \neq r.$

L’ensemble $\{ r_i, 1\leq i\leq n\}$ est inclus dans l’ensemble $\llbracket 0,n-1\rrbracket \setminus \{r\}$ qui comporte $n-1$ éléments. Utilisant le principe des tiroirs, vous déduisez qu’il existe $(i,j)\in\llbracket 1, n\rrbracket ^2$ tel que $i<j$ et $r_i=r_j.$

Vous déduisez $a_i\equiv r_i \equiv r_j \equiv a_j \mod n$ et par transitivité $a_i\equiv a_j \mod n.$ Comme $A$ est un ensemble d’entiers non congruents modulo $n$, cela implique $a_i=a_j.$ Or $i<j$ donc $a_i < a_j$ d’où une contradiction.

Il a été démontré que :

\forall x\in \Z, \exists a\in A, x\equiv a\mod n.

Soit $x$ un entier relatif. Supposez qu’il existe $(a,a’)\in A^2$ tel que :

\begin{align*}
x\equiv a\mod n\\
x\equiv a' \mod n.
\end{align*}

Alors $a\equiv a’\mod n$ et comme $A$ est un ensemble d’entiers non congruents, vous avez $a=a’.$

Ainsi :

\forall x\in \Z, \exists !a\in A, x\equiv a\mod n.

L’ensemble $A$ est bien un système complet de congruences modulo $n.$

Soit $n$ un entier naturel non nul fixé dans tout cet exposé.

Une partie $A$ de l’ensemble $\Z$ sera qualifiée de système complet de congruences modulo $n$ si et seulement si, pour tout entier relatif $x$, il existe un unique élément $a$ de $A$ tel que $x\equiv a \mod n.$

L’exemple fondamental

Soit $x$ un entier relatif. Vous effectuez la division euclidienne de $x$ par $n.$ Il existe un quotient $q$ et un entier $r\in \llbracket 0, n-1\rrbracket$ tels que :

x = qn+r.

Du coup, vous obtenez :

x\equiv r\mod n.

Supposez qu’il existe $r’\in\llbracket 0, n-1\rrbracket$ tel que :

x\equiv r'\mod n.

Alors vous déduisez :

r\equiv r' \mod n.

Vous avez donc $n\mid r-r’$ donc il existe un entier relatif $k$ tel que $r-r’ = kn.$

Supposez que $k$ soit non nul. Alors $\vert k \vert \geq 1$ et comme $\vert r – r’\vert = \vert k \vert \times n$ vous déduisez $\vert r-r’\vert \geq n.$

Cependant, comme $r$ et $r’$ appartiennent à $\llbracket 0, n-1\rrbracket$ vous déduisez que $1-n\leq r-r’\leq n-1$ et donc $\vert r-r’\vert \leq n-1$ d’où d’une contradiction.

Donc $k=0$ et $r=r’.$ Il a été démontré que :

\forall x\in\Z, \exists! r\in\llbracket 0, n-1\rrbracket, x\equiv r\mod n.

Vous venez de démontrer dans ce paragraphe que l’ensemble $\llbracket 0, n-1\rrbracket$ est un système complet de congruences modulo $n.$

Étudiez le cardinal d’un système de congruences modulo n

Soit $A$ un système complet de congruences modulo $n.$

En raisonnant par l’absurde, supposez que $A$ possède au moins $n+1$ éléments. Vous notez ces entiers relatifs $a_1, \dots, a_{n+1}$ avec $a_1<\cdots<a_{n+1}.$

D’après le paragraphe précédent appliqué pour chaque élément précité, vous déduisez que :

\forall i\in\llbracket 1, n+1\rrbracket, \exists!r_i\in\llbracket 0, n-1\rrbracket, a_i\equiv r_i\mod n.

Les entiers $(r_i)_{1\leq i\leq n+1}$ sont au nombre de $n+1$ et ils appartiennent tous à l’ensemble $\llbracket 0, n-1\rrbracket$ qui comporte $n$ éléments. Utilisant le principe des tiroirs, vous déduisez qu’il existe un couple $(u,v)\in\llbracket 1, n+1\rrbracket^2$ tel que $u<v$ et $r_u = r_v.$ Comme $a_u \equiv r_u \mod n$ et $a_v\equiv r_v \mod n$ vous déduisez que $a_v\equiv a_u \mod n.$

D’une part, $a_v\equiv a_v \mod n$ et d’autre part $a_v\equiv a_u \mod n$ avec $a_u\neq a_v.$ Il a été montré qu’il existe un entier relatif $a_v$ et deux éléments de $A$ tels que $a_v$ leur soit congru modulo $n.$ Cela contredit le fait que $A$ soit un système complet de congruences modulo $n$ donc $A possède au maximum $n$ éléments.

Supposez en raisonnant encore par l’absurde que $A$ possède au maximum $n-1$ éléments.

Si $A$ est vide, alors $1$ doit être congru à un unique élément de $A$ modulo $1$, ce qui est impossible si $A$ ne possède aucun élément, donc $A$ n’est pas vide.

Vous notez $m$ le nombre d’éléments de $A$ vous avez $1\leq m\leq n-1.$ Vous notez les éléments de $A$ ainsi $a_1, \dots, a_{m}$ avec $a_1<\cdots<a_{m}.$

Toujours d’après le paragraphe précédent appliqué pour chaque élément précité, vous déduisez que:

\forall i\in\llbracket 1, m\rrbracket, \exists!r_i\in\llbracket 0, n-1\rrbracket, a_i\equiv r_i\mod n.

L’ensemble $R = \{r_i, 1\leq i \leq m\}$ contient au maximum $m$ éléments et c’est une partie de $\llbracket 0, n-1\rrbracket$ qui en comporte $n$ avec $n>m.$ Donc il existe un entier $r\in\llbracket 0, n-1\rrbracket$ tel que $r\notin R.$

S’il existait $i\in\llbracket 1, m\rrbracket$ tel que $r\equiv a_i \mod n$ alors $r\equiv r_i \mod n.$ Comme $r$ et $r_i$ appartiennent tous les deux à l’ensemble $\llbracket 0, n-1\rrbracket$ $\vert r-r_i\vert \leq n-1.$ Or $n$ divise $ r-r_i$ il existe un entier relatif $k$ tel que $r-r_i = kn$ ce qui implique $\vert r-r_i\vert = \vert k\vert \times n.$ Si $k$ n’est pas nul, il vient $\vert r-r_i\vert \geq n$ ce qui est absurde. Donc $k=0$ et $r=r_i$ et $r\in R$ contradiction. Donc $A$ ne peut pas posséder $n-1$ éléments au maximum.

Il en résulte que tout système complet de congruences modulo $n$ possède exactement $n$ éléments.