Cours L'incontournable du chapitre
Exercice d'application

Exercice : Arithmétique

 

Partie A

 

On considère l’équation $(E)$ suivante : $51x − 26y = 1$ où $x$ et $y$ sont des nombres entiers relatifs.

 

1) Justifier, en énonçant un théorème du cours, que cette équation admet au moins un couple solution.

 

2) A) Donner un couple solution ($x_0$ ; $y_0$) de cette équation.

B) Déterminer l’ensemble des couples solutions de cette équation.

 

 

Partie B

 

On fait correspondre à chaque lettre de l’alphabet un nombre entier comme l’indique le tableau ci-dessous :

 

A

B

C

D

E

F

G

H

I

J

0

1

2

3

4

5

6

7

8

 

K

L

M

N

O

P

Q

R

S

T

10

11

12

13

14

15

16

17

18

19

 

U

V

W

X

Y

Z

20

21

22

23

24

25

 

Afin de coder une lettre de l’alphabet, correspondant à un entier $x$ compris entre $0$ et $25$, on définit une fonction de codage $f$ par :

$f(x) = y$, où $y$ est le reste de la division euclidienne de $51x + 2$ par $26$.
La lettre de l'alphabet correspondant à l'entier $x$ est ainsi codée par la lettre correspondant à l'entier $y$.

 

1) Coder la lettre $N$.

2) En utilisant la partie $A$, déterminer l'entier $a$ tel que $0 \le a \le 25$  et  $51a \equiv 1\; [26]$.

3) Démontrer que si la lettre correspondant à un entier $x$ est codée par une lettre correspondant à un entier $y$, alors $x$ est le reste de la division euclidienne par $26$ d'une fonction de décodage $f^{-1} (y) = ay + 2$.

4) Déterminer alors la lettre qui est codée par la lettre $N$. Que constate-t-on ?

5) On applique $100$ fois de suite la fonction de codage $f$ à un nombre $x$ correspondant à une certaine lettre. Quelle lettre obtient-on ?

Partie A

 

1) On cite le théorème de Bezout : $a$ et $b$ sont premiers entre eux si et seulement si il existe un couple d’entiers relatifs ($u$; $v$) tel que : $au + bv = 1$

$51$ et $26$ sont premiers entre eux, donc d’après le théorème de Bezout, il existe un couple ($u$; $v$) d’entiers relatifs tels que $51u − 27v = 1$

 

2) A) $51(-1)-26(-2) = -51 + 52 = 1$

Donc $(-1;-2)$ est solution de cette équation.

 

B) Soit $(x;y)$ une solution générale de l'équation. En soustrayant termes à termes les égalités suivantes :

$51x - 26y = 1\quad$   et

$51(-1) - 26(-2) = 1$

On obtient = $51(x+1) - 26 (y+2) = 0 \Leftrightarrow 51 (x+1) = 26(y+2) \quad(E')$

$26$ divise $51 (x+1)$, or $pgcd \ (51 ; 26) = 1$ donc, d'après le théorème de Gauss, $26$ divise $(x+1)$.

Ainsi, il existe un entier $k$ vérifiant : $x+1 = 26k, k \in \mathbb{Z}$

En remplaçant $x$ par $26k-1$ dans $(E')$, on a :

$51x − 26y = 1 \iff 51(26k-1) − 26y = 1$

$\iff 51\times26k-26y=52$

$\iff 26(51k-y)=26\times2$

$\iff y=51k-2$

 

L'ensemble des couples solutions de l'équation est de la forme :

 $S = \{( -1 + 26 k;-2 + 51k)\quad ,k \in \mathbb{Z}\} $

 

 

Partie B

 

1) $N \rightarrow 13$ donc $f(13) = 51(13) + 2 = 665 $

Or, $665 \equiv 15\; [26]$  donc le reste est : $y=15$

La lettre $N$ est donc codée par $15$.

 

2) $51a \equiv 1 [26] \Leftrightarrow 51a \equiv 1 + 26k, k \in Z \Leftrightarrow 51a - 26k \equiv 1, k \in\mathbb{Z}$

Donc, d'après la partie $A$, $a$ est de la forme : $a = -1 + 26k$.

Comme $0 \le a \le 25$, seul $k = 1$ correspond, donc $a=-1 + 26 = 25$

 

3) On a : $51x + 2 \equiv y\; [26] \Leftrightarrow 51x \equiv y -2\; [26]$

En multipliant par $a$, on obtient : $51a \ x \equiv ay - 2a\; [26]$

D'après la question précédente $51a \equiv 1\; [26]$ donc $x \equiv ay - 2a\; [26]$

Comme $a = 25$, on a : $-2a = -50 = 26(-2) +2$ donc $-2a \equiv 2\; [26]$

Conclusion : $x \equiv ay + 2 [26] \Leftrightarrow f^{-1} (y) = ay +2$

 

4) $N \rightarrow 13$  Or, $f^{-1} (13) = 25(13) + 2 = 327$

$327 \equiv 15\; [26]$ et $x= 15$ correspondant à  $P$

On constate que la lettre $N$ se code et se décode en $P$.

 

5) D'après la question précédente, comme $N$ se code et se décode en $P$, on peut raisonnablement penser que si on compose deux fois la fonction $f$ de codage, on obtient la fonction identité.

Vérifions-le :

$f[f(x)] \equiv f(51x + 2)\; [26]$

$f[f(x)] \equiv 51 (51x+2) +2\; [26]$

$f[f(x)] \equiv 2601x + 51 \times 2 + 2\; [26]$

On a : $2601 = 26 \times 100 + 1 \equiv 1\; [26]$ donc 

$f[f(x)] \equiv x + 104\; [26]$

De plus : $104 = 26 \times 4 \equiv 0\; [26]$ donc

$f[f(x)] \equiv x\; [26]$

 

Si on applique deux fois de suite la fonction $f$ à une lettre, on obtient la même lettre.

Si l'on réitère $50$ fois cette opération soit $100$ fois la fonction $f$, on obtient la même lettre de départ.