Un algorithme de Lehmer

(Exercice d’oral Centrale Mp)

  1. Dans cette question, {z=a+ib\in\mathbb{C}} est donné, avec {a\in\mathbb{R}} et {b\in\mathbb{R}^{*}}.

    • Exprimer l’argument de {z} (modulo {\pi}) en fonction de {\text{arctan}\,\dfrac{b}{a}} si {a\ne0}.
      Préciser le cas {a=0}.
    • On pose {\varphi(z)=(-n+i)z}, où {n} est la partie entière de {\dfrac{a}{b}}.

      Montrer que si {b>0} alors {0\le \text{Im}\,\varphi(z)\lt b}.

      Montrer que si {b\lt 0} alors {b\lt \text{Im}\,\varphi(z)\le 0}.

  2. Dans cette question, {a} et {b} sont donnés dans {\mathbb{Z}^{*}}.

    On définit une suite {(z_{k})}, par {z_{0}=a+ib}, de la façon suivante :

    Si {z_{k}} est connu et si {\text{Im}\, z_{k}\ne 0}, on pose {z_{k+1}=\varphi(z_{k})} (voir 1.b).

    • Montrer que la suite {(z_{k})} est finie.

      Il existe donc un plus petit {p\ge1} tel que {\text{Im}\, z_{p}=0}.

    • En déduire l’existence d’entiers {n_{0},\ldots,n_{p-1}} tels que : {\text{arctan}\,\dfrac{b}{a}\equiv\displaystyle\sum_{k=0}^{p-1}\text{arctan}\,\dfrac{1}{n_{k}}\ \mod{\pi}}NB: si {n_{k}=0}, on convient que {\text{arctan}\,\dfrac{1}{n_{k}}\equiv\dfrac\pi2\ \mod{\pi}}.

    • Effectuer les calculs pour {z=20+3i}.

      En déduire : {\text{arctan}\,\dfrac{3}{20}=\text{arctan}\,\dfrac{1}{6}-\text{arctan}\,\dfrac{1}{62}-\text{arctan}\,\dfrac{1}{7628}}

Cliquer ici pour voir (ou cacher) le corrigé

    • Si {a=0}, donc {z=ib}, avec {b\in\mathbb{R}^{*}}, on a : {\arg z\equiv\dfrac\pi2\mod{\pi}}.

      Posons {z=a+ib=\rho\text{e}^{i\,\theta}}, avec {a\ne0} et {\rho=\sqrt{a^{2}+b^{2}}>0}.

      Ainsi {\cos\,\theta=\dfrac{a}{\rho}\ne0}, et {\sin(\,\theta)=\dfrac{b}{\rho}}.

      On en tire {\tan\,\theta=\dfrac{b}{a}}, donc {\,\theta\equiv\text{arctan}\,\dfrac{b}{a}\mod{\pi}}.

      Conclusion : {\arg(ib)\equiv\dfrac\pi2\mod{\pi}}, et {\arg z\equiv\text{arctan}\,\dfrac{b}{a}\mod{\pi}} si {a\ne0}

    • Posons {\varphi(z)=(-n+i)(a+ib)=c+id}, avec {(c,d)} dans {\mathbb{R}^{2}}.

      On a {c=-na-b}, {d=a-bn}, et {n\le\dfrac{a}{b}\lt n+1} par définition de {n}.

      Si {b>0}, alors {nb\le a\lt (n+1)b} donc {0\le d\lt b}, donc {0\le \text{Im}\,\varphi(z)\lt \text{Im}\, z}.

      Si {b\lt 0}, alors {nb\ge a> (n+1)b}, donc {0\ge d>b}, donc {\text{Im}\, z\lt \text{Im}\,\varphi(z)\le 0}.

    • Si {z_{k}} est défini (avec {k\ge0}), posons {z_{k}=x_{k}+iy_{k}}, avec {(x_{k},y_{k})\in\mathbb{R}^{2}}.

      Initialement, {x_{0}=a} et {y_{0}=b} sont dans {\mathbb{Z}^{*}}.

      Par une récurrence évidente (et au vu de la définition de {\varphi}) il est clair que si {z_{k}} existe alors les parties réelles {x_{0},x_{1},\ldots,x_{k}} et les parties imaginaires {y_{0},y_{1},\ldots,y_{k}} sont dans {\mathbb{Z}}.

      De plus, d’après (1.b), on a : {\begin{cases}0\le y_{k}\lt \cdots\lt y_{1}\lt y_{0}=b&\text{\ si\ }b>0\\y_{0}=b\lt y_{1}\lt \cdots\lt y_{k}\le 0&\text{\ si\ }b\lt 0\end{cases}}

      Si {(z_{k})} était infinie, la suite {(|y_{k}|)} serait infinie strictement décroissante dans {\mathbb{N}} (absurde). Il existe donc un premier entier {p\ge1} tel que {\text{Im}\, z_{p}=0} ({z_{p}} existe mais pas {z_{p+1}}).

    • Posons {z_{k}=x_{k}+iy_{k}} pour {0\le k\le p-1} (les {x_{k}} sont dans {\mathbb{Z}}, les {y_{k}} dans {\mathbb{Z}^{*}}).

      Les égalités {z_{k+1}=(-n_{k}+i)z_{k}}, où {n_{k}=\biggl[\dfrac{x_{k}}{y_{k}}\biggr]}, donnent {z_{p}=z_{0}\displaystyle\prod_{k=0}^{p-1}(-n_{k}+i)}.

      On a {\text{Im}\, z_{p}=0} donc {\arg z_{p}\equiv0\ \mod\pi} ({z_{p}\ne0} comme les facteurs du produit).

      De même {\arg z_{0}\equiv \text{arctan}\,\dfrac{b}{a}\ \mod\pi}.

      De même {\arg(-n_{k}+i)\equiv-\text{arctan}\,\dfrac{1}{n_{k}}\ \mod\pi}.

      L’égalité {z_{p}=z_{0}\displaystyle\prod_{k=0}^{p-1}(-n_{k}+i)} donne alors : {0 \equiv \text{arctan}\,\dfrac{b}{a}-\displaystyle\sum_{k=0}^{p-1}\text{arctan}\,\dfrac{1}{n_{k}}\ \mod\pi}Finalement, on a obtenu : {\text{arctan}\,\dfrac{b}{a}\equiv \displaystyle\sum_{k=0}^{p-1}\text{arctan}\,\dfrac{1}{n_{k}}\ \mod\pi}

    • Posons {z_{0}=20+3i}. On a {n_{0}=\biggl[\dfrac{20}{3}\biggr]=6}.

      On en déduit {z_{1}=(-n_{0}+i)z_{0}=(-6+i)(20+3i)=-123+2i}.

      Ensuite {n_{1}=\biggl[\dfrac{-123}{2}\biggr]=-62}.

      Il en découle {z_{2}=(-n_{1}+i)z_{1}=(62+i)(-123+2i)=-7628+i}.

      Enfin {n_{2}=-7628} et {z_{3}=(-n_{2}+i)z_{2}=(7628+i)(-7628+i)\in\mathbb{R}^{-*}}.

      On en déduit {p=2} et {[n_{0},n_{1},n_{2}]=[6,-62,-7628]}.

      Il en découle la formule : {\text{arctan}\,\dfrac{3}{20}=\text{arctan}\,\dfrac{1}{6}-\text{arctan}\,\dfrac{1}{62}-\text{arctan}\,\dfrac{1}{7628}\ \mod\pi}Mais on voit facilement que les deux membres sont dans {]-\pi/2,\pi/2\,[}.

      On a donc prouvé l’égalité : {\text{arctan}\,\dfrac{3}{20}=\text{arctan}\,\dfrac{1}{6}-\text{arctan}\,\dfrac{1}{62}-\text{arctan}\,\dfrac{1}{7628}}