Auteur/autrice : Yannis TRIANTAPHYLIDES

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

En le décomposant comme produit de nombres premiers, vous constatez qu’il existe un entier naturel non nul $k$ ainsi que des entiers naturels non nuls $u_1, \dots, u_k$ et des nombres premiers $p_1\dots,p_k$ tels que :

n = p_1^{u_1}\cdots p_k^{u_k} = \prod_{i=1}^k p_i^{u_i}.

Vous allez utiliser un outil de dénombrement pour calculer $\varphi(n)$ qui est le nombre d’éléments de l’ensemble $A$ défini par :

A = \{m\in\llbracket 1, n\rrbracket, \mathrm{PGCD}(m, n)=1\}.

Utilisez le principe d’inclusion-exclusion (ou formule du crible)

Il est délicat de dénombrer directement le nombre d’éléments de $A.$ Vous allez donc dénombrer à la place le complémentaire de $A.$ Vous obtenez donc :

n-\varphi(n) = \#\{m\in\llbracket 1, n\rrbracket, PGCD(m, n)\neq1\}.

Vous notez $B$ l’ensemble défini par :

B= \{m\in\llbracket 1, n\rrbracket, PGCD(m, n)\neq1\}.

Soit $m$ un élément de $B.$ Puisque $PGCD(m,n)$ n’est pas égal à $1$, il est supérieur ou égal à $2.$ Donc il existe un nombre premier $p$ tel que $p$ divise $PGCD(m,n).$ Un tel $p$ divise $n.$ Compte tenu de la décomposition en produit de facteurs premiers de $n$ l’application du lemme d’Euclide permet d’affirmer qu’il existe un entier $i\in\llbracket 1, k\rrbracket$ tel que $p$ divise $p_i.$ Comme $p_i$ est un nombre premier, vous déduisez que $p\in\{1, p_i\}.$ Comme $p\neq 1$ en tant que nombre premier, vous avez $p = p_i.$

Comme $p$ divise $PGCD(m,n)$ vous avez aussi $p$ qui divise $m.$ Or $p = p_i$ donc il $p_i$ divise $m.$

Réciproquement, soit $i\in\llbracket 1, k\rrbracket$ tel que $p_i$ divise $m.$ Comme $p_i$ apparaît dans la décomposition de $n$ en produit de nombres premiers, vous déduisez que $p_i$ divise $n.$ Comme $p_i$ divise $m$ et $n$ à la fois, il divise $PGCD(m,n).$ Comme $p_i$ est supérieur ou égal à $2$ en tant que nombre premier, vous déduisez $PGCD(m,n)\neq 1.$

Vous avez donc établi que :

B = \{m\in\llbracket 1, n\rrbracket,\exist i\in\llbracket 1, k\rrbracket, p_i \mid m\}.

Cette écriture de $B$ suggère de définir, pour tout $i\in\llbracket 1, k\rrbracket$ l’ensemble suivant :

B_i=\{m\in\llbracket 1, n\rrbracket, p_i \mid m\}.

Vous avez ainsi :

B = \bigcup_{i=1}^k B_i.

Le nombre d’éléments de $B$ va être déterminé grâce au principe d’inclusion-exclusion (encore appelé aussi formule du crible). Il vient :

\begin{align*}
\#B &= \sum_{1\leq i \leq k} \#B_i-\sum_{\substack{1\leq i\leq k\\1\leq j\leq k\\i< j }}\#(B_i\cap B_j)+\cdots+(-1)^{k+1}\#(B_1\cap\cdots\cap B_k)\\
&=\sum_{u=1}^k (-1)^{u+1}\sum_{\substack{1\leq i_1\leq k\\  \dots\\ 1\leq i_u\leq k\\i_1< \cdots < i_u}}\#(B_{i_1}\cap\cdots\cap B_{i_u}).
\end{align*} 

Soit $u$ un nombre entier appartenant à l’intervalle $\llbracket 1, k\rrbracket$ et $(i_1,\dots,i_u)\in\llbracket 1, k\rrbracket^u$ tel que $i_1<\cdots < i_u.$ Par définition, vous avez :

B_{i_1}\cap\cdots\cap B_{i_u}=\{m\in\llbracket 1, n\rrbracket, \forall t\in\llbracket 1, u\rrbracket, p_{i_t} \mid m\}.

Comme $i_1< \cdots < i_u$ les nombres premiers $p_{i_1}, \cdots, p_{i_u}$ sont deux à deux distincts. En particulier ils sont premiers entre eux deux à deux. Via le corollaire du théorème de Gauss, vous déduisez que :

B_{i_1}\cap\cdots\cap B_{i_u}=\{m\in\llbracket 1, n\rrbracket, p_{i_1}\cdots p_{i_u} \mid m\}.

Soit maintenant $x$ un élément de l’ensemble $B_{i_1}\cap\cdots\cap B_{i_u}.$ $x$ est un entier compris entre $1$ et $n$ et le produit $p_{i_1}\cdots p_{i_u}$ divise $x.$ Donc il existe un entier naturel non nul $y$ tel que :

x = p_{i_1}\cdots p_{i_u} y

Comme $x\leq n$ vous déduisez :

p_{i_1}\cdots p_{i_u} y \leq n.

La décomposition en facteurs premiers de $n$ montre que $\frac{n}{p_{i_1}\cdots p_{i_u}}$ est un nombre entier.

En effet :

\begin{align*}
n & =\prod_{i=1}^k p_i^{u_i}\\
&= \prod_{i\in\{i_1,\cdots, i_u\}} p_i^{u_i} \prod_{i\not\in \{i_1,\dots, i_u\}} p_i^{u_i}\\
&=p_{i_1}\cdots p_{i_u} \left(  \prod_{i\in\{i_1,\cdots, i_u\}} p_i^{u_i-1} \prod_{i\not\in \{i_1,\dots, i_u\}} p_i^{u_i}\right)\\
\end{align*} 

Comme $\forall i\in\llbracket 1, k\rrbracket u_i \geq 1$ le nombre $\prod_{i\in{i_1,\cdots, i_u}} p_i^{u_i-1} \prod_{i\not\in {i_1,\dots, i_u}} p_i^{u_i}$ est bien un entier naturel non nul.

Par suite :

y\leq \frac{n}{p_{i_1}\cdots p_{i_u}}.

Comme $y$ est non nul, il vient :

1\leq y\leq \frac{n}{p_{i_1}\cdots p_{i_u}}

Vous avez démontré l’inclusion :

B_{i_1}\cap\cdots\cap B_{i_u} \subset \left\{ p_{i_1}\cdots p_{i_u}  y, y\in \left[ 1, \frac{n}{p_{i_1}\cdots p_{i_u}} \right]\cap \N\right\}.

Réciproquement, soit $y$ un nombre entier appartenant à l’intervalle $\left[ 1, \frac{n}{p_{i_1}\cdots p_{i_u}} \right].$

Note. Il est rappelé que $\frac{n}{p_{i_1}\cdots p_{i_u}}$ est un entier naturel non nul.

Par produit, le nombre $p_{i_1}\cdots p_{i_u} y$ est un entier naturel non nul. D’autre part, $p_{i_1}\cdots p_{i_u} y \leq n.$ Donc $p_{i_1}\cdots p_{i_u} y\in\llbracket 1, n\rrbracket.$ Le nombre $p_{i_1}\cdots p_{i_u} y$ est divisible par $p_{i_1}, \dots, p_{i_u}$ donc il appartient à $B_{i_1},\dots,B_{i_u}$ et il appartient à $B_{i_1}\cap\cdots\cap B_{i_u}.$

Vous avez donc l’égalité :

B_{i_1}\cap\cdots\cap B_{i_u} = \left\{ p_{i_1}\cdots p_{i_u}  y, y\in \left[ 1, \frac{n}{p_{i_1}\cdots p_{i_u}} \right]\cap \N\right\}.

Cette écriture montre que le nombre d’éléments de l’ensemble $B_{i_1}\cap\cdots\cap B_{i_u}$ est égal à :

\boxed{\#(B_{i_1}\cap\cdots\cap B_{i_u}) = \frac{n}{p_{i_1}\cdots p_{i_u}}.}

A ce stade il a été démontré que :

\begin{align*}
n-\varphi(n) &=\sum_{u=1}^k (-1)^{u+1}\sum_{\substack{1\leq i_1\leq k\\  \dots\\ 1\leq i_u\leq k\\i_1< \cdots < i_u}}\#(B_{i_1}\cap\cdots\cap B_{i_u})\\
&= \sum_{u=1}^k (-1)^{u+1} \sum_{\substack{1\leq i_1\leq k\\  \dots\\ 1\leq i_u\leq k\\i_1< \cdots < i_u}}  \frac{n}{p_{i_1}\cdots p_{i_u}}.
\end{align*} 

Déterminez une expression de $\varphi(n)$

L’expression précédente se factorise par $n$ si bien que :

\begin{align*}
n-\varphi(n) = n \left(\sum_{u=1}^k (-1)^{u+1} \sum_{\substack{1\leq i_1\leq k\\  \dots\\ 1\leq i_u\leq k\\i_1< \cdots < i_u}}  \frac{1}{p_{i_1}\cdots p_{i_u}}\right).
\end{align*} 

En isolant $\varphi(n)$ vous déduisez :

\begin{align*}
\varphi(n) &=n- n \left(\sum_{u=1}^k (-1)^{u+1} \sum_{\substack{1\leq i_1\leq k\\  \dots\\ 1\leq i_u\leq k\\i_1< \cdots < i_u}}  \frac{1}{p_{i_1}\cdots p_{i_u}}\right)\\
&= n  \left(1-\sum_{u=1}^k (-1)^{u+1} \sum_{\substack{1\leq i_1\leq k\\  \dots\\ 1\leq i_u\leq k\\i_1< \cdots < i_u}}  \frac{1}{p_{i_1}\cdots p_{i_u}}\right)\\
&= n  \left(1+\sum_{u=1}^k (-1)^{u} \sum_{\substack{1\leq i_1\leq k\\  \dots\\ 1\leq i_u\leq k\\i_1< \cdots < i_u}}  \frac{1}{p_{i_1}\cdots p_{i_u}}\right).
\end{align*} 

Or, le développement du produit $\prod_{i=1}^k\left(1-\frac{1}{p_i}\right)$ est précisément égal à :

\left(1+\sum_{u=1}^k (-1)^{u} \sum_{\substack{1\leq i_1\leq k\\  \dots\\ 1\leq i_u\leq k\\i_1< \cdots < i_u}}  \frac{1}{p_{i_1}\cdots p_{i_u}}\right).

Donc vous avez démontré que :

\boxed{\varphi(n) = n\prod_{i=1}^k\left(1-\frac{1}{p_i}\right).}

Déduisez-en que la fonction $\varphi$ est une fonction multiplicative

Soient $r$ et $s$ deux entiers supérieurs ou égaux à $2$ et premiers entre eux.

Vous décomposez $r$ en produit de nombres premiers. Il qu’il existe un entier naturel non nul $\kappa$ ainsi que des entiers naturels non nuls $\alpha_1, \dots, \alpha_{\kappa}$ et des nombres premiers $\xi_1\dots,xi_k$ tels que :

r = \prod_{i=1}^{\kappa}\xi_i^{\alpha_i}.

Vous décomposez $s$ en produit de nombres premiers. Il qu’il existe un entier naturel non nul $\lambda$ ainsi que des entiers naturels non nuls $\beta, \dots, \beta{\lambda}$ et des nombres premiers $\zeta_1\dots, \zeta_{\lambda}$ tels que :

s = \prod_{j=1}^{\lambda}\zeta_j^{\beta}.

Comme $r$ et $s$ sont premiers entre eux, quel que soit $(i,j)\in\llbracket 1, \kappa\rrbracket \times \llbracket 1, \lambda\rrbracket$ vous avez $\xi_i \neq \zeta _j.$ Donc vous avez directement la décomposition en produit de facteurs premiers du nombre $rs$ qui est :

rs = \left(\prod_{i=1}^{\kappa}\xi_i^{\alpha_i}\right) \left(\prod_{j=1}^{\lambda}\zeta_j^{\beta}\right).

Vous déduisez de cette écriture que :

\begin{align*}
\varphi(rs) &= rs \prod_{i=1}^{\kappa}\left(1-\frac{1}{\xi_i}\right) \prod_{i=j}^{\lambda}\left(1-\frac{1}{\zeta_j}\right) \\
&=\left(r \prod_{i=1}^{\kappa} \left(1-\frac{1}{\xi_i}\right) \right)\left(s \prod_{j=1}^{\lambda} \left(1-\frac{1}{\zeta_j}\right) \right)\\
&=\varphi(r)\varphi(s).
\end{align*}

Et vous concluez : la fonction d’Euler $\varphi$ est multiplicative :

\boxed{\forall (r,s)\in\N^2, \left\{\begin{align*} &r\geq 2\\&s\geq 2\\&PGCD(r,s)=1\end{align*}\right. \implies\varphi(rs)=\varphi(r)\varphi(s).}

Il s’agit d’un test de calcul modulaire qui permet de démontrer, sans effectuer de divisions successives, qu’un nombre donné n’est pas premier.

Démontrez un lemme

Pour tout entier naturel $n$ supérieur ou égal à $2$ vous notez $\mathscr{P}(n)$ la propriété « il existe un entier naturel $t$ et un entier naturel impair $q$ tels que $n = 2^t q$ ».

Initialisation. Pour $n=2$, vous posez $t = 1$ et $q=1.$ Vous avez bien $2^t q = 2^1 \times 1 = 2 = n.$ Donc $\mathscr{P}(2)$ est vraie.

Hérédité. Soit $n$ un entier supérieur ou égal à $2.$ Supposez que $\mathscr{P}(2),\dots, \mathscr{P}(n)$ sont vraies.

Notez déjà que $n+1\geq 3.$ Si $n+1$ est impair, alors vous posez $t = 0$ et $q = n+1.$ Vous avez immédiatement $2^t q = 2^0 \times (n+1) = n+1.$

Si $n+1$ est pair, il s’ensuit que $n+1\geq 4.$ Alors $m = \frac{n+1}{2}$ est un entier supérieur ou égal à $2.$

Comme $n\geq 1$ il vient $2n \geq n+1$ et donc $\frac{n+1}{2}\leq n.$

Comme $m\in\llbracket 2, n\rrbracket$ vous appliquez l’hypothèse de récurrence. Il existe un entier naturel $t’$ et un entier naturel impair $q$ tels que $m = 2^{t’} q.$ Du coup $2m = 2^{1+t’}q$ ce qui s’écrit $n+1 = 2^{1+t’} q.$ En posant $t = 1+t’$ vous constatez que $t\in\N$ et vous avez bien $n+1 = 2^t q.$

Donc $\mathscr{P}(n+1)$ est vraie.

Conclusion. Par récurrence forte, il a été démontré que :

\boxed{\forall n\in\N, n\geq 2\implies (\exists t \in\N, \exists q\in\N, n = 2^tq\text{ et }q\text{ est impair}).}

Soient $t, q, u, r$ quatre entiers naturels avec $2^t q = 2^u r$ et $q$ et $r$ impairs.

Si $t> u$ alors $t\geq u+1.$ Vous avez $2^{t-u} q = r.$ Or, $t-u \geq 1$ donc $2^{t-u}q$ est pair. Or $r$ est impair, contradiction.

Si $u> t$ alors $u\geq t+1.$ Vous avez $q = 2^{u-t} r.$ Or, $u-t \geq 1$ donc $2^{u-t}r$ est pair. Or $q$ est impair, contradiction.

Du coup, $u=t.$ Ainsi $2^t q = 2^t r$ et $q=r.$

En définitive l’unicité est démontrée.

\boxed{\forall n\in\N, n\geq 2\implies (\exists! t \in\N, \exists !q\in\N, n = 2^tq\text{ et }q\text{ est impair}).}

Descriptif du test de Miller en base $b$

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

Soit $n$ un entier naturel impair. D’après le lemme, il existe un unique entier naturel $t$ et un unique entier naturel impair $q$ tels que $n-1 = 2^t q.$ Notez que $t=0$ entraîne $n-1 =q$ et $n-1$ serait impair donc $n$ serait pair ce qui est absurde, donc $t \geq 1.$

Vous direz que $n$ passe le test de Miller en base $b$, si et seulement si :

\boxed{(b^q\equiv 1 \mod n) \text{ ou } (\exists s\in\llbracket 0, t-1\rrbracket, b^{2^s q}\equiv -1 \mod n).}

Note. Un nombre entier supérieur ou égal à $2$ qui passe le test de Miller en base $b$ peut ne pas être premier. Dans ce dernier cas précis, il est qualifié de nombre pseudo-premier fort en base $b.$

L’intérêt du test de Miller réside dans le théorème ci-dessous.

Tout nombre premier $p$ impair passe le test de Miller en base $b$ dès que $b$ n’est pas multiple de $p$

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

Soit $p$ un nombre premier impair tel que $b$ ne soit pas un multiple de $p.$

Comme $p-1$ est pair, il existe un unique entier naturel $t$ et un unique entier impair $q$ tels que $p-1 = 2^t q.$

S’il existe $s\in\llbracket 0, t-1\rrbracket, b^{2^s q}\equiv -1 \mod p$ alors $p$ passe le test de Miller en base $b.$

Si un tel entier $s$ n’existe pas, cela signifie ce qui suit :

\forall s\in\llbracket 0, t-1\rrbracket, b^{2^sq}\not\equiv -1 \mod p.

Pour tout entier naturel $u$ vous notez $\mathscr{P}(u)$ la propriété « $b^{2^u q} \equiv 1 \mod p$. » Vous procédez par récurrence descendante.

Initialisation. Pour $u = t$ vous cherchez à évaluer $b^{2^uq} = b^{2^tq} = b^{p-1}.$ Comme $PGCD(b,p)$ divise $p$, ce nombre vaut $1$ ou $p$ car $p$ est premier. Si $PGCD(b,p)=p$ alors $p$ divise $b$ ce qui est absurde. Donc $PGCD(b,p)=1.$ L’application du petit théorème de Fermat fournit $b^{p-1} \equiv 1\mod p$ ce qui prouve que $\mathscr{P}(t)$ est vraie.

Caractère descendant. Soit $u$ un nombre entier appartenant à l’intervalle $\llbracket 1, t \rrbracket.$ Supposez $\mathscr{P}(u)$ vraie.

Alors $b^{2^u q} \equiv 1 \mod p.$ Vous en déduisez que :

\begin{align*}
\left(b^{2^{u-1} q}\right)^2 \equiv 1 \mod p\\
\left(b^{2^{u-1} q}\right)^2 -1^2 \equiv 0 \mod p\\
\left(b^{2^{u-1} q}-1\right)\left(b^{2^{u-1} q}+1\right) \equiv 0 \mod p.
\end{align*}

Donc $p$ divise le produit $\left(b^{2^{u-1} q}-1\right)\left(b^{2^{u-1} q}+1\right).$

Cependant, notez que $u-1\in\llbracket 0, t-1\rrbracket$ donc $b^{2^{u-1}q}\not\equiv -1 \mod p$ donc $p$ ne divise pas $b^{2^{u-1} q}+1.$

Utilisant le lemme d’Euclide, vous déduisez que $p$ divise $b^{2^{u-1} q}-1$ et donc $b^{2^{u-1} q}\equiv 1 \mod p.$

La propriété $\mathscr{P}(u-1)$ est vraie.

Conclusion. Il a été démontré par récurrence descendante que $\mathscr{P}(0)$ est vraie, autrement dit $b^{2^0 q} \equiv 1 \mod n$ ce qui fournit $b^{ q} \equiv 1 \mod p.$

Ainsi $p$ passe le test de Miller en base $b.$

Application : démontrez que $1387$ n’est pas un nombre premier

Tout nombre premier $p$ passe le test de Miller en base $b$ dès que $PGCD(b,p)=1.$

Par contraposée, si $n$ est un nombre entier supérieur ou égal à $2$ de sorte que :

• il existe une base $b$ vérifiant $PGCD(b,n)=1$
• le nombre $n$ ne passe pas le test de Miller en base $b$

alors $n$ n’est pas premier.

Note. En pratique la base $b$ est choisie pour être strictement inférieure à $n$. S’il s’avère que $PGCD(b,n)\geq 2$ alors ce nombre est déjà un diviseur de $n$ compris entre $2$ et $n-1.$ Il est inutile de pratiquer le test de Miller puisque $n$ est déjà non premier.

Pour le nombre $n = 1387$ vous choisissez $b=2$ pour base. Comme $1387$ est impair, $PGCD(n,b)=1.$ Vous appliquez le test de Miller à $1387$ en base $2.$

Tout d’abord :

\begin{align*}
n-1 &= 1386\\
&= 2\times 693.
\end{align*} 

Par conséquent $t = 1$ et $q = 693.$

Vous évaluez $2^{693} \mod 1387.$

D’une part :

\begin{align*}
2^{10}&\equiv 1024 \mod 1387\\
2^{20}&\equiv 1024^2 \mod 1387\\
2^{20}&\equiv 1048576 \mod 1387\\
2^{20}&\equiv 756\times 1387+ 4 \mod 1387\\
2^{20}&\equiv  2^2 \mod 1387.
\end{align*} 

Comme $PGCD(2, 1387)=1$ vous pouvez simplifier la congruence deux fois par $2$ grâce au théorème de Gauss, ce qui fournit :

\boxed{2^{18}\equiv 1\mod 1387.}

D’autre part, vous effectuez la division euclidienne de $693$ par $18$ ce qui fournit :

693 = 18\times 38 + 9.

Du coup :

\begin{align*}
2^{693} &\equiv 2^9 \times (2^{18})^{38} \mod 1387\\
&\equiv 512\mod 1387.
\end{align*} 

Comme $2^{693}$ n’est ni congru à $1$ ni congru à $-1$ modulo $1387$, $1387$ ne passe pas le test de Miller en base $2$ donc $1387$ n’est pas premier.

Application : démontrez que le nombre $1\,373\,653$ n’est pas premier

Il s’agit de déterminer $t$ et $q.$

Vous notez $n = 1373653$ et par suite :

\begin{align*}
n-1 &= 1\,373\,652 \\
&= 2\times 686\,826\\
&= 4\times 343\,413.
\end{align*}

Vous choisissez $b=5$ pour base et allez effectuer le calcul de $5^{343\,413}$ modulo $1\,373\,653.$ Pour plus de lisibilité, les congruences qui suivent sont toutes effectuées modulo $1\,373\,653.$

\begin{align*}
5^2 &= 25\\
5^4 &= 25^2 =625 \\
5^8 &= 625^2 = 360\,425+024\,200+006\,000 = 360\,425+30\,200 =390\,625\\
5^{16} &\equiv 390\,625^2 \equiv 152\,587\,890\,625 \equiv 1\,373\,653\times 111\,081 + 1\,141\,732\\
5^{16} &\equiv 1\,141\,732\\
5^{32} &\equiv 1\,141\,732^2 \equiv 1\,303\,551\,959\,824 \equiv 948\,967\times 1\,373\,653+593\,373\\
5^{32} &\equiv 593\,373\\
5^{64} &\equiv 593\,373^2 \equiv  352\,091\,517\,129 \equiv 256\,317\times 1\,373\,653+901\,128\\
5^{64} &\equiv 901\,128\\
5^{128} &\equiv 901\,128^2   \equiv 812\,031\,672\,384 \equiv 591\,147\times 1\,373\,653+822\,393\\
5^{128} &\equiv 822\,393
\end{align*}

\begin{align*}
5^{256} &\equiv 822\,393^2   \equiv 676\,330\,246\,449 \equiv 492\, 358\times 1\,373\,653 + 1\,202\,675\\
5^{256} &\equiv 1\,202\,675\\
5^{512} &\equiv 1\,202\,675^2   \equiv 1\,446\,427\,155\,625 \equiv 1\,052\,978\times 1\,373\,653+ 766\,991\\
5^{512} &\equiv 766\,991\\
5^{1024} &\equiv 766\,991^2   \equiv 588\,275\,194\,081 \equiv 428\,256\times 1\,373\,653+ 54\,913\\
5^{1024} &\equiv 54\,913\\
5^{2048} &\equiv 54\,913^2   \equiv 3\,015\,437\,569 \equiv 2\,195\times 1\,373\,653+ 269\,234\\
5^{2048} &\equiv 269\,234\\
5^{4096} &\equiv 269\,234^2   \equiv 72\,486\,946\,756 \equiv 52\,769\times 1\,373\,653+ 651\,599\\
5^{4096} &\equiv 651\,599
\end{align*}

\begin{align*}
5^{8192} &\equiv 651\,599^2   \equiv 424\,581\,256\,801 \equiv 309\,089\times 1\,373\,653 + 224\,684\\
5^{8192} &\equiv 224\,684\\
5^{16384} &\equiv 224\,684^2   \equiv 50\,482\,899\,856 \equiv 36\,750\times 1\,373\,653 + 1\,152\,106\\
5^{16384} &\equiv 1\,152\,106\\
5^{32768} &\equiv 1\,152\,106^2   \equiv 1\,327\,348\,235\,236 \equiv 966\,290\times 1\,373\,653 + 1\,077\,866\\
5^{32768} &\equiv 1\,077\,866\\
5^{65536} &\equiv 1\,077\,866^2   \equiv 1\,161\,795\,113\,956 \equiv 845\,770\times 1\,373\,653 + 616\,146\\
5^{65536} &\equiv 616\,146\\
5^{131072} &\equiv 616\,146^2   \equiv 379\,635\,893\,316 \equiv 276\,369\times 1\,373\,653 + 787\,359\\
5^{131072} &\equiv 787\,359\\
\end{align*}

\begin{align*}
5^{262144} &\equiv 787\,359^2   \equiv 619\,934\,194\,881 \equiv 451\,303\times 1\,373\,653 + 475\,022\\
5^{262144} &\equiv 475\,022.
\end{align*}

Vous décomposez $343\,413$ comme une somme de puissances de $2$ à l’aide de soustractions.

\begin{align*}
343\,413 -262\,144 &= 81\,269\\
81\,269 - 65\,536&=15\,733\\
15\,733 - 8\,192 &=7\,541\\
7\,541 - 4\,096 &= 3\,445\\
3\,445- 2\,048 &=1\,397\\
1\,397-1\,024 &= 373\\
373 - 256 &= 117\\
117-64 &= 53\\
53 - 32 &= 21\\
21- 16 &= 5\\
5- 4 &=1.
\end{align*} 

Cela montre que :

\begin{align*}
343\,413 &= 262\,144+65\,536+8\,192\\
&\quad+4\,096+2\,048+1\,024\\
&\quad+256+64+32\\
&\quad+16+4+1.
\end{align*} 

Vous calculez les puissances suivantes :

\begin{align*}
5^{262\,144}\times 5^{65\,536}\times 5^{8\,192} &\equiv 475\,022\times 616\,146 \times 224\,684\\
&\equiv 65\,761\,165\,874\,653\,008\\
&\equiv 47\,873\,200\,782\times 1\,373\,653 + 856\,362\\
&\equiv 856\,362
\end{align*}

\begin{align*}
5^{4\,096}\times 5^{2\,048}\times 5^{1\,024} &\equiv 651\,599\times 269\,234 \times 54\,913\\
&\equiv 9\,633\,530\,647\,480\,558\\
&\equiv 7\,013\,074\,369\times 1\,373\,653 + 1\,280\,601\\
&\equiv 1\,280\,601
\end{align*}

\begin{align*}
5^{256}\times 5^{64}\times 5^{32} &\equiv 1\,202\,675\times 901\,128 \times 593\,373\\
&\equiv 643\,076\,365\,633\,990\,200\\
&\equiv 468\,150\,519\,551\times 1\,373\,653 + 1\,200\,397\\
&\equiv 1\,200\,397
\end{align*}

\begin{align*}
5^{16}\times 5^{4}\times 5^{1} &\equiv 1\,141\,732 \times 625 \times 5\\
&\equiv 3\,567\,912\,500\\
&\equiv 2\,597\times 1\,373\,653 + 535\,659\\
&\equiv 535\,659.
\end{align*}

Puis :

\begin{align*}
5^{343\,413} &\equiv 856\,362\times 1\,280\,601 \times 1\,200\,397 \times 535\,659\\
&\equiv 705\,154\,906\,313\,747\,945\,181\,126\\
&\equiv 513\,342\,821\,159\,163\,154 \times 1\,373\,653 +1\,199\,564\\
&\equiv 1\,199\,564.
\end{align*} 

Vous calculez $5^{686\,826}$ comme suit :

\begin{align*}
5^{686\,826} &\equiv 5^{343\,413\times 2}\\
 &\equiv (5^{343\,413})^2\\
&\equiv 1\,199\,564^2\\
&\equiv 1\,438\,953\,790\,096\\
&\equiv 1\,047\,538\times 1\,373\,653+73\,782\\
&\equiv 73\,782.
\end{align*} 

Il a été démontré que :

\left\{\begin{align*}
5^{343\,413}&\not\equiv 1\\
5^{343\,413}&\not\equiv -1\\
5^{686\,826}&\not\equiv -1.
\end{align*} \right.

Cela prouve que le nombre $1\,373\,653$ ne passe pas le test de Miller en base $5.$ Ainsi $1\,373\,653$ n’est pas un nombre premier.

Prolongements

Première partie

Soit $n$ un nombre entier impair supérieur ou égal à $3$ et strictement inférieur à $2\,047.$

Démontrez que $n$ est premier, si et seulement si, il passe le test de Miller en base $2.$

Deuxième partie

Soit $n$ un nombre entier impair supérieur ou égal à $3$ et strictement inférieur à $10\,000.$

Démontrez que $n$ est premier, si et seulement si, il passe le test de Miller en base $2$ et s’il n’appartient pas à l’ensemble $A$ suivant :

A=\{2\,047, 3\,277, 4\,033, 4\,681, 8\,321\}.

Troisième partie

Soit $n$ un nombre entier impair ou égal à $3$ et strictement inférieur à $1\,373\,653.$

Démontrez que $n$ est premier, si et seulement si, il passe le test de Miller en base $2$ et en base $3.$

Soit $b$ un nombre entier supérieur ou égal à $2$ qui sera appelé base et soit $x$ un nombre réel strictement compris entre $0$ et $1.$

Un exemple en base $10$, l’écriture décimale de 3/22

Vous allez déterminer le développement en base $10$ du nombre $\frac{3}{22}.$

Une première idée consiste à effectuer la division de $3$ par $22.$

\begin{array}{cccc|c}
3,&0 & 0 & 0& 22
\\ \hline
3 &0& & &0,136
\\
0 & 8 &0& &
\\
0 & 1 & 4 &0
\\
& & & 8
\end{array}

Vous constatez que, lorsque vous allez abaisser un zéro pour trouver le quatrième chiffre après la virgule, vous allez devoir diviser $80$ par $22$ or ce calcul a déjà effectué précédemment, le quotient est $3.$ Puis vous allez trouver un reste de $14$ ce qui va aboutir à la division de $140$ par $22$ qui fournira $6$ de quotient, et ainsi de suite.

Ainsi :

\frac{3}{22} = 0,13636363636\dots

Les pointillés signifient ici que la séquence $36$ se répète indéfiniment. Vous la noterez ainsi :

\frac{3}{22} = 0,1\overline{36}.

Dans le développement précédent, le chiffre $1$ constitue la prépériode et la séquence $36$ constitue la période. Le nombre de chiffres de la prépériode est $1$ et le nombre de chiffre de la période est de $2.$

Note. Vous pouvez aussi considérer que :

\frac{3}{22} = 0,13\overline{63}.

Vous avez changé de prépériode et de période.

Analyse : cas où le nombre $x$ admet un développement périodique

Dans le cas général, vous allez supposer que $x$ admet un développement propre, périodique de longueur $k$ précédé d’une prépériode de longueur $N.$

En base $b$ le nombre $x$ s’écrit :

x = (0,c_1\dots c_N\overline{c_{N+1}\dots c_{N+k}} )_b.

Les entiers $c_1,\dots c_{N+k}$ vérifient :

\forall i\in\llbracket 1, N+k\rrbracket, 0\leq c_i \leq b-1.

De plus, comme le développement est propre, il est impossible d’avoir $\forall i\in\llbracket N+1,N+k\rrbracket c_i = b-1.$ Autrement dit :

\exists \ell\in\llbracket N+1,N+k\rrbracket, c_{\ell} \neq b-1.

Vous pouvez maintenant procéder au calcul de $x$ à l’aide des sommes suivantes :

\begin{align*}
x &= \frac{c_1}{b}+\cdots+\frac{c_N}{b^N}+\frac{c_{N+1}}{b^{N+1}}+\cdots+\frac{c_{N+k}}{b^{N+k}}\\
 &\quad +\frac{c_{N+1}}{b^{N+k+1}}+\cdots+\frac{c_{N+k}}{b^{N+2k}}\\
&\quad +\frac{c_{N+1}}{b^{N+2k+1}}+\cdots+\frac{c_{N+k}}{b^{N+3k}}
\\
&=\frac{c_1}{b}+\cdots+\frac{c_N}{b^N} \\
&\quad+ \frac{c_{N+1}}{b^{N+1}}\left(1+\frac{1}{b^k}+\frac{1}{b^{2k}}+\cdots\right) \\
&\quad + \cdots +  \frac{c_{N+k}}{b^{N+k}}\left(1+\frac{1}{b^k}+\frac{1}{b^{2k}}+\cdots\right)
\\
&=\frac{c_1}{b}+\cdots+\frac{c_N}{b^N} \\
&\quad + \left(\frac{c_{N+1}}{b^{N+1}}+ \cdots +\frac{c_{N+k}}{b^{N+k}} \right)\left(1+\frac{1}{b^k}+\frac{1}{b^{2k}}+\cdots\right).
\end{align*}

Vous évaluez la somme infinie en utilisant le fait qu’elle est en progression géométrique de raison $\frac{1}{b^k}.$

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

Du coup, vous déduisez :

\begin{align*}
x &= \sum_{i=1}^N \frac{c_i}{b^i} + \frac{b^k}{b^k-1} \sum_{i=1}^k \frac{c_{N+i}}{b^{N+i}} \\
&= \sum_{i=1}^N \frac{b^{N-i}c_i} {b^N} + \frac{b^k}{b^k-1} \sum_{i=1}^k \frac{b^{k-i}c_{N+i}}{b^{N+k}} \\
&=  \frac{\sum_{i=1}^N b^{N-i}c_i} {b^N} +\frac{1}{b^k-1} \sum_{i=1}^k \frac{b^{k-i}c_{N+i}}{b^{N}} \\ 
&=  \frac{\sum_{i=1}^N b^{N-i}c_i} {b^N} +\frac{1}{b^k-1} \times  \frac{\sum_{i=1}^k b^{k-i}c_{N+i}}{b^{N}} \\ 
&=  \frac{(b^k-1)\sum_{i=1}^N b^{N-i}c_i + \sum_{i=1}^k b^{k-i}c_{N+i}} {b^N(b^k-1) }.
\end{align*}

En posant $a = (b^k-1)\sum_{i=1}^N b^{N-i}c_i + \sum_{i=1}^k b^{k-i}c_{N+i}$ vous constatez que $a\in\N$ et que $x=\frac{a}{b^N(b^k-1)}$ qui est le quotient de deux entiers. Le nombre $x$ est donc rationnel. Avant d’effectuer la synthèse, vous allez démontrer un lemme bien utile.

\lfloor u\rfloor \leq u < \lfloor u\rfloor +1.

\lfloor u\rfloor + m \leq u+m < (\lfloor u\rfloor + m) +1.

\lfloor u\rfloor+m = \lfloor u+m\rfloor.

\boxed{\forall u\in\R, \forall m\in\Z,  \lfloor u+m\rfloor = \lfloor u \rfloor + m.}

Synthèse : cas où le nombre $x$ est rationnel

Comme $0<x<1$, $x$ admet une unique forme irréductible, il existe un unique entier $r$ non nul et un unique $s$ non nul tels que :

\left\{\begin{align*}
&x=\frac{r}{s}\\
&PGCD(r,s)=1.
\end{align*}
\right.

Notez que si $s=1$ alors $x$ est entier, ce qui contredit $x\in]0,1[.$ Donc $s\geq 2.$

Le but va consister à montrer que $x$ peut s’écrire comme un quotient de deux entiers avec un dénominateur égal à $b^N(b^k-1)$ où $N$ est un entier naturel et $k$ un entier naturel non nul.

Notez $B$ l’ensemble des nombres premiers qui divisent la base $b.$ En écrivant $b$ comme produit de nombres premiers, vous déduisez que pour chaque élément $p$ de $B$, il existe un entier naturel non nul $\nu(p)$ de sorte que:

b = \prod_{p\in B} p^{\nu(p)}.

Le dénominateur $s$ admet une décomposition en produit de nombres premiers. Notez $S$ l’ensemble des nombres premiers qui divisent $s.$ En écrivant $s$ comme produit de nombres premiers, vous déduisez que pour chaque élément $p$ de $S$, il existe un entier naturel non nul $\mu(p)$ de sorte que:

Ainsi:

s = \prod_{p\in S} p^{\mu(p)}.

Comme $S$ est l’union disjointe de $S\cap B$ et de $S\cap \overline{B}$ (formé par les nombres premiers $p$ qui divisent $s$ mais pas $b$) vous avez:

s = \prod_{p\in S\cap B} p^{\mu(p)} \times  \prod_{p\in S\cap \overline{B}} p^{\mu(p)}.

Vous posez $T = \prod_{p\in S\cap B} p^{\mu(p)}$ et $U = \prod_{p\in S\cap \overline{B}} p^{\mu(p)}.$

Notez que si $S\cap B$ est vide, par définition, $T$ est égal à $1.$ De même, si $S\cap \overline{B}$ est vide, alors $U=1.$

Dans les autres cas, si $T\geq 2$ (ce qui correspond au cas où $S\cap B$ est non vide) les facteurs premiers de $T$ apparaissent tous dans la décomposition en facteurs premiers de $b.$ D’autre part, si $U\geq 2$ (ce qui correspond au cas où $S\cap \overline{B}$ est non vide) les facteurs premiers de $U$ sont tous différents de ceux apparaissant dans $b.$

Vous déduisez que ces observations que $PGCD(U,b)=1$ et qu’il existe un nombre entier naturel $N$ (vous choisissez parmi ceux qui conviennent le plus petit d’entre eux) tel que $T$ divise $b^N.$

Comme $U$ et $b$ sont premiers entre eux, en notant $k$ l’ordre de $b$ modulo $U$, vous avez:

b^k\equiv 1 \mod U.

Il en résulte qu’il existe un entier $\alpha$ et un entier $\beta$ tels que:

b^N = \alpha T\\
b^k-1 = \beta U.

Reprenant l’écriture de $x$ vous obtenez:

\begin{align*}
x &= \frac{r}{s}\\
&= \frac{r}{TU}\\
&= \frac{\alpha\beta r}{\alpha T \beta U}\\
&=\frac{\alpha\beta r}{b^N(b^k-1)}.
\end{align*}

Maintenant que cette écriture est acquise, vous allez pouvoir démontrer que le développement en base $b$ de $x$ est $k$-périodique à partir du rang $N+1.$

Soit $n$ un entier supérieur ou égal à $N+1.$ Prenant les conclusions du contenu rédigé dans l'article 368 vous avez :

\left\{\begin{align*}
c_n &= \lfloor b^nx \rfloor-b  \lfloor b^{n-1}x \rfloor\\
c_{n+k} &= \lfloor b^{n+k}x \rfloor-b  \lfloor b^{n+k-1}x \rfloor.
\end{align*} \right.

Note. Remarquez que $c_1 = \lfloor b x \rfloor = \lfloor b^1 x \rfloor – b \lfloor b^0 x \rfloor$ vu que $\lfloor x \rfloor = 0.$

Comme $b^N(b^k-1)x = \alpha \beta r$ vous déduisez que $b^N(b^k-1)x$ est un entier, donc $b^{N+k} x-b^N x$ est un entier. Comme $n\geq N$, $b^{n-N}$ est un entier et par produit $b^{n-N}(b^{N+k} x-b^N x)$ est entier donc $b^{n+k} x-b^n x$ est un entier.

D’après le lemme :

\begin{align*}
\lfloor  b^{n+k}x \rfloor  &= \lfloor  (b^{n+k}x  - b^n x) + b^n x\rfloor \\
&=b^{n+k}x  - b^n x + \lfloor  b^{n}x \rfloor.
\end{align*}

De même, $n\geq N+1$ donc $b^{n-N-1}$ est un entier et par produit $b^{n-N-1}(b^{N+k} x-b^N x)$ est entier donc $b^{n+k-1} x-b^{n-1} x$ est un entier.

Du coup, toujours d’après le lemme :

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

En multipliant par $b$ vous avez :

\begin{align*}
b\lfloor  b^{n+k-1}x \rfloor  &=b^{n+k}x  - b^{n} x + b\lfloor  b^{n-1}x \rfloor.
\end{align*}

Par soustraction vous avez obtenu :

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

Du coup $c_{n+k} = c_n.$

Il vient d’être démontré que :

\forall n\geq N+1, c_{n+k} = c_n.

Le développement propre de $x$ en base $b$ est bien $k$-périodique à partir du rang $N+1.$

Compléments sur la prépériode et la période

D’après ce qui précède, $x$ est rationnel, si et seulement si, son développement propre en base $b$ est périodique à partir d’un certain rang.

Vous supposez maintenant que $x = \frac{r}{TU}$ est rationnel, de sorte qu’il existe un entier naturel $N$ minimal tel que $T$ divise $b^N$, $U$ un entier naturel non nul premier avec $b$ et $PGCD(r, TU)=1.$ Vous développez $x$ en base $b$, vous notez $M$ la longueur de la prépériode de ce développement (éventuellement nulle) et et $\ell$ la longueur de la période de celui-ci (supérieure ou égale à $1$).

Alors :

x = (0,c_1\dots c_M\overline{c_{M+1}\dots c_{M+\ell}} )_b.

Les calculs effectués précédemment ont montré que :

x=  \frac{(b^{\ell}-1)\sum_{i=1}^M b^{M-i}c_i + \sum_{i=1}^{\ell} b^{\ell-i}c_{M+i}} {b^M(b^{\ell}-1) } = \frac{r}{TU}.

Par produit, cela devient :

TU\left((b^{\ell}-1)\sum_{i=1}^M b^{M-i}c_i + \sum_{i=1}^{\ell} b^{\ell-i}c_{M+i}\right) = rb^M(b^{\ell}-1).

Donc $T$ divise le produit $rb^M(b^{\ell}-1).$ Comme $PGCD(r,TU)=1$ vous avez aussi $PGCD(r,T)=1.$ D’après le théorème de Gauss, $T$ divise $b^M(b^{\ell}-1).$ Supposez $PGCD(T, b^{\ell}-1) > 1.$ Il existe un nombre premier $p$ qui divise $PGCD(T, b^{\ell}-1).$ Alors $p$ divise $T.$ Par définition de $T$, $p$ divise $b$, donc $p$ divise $b^{\ell}.$ Or $p$ divise aussi $b^{\ell}-1$ donc par différence $p$ divise $1$ ce qui est absurde. Donc $PGCD(T, b^{\ell-1})=1.$ Toujours par le théorème de Gauss, $T$ divise $b^M.$ Or $N$ est le plus petit entier naturel tel que $T$ divise $b^N$, par suite $M\geq N.$

La prépériode est toujours supérieure ou égale à $N$, où :

N = \min\{\xi\in\N, T\mid b^{\xi}\}.

Reprenant l’égalité $TU\left((b^{\ell}-1)\sum_{i=1}^M b^{M-i}c_i + \sum_{i=1}^{\ell} b^{\ell-i}c_{M+i}\right) = rb^M(b^{\ell}-1)$ vous déduisez que $U$ divise $rb^M(b^{\ell}-1).$ Comme $PGCD(r,TU)=1$ vous avez $PGCD(r,U)=1.$ La théorème de Gauss permet d’affirmer que $U$ divise $b^M(b^{\ell}-1).$ Or, $PGCD(U,b)=1$ donc $PGCD(U,b^M)=1$ et via la théorème de Gauss, $U$ divise $b^{\ell}-1$ donc $b^{\ell}\equiv 1 \mod U$ donc $\ell$ est un multiple de l’ordre de $b$ modulo $U.$

En notant $k$ l’ordre de $b$ modulo $U$, il apparaît que la période est toujours un multiple de $k.$

Conclusion

Soit $b$ un nombre entier supérieur ou égal à $2$ qui sera appelé base et soit $x$ un nombre réel strictement compris entre $0$ et $1.$

Le développement propre de $x$ en base $b$ est périodique à partir d’un certain rang, si et seulement si, $x$ est rationnel.

Si $x$ est rationnel, il existe un unique entier $r$ non nul et un unique entier $s\geq 2$ avec $PGCD(r,s)=1$ tels que :

x = \frac{r}{s}.

Vous décomposez $s$ sous la forme $s = TU$ où l’entier non nul $T$ est formé par la partie de la décomposition en facteurs premiers de $s$ comportant tous les nombres premiers qui divisent la base $b$ (s’il n’y en a pas, $T=1$.) $U$ l’entier non nul formé par la partie de la décomposition en facteurs premiers de $s$ comportant tous les nombres premiers qui ne divisent pas la base $b.$

En notant $\boxed{N = \min\{\xi\in\N, T\mid b^{\xi}\} }$ et $\boxed{k = \text{l’ordre de } b\text{ modulo }U}$ , $x$ admet dans son développement propre en base $b$, $k$-périodique, avec une prépériode de longueur $N.$

De plus, si on choisit une autre prépériode ou une autre période dans le développement de $x$ en base $b$, alors la longueur de cette prépériode sera supérieure ou égale à $N$ et la longueur de la période sera supérieure ou égale à $k.$

Reprise de l’exemple du début, calcul préalable de la prépériode et de la période de 3/22

Sans poser de division, on peut savoir que $\frac{3}{22}$ admet un développement décimal propre périodique et déterminer sa prépériode la plus courte ainsi que sa période la plus courte.

En décimal, l’écriture de la base $b$ en produit de nombres premiers est égale à $10 = 2\times 5.$

Vous écrivez maintenant $22$ en produit de nombres premiers :

22 = 2\times 11.

Vous séparez ceux qui apparaissent dans la décomposition de $b$ des autres.

Vous obtenez $T = 2$ et $U = 11.$ Vous avez $N = \min\{\xi\in\N, T\mid 10^{\xi}\} = 1.$ La prépériode a pour longueur $1.$

Il reste maintenant à chercher l’ordre $k$ de $10$ modulo $11$.

\left\{\begin{align*}
10^1 \equiv -1 \mod 11\\
10^2 \equiv 1 \mod 11.
\end{align*}
\right.

Vous avez obtenu $k = 2$ donc la période sera égale à $2.$

Vous allez maintenant utiliser $3$ divisions pour obtenir les chiffres intervenant dans le développement de $3/22.$

D’après ce qui précède, il suffit de calculer $c_1, c_2$ et $c_3.$

c_1 = \left\lfloor 10 \times \frac{3}{22}\right\rfloor =  \left\lfloor  \frac{30}{22}\right\rfloor = 1.

Puis :

\begin{align*}
c_2 &= \left\lfloor 100 \times \frac{3}{22}\right\rfloor - 10 \left\lfloor 10 \times \frac{3}{22}\right\rfloor\\
&=  \left\lfloor  \frac{300}{22}\right\rfloor - 10\times 1\\
&=13-10\\
&=3.
\end{align*}

Enfin :

\begin{align*}
c_3 &= \left\lfloor 1000 \times \frac{3}{22}\right\rfloor - 10 \left\lfloor 100 \times \frac{3}{22}\right\rfloor\\
&=  \left\lfloor  \frac{3000}{22}\right\rfloor - 10\times 13\\
&=136-130\\
&=6.
\end{align*}

Par conséquent :

\frac{3}{22} = 0,c_1\overline{c_2c_3} = 0,1\overline{36}.

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

Il a été démontré dans le contenu rédigé dans l'article 368 et dans celui rédigé dans l'article 367 que $x$ admet un unique développement propre en base $b.$

Il existe une unique suite $(c_i)_{i\geq 1}$ telle que :

\left\{
\begin{align*}
&\forall i\geq 1, 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.

Par définition, vous direz que la représentation de $x$ en base $b$ donnée par $\sum_{i=1}^{+\infty}\frac{c_i}{b^i}$ se termine, si et seulement si, tous les $c_i$ sont nuls à partir d’un certain rang, soit $\exists M\in\NN, \forall n\geq M, c_n = 0.$

Analyse

Supposez que la représentation de $x$ en base $b$ se termine.

Il existe un entier $M$ non nul tel que :

\forall n\geq M, c_n = 0.

Si $M$ était était égal à $1$, alors $x$ serait nul ce qui est absurde. Donc $M$ est supérieur ou égal à $2.$

Vous écrivez maintenant :

\begin{align*}
x &=\sum_{i=1}^{M-1}\frac{c_i}{b^i} +  \sum_{i=M}^{+\infty}\frac{c_i}{b^i}\\
&=\sum_{i=1}^{M-1}\frac{c_i}{b^i} +  \sum_{i=M}^{+\infty}\frac{0}{b^i}\\
&=\sum_{i=1}^{M-1}\frac{c_i}{b^i} +  0\\
&=\sum_{i=1}^{M-1}\frac{c_i}{b^i} \\
&=\sum_{i=1}^{M-1}\frac{b^{M-1-i}c_i}{b^{M-1}} \\
&= \frac{\sum_{i=1}^{M-1}b^{M-1-i}c_i}{b^{M-1}}.
\end{align*} 

Vous posez :

\left\{\begin{align*}
r &= \sum_{i=1}^{M-1}b^{M-1-i}c_i\\
s &= b^{M-1}.
\end{align*}
\right.

Ainsi vous avez $x=frac{r}{s}.$ $s \geq b\geq 2$ vous avez $s$ qui est non nul. Comme $r = sx$ où $x$ est strictement supérieur à $0$, vous déduisez que $s$ et $r$ sont deux entiers strictement positifs. Notez maintenant $d = PGCD(r,s).$ Il existe deux entiers strictement positifs $r’$ et $s’$ tels que $r =dr’$ et $s = ds’.$

D’une part $x = \frac{r}{s} = \frac{dr’}{ds’} = \frac{r’}{s’}$ avec $d = PGCD(dr’,ds’) = d PGCD(r’,s’)$ et donc $1 = PGCD(r’,s’).$

Notez que si $s’ = 1$ alors $x = r’$ et $x$ est entier ce qui est absurde puisque $x\in]0,1[.$ Donc $s’\geq 2.$

Soit maintenant $p$ un facteur premier de $s’.$ $p$ divise $s’$ or $s’$ divise $s = b^{M-1}$ donc $p$ divise $b^{M-1}.$ Par le lemme d’Euclide, $p$ divise $b.$

Par conséquent tous les facteurs premiers de $s’$ sont aussi des facteurs premiers de $b.$

L’analyse est achevée. Si $x$ admet un développement en base $b$ qui se termine, alors il existe deux entiers $r’$ et $s’$ avec $s’\geq 2$ tels que $x = \frac{r’}{s’}$ et $PGCD(r’,s’)=1$ et tous les facteurs premiers de $s’$ sont des facteurs premiers de $b.$

Synthèse

Supposez qu’il existe deux entiers $r’$ et $s’$ avec $s’\geq 2$ tels que $x=\frac{r’}{s’}$ et $PGCD(r’,s’)=1$ et tous les facteurs premiers de $s’$ sont des facteurs premiers de $b.$

Comme $s’$ est un entier supérieur ou égal à $2$ il admet une décomposition en produit de $t$ nombres premiers où $t$ est un entier naturel non nul. Notez $p_1, \dots, p_t$ les $t$ nombres premiers deux à deux distincts qui apparaissent dans cette décomposition. Il existe des entiers naturels non nuls $u_1, \dots, u_t$ tels que :

s' = p_1^{u_1}\times\cdots\times p_t^{u_t}.

Par hypothèse, $p_1,\dots, p_t$ sont des nombres premiers qui apparaissent dans la décomposition de $b.$ Il existe un entier naturel non nul $q$ et des entiers naturels non nuls $v_1, \dots, v_t$ tels que :

b = p_1^{v_1}\times\cdots\times p_t^{v_t}\times q.

Soit $M$ l’entier naturel non nul défini par :

M =\left\lfloor \max\left\{\frac{u_i}{v_i}, 1\leq i\leq t\right\}\right\rfloor+1.

Par définition de la partie entière, vous avez :

M>\max\left\{\frac{u_i}{v_i}, 1\leq i\leq t\right\}.

Du coup :

\forall i\in\llbracket 1, t\rrbracket, \frac{u_i}{v_i}< M.

Ainsi :

\forall i\in\llbracket 1, t\rrbracket, u_i< Mv_i.

En élevant $b$ à la puissance $M$ il vient :

\begin{align*}
b^M &= p_1^{Mv_1}\times\cdots\times p_t^{Mv_t}\times q^M\\
&=(p_1^{u_1}\times\cdots\times p_t^{u_t})\times (p_1^{Mv_1-u_1}\times\cdots\times p_t^{Mv_t-u_t}\times q^M)\\
&=s' \times (p_1^{Mv_1-u_1}\times\cdots\times p_t^{Mv_t-u_t}\times q^M).
\end{align*} 

Vous notez $a$ l’entier naturel non nul défini par $p_1^{Mv_1-u_1}\times\cdots\times p_t^{Mv_t-u_t}\times q^M$ pour avoir :

b^N = s' a.

Vous écrivez alors :

\begin{align*}
x &= \frac{r'}{s'}\\
&=\frac{ar'}{as'}\\
&=\frac{ar'}{b^M}.
\end{align*} 

Comme $0<x<1$ vous déduisez que $0 <ar’ < b^M.$ En décomposant l’entier non nul $ar’$ en base $b$, il existe des entiers $d_0, \dots, d_{M-1}$ vérifiant :

\begin{align*}
&ar' = d_{M-1}b^{M-1}+\cdots+d_0\\
&\forall i\in\llbracket 0, M-1\rrbracket, 0\leq d_i\leq b-1.
\end{align*}

Ainsi :

\begin{align*}
x &= \frac{d_{M-1}b^{M-1}+\cdots+d_0}{b^M}\\
 &= \frac{\sum_{i=0}^{M-1}d_i b^i}{b^M}\\
 &= \sum_{i=0}^{M-1}\frac{d_i }{b^{M-i}}\\
 &= \sum_{j=1}^{M}\frac{d_{M-j} }{b^{j}}.
\end{align*} 

L’écriture obtenue de $x$ est un développement propre en base $b.$ Par unicité de celui-ci :

\left\{\begin{align*}
&\forall j\in\llbracket 1, M\rrbracket, c_j = d_{M-j}\\
&\forall j\geq M+1, c_j = 0.
\end{align*}
\right.

Il a bien été démontré que $x$ admet une écriture en base $b$ qui se termine.

Concluez

Soit $x$ un nombre réel strictement compris entre $0$ et $1.$

Le développement propre de $x$ en base $b$ qui se termine, si et seulement si, il existe deux entiers $r’$ et $s’$ avec $s’\geq 2$ tels que $x = \frac{r’}{s’}$ et $PGCD(r’,s’)=1$ et tous les facteurs premiers de $s’$ sont des facteurs premiers de $b.$

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.$