Pondichéry 2012. Enseignement de spécialité

EXERCICE 4 (5 points)

Partie A Restitution organisée de connaissances

Puisque $a\equiv b\;(\text{mod}\;n)$ et $c\equiv d\;(\text{mod}\;n)$, il existe deux entiers relatifs $k$ et $k'$ tels que $b=a+kn$ et $d=c+k'n$.
Mais alors,

$bd=(a+kn)(c+k'n)=ac+ak'n+ckn+kk'n^2=ac+(ak'+ck+kk'n)n$

Posons $K=ak'+ck+kk'n$. $K$ est un entier relatif tel que $bd=ac+Kn$ et on a donc montré que $ac\equiv bd\;(\text{mod}\;n)$.


Partie B Inverse de 23 modulo 26

  1. $23\times(-9)-26\times(-8)=-207+208=1$. Donc le couple $(-9,-8)$ est solution de l'équation $(E)$.

  2. Posons $(x_0,y_0)=(-9,-8)$. Soient $x$ et $y$ deux entiers relatifs.
    $(x,y)$ solution de $(E)\lra23x-26y=1\lra 23x-26y=23x_0-26y_0\lra23(x-x_0)=26(y-y_0)$.

    Si $(x,y)$ est solution de $(E)$, alors l'entier $26$ divise l'entier $26(y-y_0)=23(x-x_0)$. D'autre part, la question précédente montre qu'il existe deux entiers relatifs $u$ et $v$ tels que $23u+26v=1$. Le théorème de \textsc{Bézout} permet alors d'affirmer que les entiers $23$ et $26$ sont premiers entre eux.

    Ainsi, $26$ divise $23(x-x_0)$ et $26$ est premier à $23$. D'après le théorème de \textsc{Gauss}, $26$ divise $x-x_0$. Par suite, il existe un entier relatif $k$ tel que $x-x_0=26k$ ou encore tel que $x=-9+26k$. De même, il existe un entier relatif $k'$ tel que $y=-8+23k'$.

    En résumé, si $(x,y)$ est solution de $(E)$, il existe deux entiers relatifs $k$ et $k'$ tels que $x=-9+26k$ et $y=-8+23k'$.

    Réciproquement, soient $k$ et $k'$ deux entiers relatifs puis $x=-9+26k$ et $y=-8+23k'$.

    $(x,y)$ est solution de $(E)\lra23(-9+26k)-26(-8+23k')=1\lra1+23\times26\times(k-k')=1\lra k=k'$.

    Les solutions de $(E)$ sont les couples d'entiers relatifs de la forme $(-9+26k,-8+23k)$, $k\in\mbz$.


  3. Soit $a$ un entier relatif. $23a\equiv1\;(\text{mod}\;26)$ si et seulement si il existe un entier relatif $y$ tel que $23a-26y=1$.
    D'après la question précédente, ceci impose l'existence d'un entier relatif $k$ tel que $a=-9+26k$. Ensuite,
    $0\leqslant a\leqslant25\Leftrightarrow 0\leqslant-9+26k\leqslant25\Leftrightarrow 9\leqslant26k\leqslant34\Leftrightarrow \dfrac{9}{26}\leqslant k\leqslant\dfrac{34}{26}\Leftrightarrow k=1$.

    Pour $k=1$, on obtient $a=-9+26=17$. Réciproquement, puisque $17\times23=391=1+15\times26$, l'entier $a=17$ est un entier tel que $0\leqslant a\leqslant25$ et $23a\equiv1\;(\text{mod}\;26)$.

    $a=17$.


Partie C Chiffrement de Hill

  1. Etape 1. ST correspond à $(x_1,x_2)=(18,19)$.

    Etape 2.

    • $11x_1+3x_2=11\times18+3\times19=198+57=255$. $y_1$ est alors le reste de la division euclidienne de $255$ par $26$. Comme $255=21+234=21+9\times26$ et que $0\leqslant 21\leqslant 25$, on en déduit que $y_1=21$.

    • $7x_1+4x_2=7\times18+4\times19=126+76=202$. Comme $202=20+182=20+7\times26$ et que $0\leqslant 20\leqslant 25$, on en déduit que $y_2=20$.

    Etape 3. Le couple $(21,20)$ correspond au mot \textbf{VU} et donc

    le mot \textbf{ST} se code en \textbf{VU}.


    1. Soient $x_1$, $x_2$, $y_1$ et $y_2$ quatre entiers. \begin{align*} \left\{ \begin{array}{l} y_1\equiv11x_1+3x_2\;(\text{mod}\;26)\\ y_2\equiv7x_1+4x_2\;(\text{mod}\;26) \end{array} \right.&\Rightarrow\left\{ \begin{array}{l} 4y_1+23y_2\equiv(4\times11+23\times7)x_1+(4\times3+23\times4)x_2\;(\text{mod}\;26)\\ 19y_1+11y_2\equiv(19\times11+11\times7)x_1+(19\times3+11\times4)x_2\;(\text{mod}\;26) \end{array} \right.\\ &\Rightarrow\left\{ \begin{array}{l} 4y_1+23y_2\equiv205x_1+104x_2\;(\text{mod}\;26)\\ 19y_1+11y_2\equiv286x_1+101x_2\;(\text{mod}\;26) \end{array} \right.\\ &\Rightarrow\left\{ \begin{array}{l} 4y_1+23y_2\equiv23x_1\;(\text{mod}\;26)\\ 19y_1+11y_2\equiv23x_2\;(\text{mod}\;26) \end{array} \right. \end{align*}

      car $205=23+7\times26$, $104=4\times26$, $286=11\times26$ et $101=23+3\times26$ et donc

      $205\equiv23\;(\text{mod}\;26)$, $104\equiv0\;(\text{mod}\;26)$, $286\equiv0\;(\text{mod}\;26)$ et $101\equiv23\;(\text{mod}\;26)$.

    2. On multiplie alors les deux membres de chaque congruence écrite par $17$. D'après la question 3) de la partie A, on a $23\times17\equiv1\;(\text{mod}\;26)$ et donc on obtient \begin{align*} \left\{ \begin{array}{l} 23x_1\equiv4y_1+23y_2\;(\text{mod}\;26)\\ 23x_2\equiv19y_1+11y_2\;(\text{mod}\;26) \end{array} \right.&\Rightarrow\left\{ \begin{array}{l} x_1\equiv4\times17y_1+23\times17y_2\;(\text{mod}\;26)\\ x_2\equiv19\times17y_1+11\times17y_2\;(\text{mod}\;26) \end{array} \right. \\ &\Rightarrow\left\{ \begin{array}{l} x_1\equiv68y_1+391y_2\;(\text{mod}\;26)\\ x_2\equiv323y_1+187y_2\;(\text{mod}\;26) \end{array} \right.\Rightarrow\left\{ \begin{array}{l} x_1\equiv16y_1+y_2\;(\text{mod}\;26)\\ x_2\equiv11y_1+5y_2\;(\text{mod}\;26) \end{array} \right. \end{align*}

      car $68=16+2\times26$, $391=1+15\times26$, $323=11+12\times26$ et $187=5+7\times26$ et donc

      $68\equiv16\;(\text{mod}\;26)$, $391\equiv1\;(\text{mod}\;26)$, $323\equiv11\;(\text{mod}\;26)$ et $187\equiv5\;(\text{mod}\;26)$.

    3. Réciproquement, \begin{align*} \left\{ \begin{array}{l} x_1\equiv16y_1+y_2\;(\text{mod}\;26)\\ x_2\equiv11y_1+5y_2\;(\text{mod}\;26) \end{array} \right.&\Rightarrow \left\{ \begin{array}{l} 11x_1+3x_2\equiv209y_1+26y_2\;(\text{mod}\;26)\\ 7x_1+4x_2\equiv156y_1+27y_2\;(\text{mod}\;26) \end{array} \right. \\ &\Rightarrow\left\{ \begin{array}{l} y_1\equiv11x_1+3x_2\;(\text{mod}\;26)\\ y_2\equiv7x_1+4x_2\;(\text{mod}\;26) \end{array} \right. \end{align*}

      car $209=1+8\times26$, $26=0+1\times26$, $156=0+6\times26$ et $27=1+1\times26$ et donc

      $209\equiv1\;(\text{mod}\;26)$, $26\equiv0\;(\text{mod}\;26)$, $156\equiv0\;(\text{mod}\;26)$ et $27\equiv1\;(\text{mod}\;26)$.

      En résumé,

      $\left\{ \begin{array}{l} y_1\equiv11x_1+3x_2\;(\text{mod}\;26)\\ y_2\equiv7x_1+4x_2\;(\text{mod}\;26) \end{array} \right.\Leftrightarrow \left\{ \begin{array}{l} x_1\equiv16y_1+y_2\;(\text{mod}\;26)\\ x_2\equiv11y_1+5y_2\;(\text{mod}\;26) \end{array} \right.$.


      • Le mot \textbf{YJ} correspond au couple $(y_1,y_2)=(24,9)$.

      • $16y_1+y_2=16\times24+9=393=3+15\times26$ et donc $x_1=3$.

      • $11y_1+5y_2=11\times24+5\times9=309=23+11\times26$ et donc $x_2=23$.

      Le couple $(3,23)$ correspond au mot \textbf{DX} et donc

      le mot \textbf{YJ} se décode en \textbf{DX}.