Exercices de Divisibilité et congruences, Terminale

1. Par définition du codage, $y$ est le reste de la division euclidienne de $4x+3$ par $27$. On a donc :$$y\equiv 4x+3(\mathrm{mod}27),\text{avec }0⩽y⩽26$$2. On code chaque caractère de « MATHS*EXPERTES » avec la table de l'énoncé (A a le rang $0$, ..., Z le rang $25$, * le rang $26$) :
- M : $x=12$ et $4\times 12+3=51=27+24$, donc $y=24$, soit Y ;
- A : $x=0$ et $4\times 0+3=3$, donc $y=3$, soit D ;
- T : $x=19$ et $4\times 19+3=79=2\times 27+25$, donc $y=25$, soit Z ;
- H : $x=7$ et $4\times 7+3=31=27+4$, donc $y=4$, soit E ;
- S : $x=18$ et $4\times 18+3=75=2\times 27+21$, donc $y=21$, soit V ;
- * : $x=26$ et $4\times 26+3=107=3\times 27+26$, donc $y=26$, soit * ;
- E : $x=4$ et $4\times 4+3=19$, donc $y=19$, soit T ;
- X : $x=23$ et $4\times 23+3=95=3\times 27+14$, donc $y=14$, soit O ;
- P : $x=15$ et $4\times 15+3=63=2\times 27+9$, donc $y=9$, soit J ;
- R : $x=17$ et $4\times 17+3=71=2\times 27+17$, donc $y=17$, soit R.
Les lettres E, T et S qui reviennent se codent de la même façon (E en T, T en Z, S en V).
La phrase codée est « YDZEV*TOJTRZTV ».

3. On part de $y\equiv 4x+3(\mathrm{mod}27)$, c'est-à-dire $4x\equiv y-3(\mathrm{mod}27)$.
On cherche un inverse de $4$ modulo $27$, c'est-à-dire un entier $k$ tel que $4k\equiv 1(\mathrm{mod}27)$ : comme $4\times 7=28=27+1$, l'entier $k=7$ convient.
En multipliant les deux membres par $7$, on obtient $28x\equiv 7(y-3)(\mathrm{mod}27)$. Or $28\equiv 1(\mathrm{mod}27)$, donc $x\equiv 7y-21(\mathrm{mod}27)$, et comme $-21\equiv -21+27=6(\mathrm{mod}27)$ :$$x\equiv 7y+6(\mathrm{mod}27)$$Réciproquement, si $x\equiv 7y+6(\mathrm{mod}27)$, alors $4x+3\equiv 28y+27\equiv y(\mathrm{mod}27)$ : les deux relations sont équivalentes. Ainsi $x$ est le reste de la division euclidienne de $7y+6$ par $27$.

4. On décode chaque caractère de « FB*TVZ*DC*ZFJ » à l'aide de $x\equiv 7y+6(\mathrm{mod}27)$ :
- F : $y=5$ et $7\times 5+6=41=27+14$, donc $x=14$, soit O ;
- B : $y=1$ et $7\times 1+6=13$, donc $x=13$, soit N ;
- * : $y=26$ et $7\times 26+6=188=6\times 27+26$, donc $x=26$, soit * ;
- T : $y=19$ et $7\times 19+6=139=5\times 27+4$, donc $x=4$, soit E ;
- V : $y=21$ et $7\times 21+6=153=5\times 27+18$, donc $x=18$, soit S ;
- Z : $y=25$ et $7\times 25+6=181=6\times 27+19$, donc $x=19$, soit T ;
- D : $y=3$ et $7\times 3+6=27=1\times 27+0$, donc $x=0$, soit A ;
- C : $y=2$ et $7\times 2+6=20$, donc $x=20$, soit U ;
- J : $y=9$ et $7\times 9+6=69=2\times 27+15$, donc $x=15$, soit P.
Les caractères F, * et Z qui reviennent se décodent de la même façon (F en O, * en *, Z en T).
La phrase décodée est « ON*EST*AU*TOP », c'est-à-dire « ON EST AU TOP ».
Vérification : en recodant O ($x=14$), on trouve $4\times 14+3=59=2\times 27+5$, soit F, qui est bien le premier caractère du message codé.