On considère la fonction Python suivante dont les paramètres $a$ et $b$ sont des entiers naturels.

def CBezout(a,b):
    r,u,v,x,y=1,1,0,0,1
    while r>0:
        r=a%b
        q=a//b
        a,b=b,r
        s=u-x*q
        u=x
        x=s
        t=v-q*y
        v=y
        y=t
    return a,u,v

1. 1. En exécutant pas à pas cette fonction dont les arguments sont $a=23$ et $b=7$, compléter le tableau suivant :

      $\quad$	Etape 0	Etape 1	Etape 2	Etape 3	...
      Les valeurs de r	$1$	$\quad$	$\quad$	$\quad$	$\quad$
      Les valeurs de a	$23$	$\quad$	$\quad$	$\quad$	$\quad$
      Les valeurs de u	$1$	$\quad$	$\quad$	$\quad$	$\quad$
      Les valeurs de v	$0$	$\quad$	$\quad$	$\quad$	$\quad$

      Code de déblocage de la correction :

      En exécutant pas à pas cette fonction pour $a=23$ et $b=7$, on obtient le tableau suivant :

      $\quad$	Etape 0	Etape 1	Etape 2	Etape 3
      Les valeurs de r	$1$	$2$	$1$	$0$
      Les valeurs de a	$23$	$7$	$2$	$1$
      Les valeurs de a	$7$	$2$	$1$	$0$
      Les valeurs de u	$1$	$0$	$1$	$-3$
      Les valeurs de v	$0$	$1$	$-3$	$10$

      Pour ces arguments, la fonction renvoie le triplet $(1~;-3~;~10)$.

   2. Expliquer le rôle de cette fonction. Que représentent les valeurs qu'elle renvoie ?

      Code de déblocage de la correction :

      Cette fonction renvoie un triplet $(d~;~u~;~v)$ où $d=PGCD(a~;~b)$ et $u$, $v$ sont des entiers tels que $au+bv=d$.

2. Saisir et tester cette fonction avec différents couples $(a~;~b)$.

   Code de déblocage de la correction :

   Par exemple :

   >>> CBezout(235,605)
   (5, -18, 7)
   >>> 

   Ainsi, $PGCD(235~;~605)=5$ et $235\times (-18)+605\times 7 = 5$

On se propose de résoudre dans $\mathbb{N^2}$ l'équation $(E)~:~8x+15y=146$

1. $(x~;~y)$ désigne un couple solution de $(E)$. Montrer que les nombres entiers naturels $x$ et $y$ vérifient respectivement $x\leq 18$ et $y\leq 9$

   Code de déblocage de la correction :

   Soit $(x~;~y)$ un couple solution de $8x+15y=146$. Or, $y\in \mathbb{N}$, donc $15y \geq 0$, comme $8x+15y=146$ alors $8x \leq 146$, soit $x\leq \dfrac{146}{8}$. D'où, $x\leq 18,25$ donc $x\geq 18$.

   De même on a $x\in \mathbb{N}$ et $8x \geq 0$, donc $15y\leq 146$, soit $y\leq \dfrac{146}{15}$. D'où, $y\leq 9,733...$ donc $y\leq 9$.

2. Voici un algorithme incomplet permettant d'obtenir les couples $(x~;~;y)$ d'entiers naturels solution de $(E)$.

   Pour x allant de 0 à ...
   	Pour y allant de 0 à ...
   		Si ... alors
   			afficher x et y
   		Fin Si
   	Fin Pour
   Fin Pour

   1. Recopier et compléter l'algorithme.

      Code de déblocage de la correction :

      Pour x allant de 0 à 18
      	Pour y allant de 0 à 9
      		Si 8x+15y=146 alors
      			afficher x et y
      		Fin Si
      	Fin Pour
      Fin Pour

   2. Coder cet algorithme en langage Python. Saisir le programme et l'exécuter afin d'obtenir tous les couples solutions de $(E)$.

      Code de déblocage de la correction :

      
      for x in range(19):
          for y in range(10):
              if 8*x+15*y==146:
                  print("({} ; {})".format(x,y))

      En exécutant le programme, on obtient un seul couple solution de $(E)$.

      
      >>> 
      (7 ; 6)
      >>> 

      Ainsi, l'équation $(E)$ a une seule solution dans $\mathbb{N^2}$ qui est $(7~;~6)$.

$\textbf{Les parties A et B peuvent être traitées de façon indépendante}$

$\textbf{Partie A}$

On considère la fonction suivante de paramètres deux entiers naturels non nuls $a$ et $b$ :

def mystere(a,b):
	c=a%b
	while c!= 0 :
		a=b
		b=c
		c=a%b
	return b

1. Faire fonctionner cette fonction avec $a = 26$ et $b = 9$ en indiquant les valeurs de $a$, $b$ et $c$ à chaque étape.

2. Cette fonction renvoie le PGCD des entiers naturels non nuls $a$ et $b$. La modifier pour qu'elle indique si deux entiers naturels non nuls $a$ et $b$ sont premiers entre eux ou non.

Code de déblocage de la correction :

1. Faire fonctionner cette fonction avec $a = 26$ et $b = 9$ en indiquant les valeurs de $a$, $b$ et $c$ à chaque étape.

   $\quad$	$\quad$	$\quad$	$\quad$
   Valeur de a	$26$	$9$	$8$
   Valeur de b	$9$	$8$	$1$
   Valeur de c	$8$	$1$	$0$
   Affichage			$1$

2. Cet algorithme donne en sortie le PGCD des entiers naturels non nuls $a$ et $b$. Le modifier pour qu'il indique si deux entiers naturels non nuls $a$ et $b$ sont premiers entre eux ou non.

   def mystere(a,b):
   	c=a%b
   	while c!= 0 :
   		a=b
   		b=c
   		c=a%b
   	if b==1:
   		print("Les nombres entrés sont premiers entre eux.")
   	else :
   		print("Les nombres entrés ne sont pas premiers entre eux.")

$\textbf{Partie B}$

A chaque lettre de l'alphabet on associe grâce au tableau ci-dessous un nombre entier compris entre 0 et 25.

On définit un procédé de codage de la façon suivante :

$\textbf{Etape 1 :}$ on choisit deux entiers naturels $p$ et $q$ compris entre $0$ et $25$.

$\textbf{Etape 2 :}$ à la lettre que l'on veut coder, on associe l'entier $x$ correspondant dans le tableau ci-dessus.

$\textbf{Etape 3 :}$ on calcule l'entier $x'$ défini par les relations \[x' \equiv px + q\quad [26]\quad \text{et}\quad 0 \leqslant x' \leqslant 25.\]

$\textbf{Etape 4 :}$ à l'entier $x'$, on associe la lettre correspondante dans le tableau.

1. Dans cette question, on choisit $p = 9$ et $q = 2$.

   1. Démontrer que la lettre V est codée par la lettre J.

   2. Citer le théorème qui permet d'affirmer l'existence de deux entiers relatifs $u$ et $v$ tels que $9u + 26v = 1$. Donner sans justifier un couple $(u,~v)$ qui convient.

   3. Démontrer que $x' \equiv 9x + 2\quad [26]$ équivaut à $x \equiv 3x' + 20\quad [26]$.

   4. Décoder la lettre R.

2. Dans cette question, on choisit $q = 2$ et $p$ est inconnu. On sait que J est codé par D. Déterminer la valeur de $p$ ( on admettra que $p$ est unique).

3. Dans cette question, on choisit $p = 13$ et $q = 2$. Coder les lettres B et D. Que peut-on dire de ce codage ?

Code de déblocage de la correction :

1. Dans cette question, on choisit $p = 9$ et $q = 2$.

   1. Démontrer que la lettre V est codée par la lettre J.

      Dans le tableau V correspond à 21, or $9 \times 21 + 2 = 189 + 2 = 191$ et $191 = 26 \times 7 + 9$ ; donc $x' \equiv 9\quad [26]$. Dans le tableau 9 correspond à la lettre J.

   2. Citer le théorème qui permet d'affirmer l'existence de deux entiers relatifs $u$ et $v$ tels que $9u + 26v = 1$. Donner sans justifier un couple $(u,~v)$ qui convient.

      9 et 26 étant premiers entre eux, le théorème de Bezout permet d'affirmer l'existence de deux entiers relatifs $u$ et $v$ tels que $9u + 26v = 1$. Le couple $(3~;~- 1)$ est un couple simple solution de cette équation.

   3. Démontrer que $x' \equiv 9x + 2\quad [26]$ équivaut à $x \equiv 3x' + 20\quad [26]$.

      On a $x' \equiv 9x + 2\quad [26] \iff $ il existe $k \in \mathbb{Z},\:\: x' = 26k + 9x + 2 \iff $ $3x' = 26k' + 27x + 6\iff 3x' = 26k' + 26x + x + 6\iff 3x' = 26r'' + x + 6 \iff x = 26(- r'') + 3x' - 6 \iff x = 26(- r'') + 3x' + 20$, soit $x \equiv 3x' + 20\quad [26]$

   4. Décoder la lettre R.

      R correspond à $x' = 17$, donc $3x' + 20 = 51 + 20 = 71$ et $71 = 26 \times 2 + 19$, soit $71 \equiv 19 \quad [26]$. On a donc $x = 19$ qui correspond à la lettre T.

2. Dans cette question, on choisit $q = 2$ et $p$ est inconnu. On sait que J est codé par D. Déterminer la valeur de $p$ (on admettra que $p$ est unique).

   J correspond à $x = 9$ et D correspond à $x' = 3$. de plus $q = 2$ ; on a donc :

   $3 = 9p + 2 \quad [26] \iff 9p \equiv 1 \quad [26]$ ou encore $27p \equiv 3 \quad [26]$, mais on sait que $27 \equiv 1 \quad [26]$ ; il en résulte que $p \equiv 3 \quad [26]$ et comme $p$ est compris entre 0 et 25, on a donc $p = 3$.

3. Dans cette question, on choisit $p = 13$ et $q = 2$. Coder les lettres B et D. Que peut-on dire de ce codage ?

   B correspond à $x = 1$, d'où $x' = 13x + 2 \equiv 15 \quad [26]$ et 15 correspond à la lettre P.

   D correspond à $x = 3$, d'où $x' = 13x + 2 \equiv 41 \quad [26]$ et $41 \equiv 15 \quad [26]$ et 15 correspond à la lettre P.

   Conclusion : deux lettres différentes sont codées par la màªme lettre. Ce codage n'est pas bon puisque le décryptage donnera plusieurs solutions.

On se propose de déterminer l'ensemble $\mathcal{S}$ des entiers relatifs $n$ vérifiant le système :

1. Recherche d'un élément de $\mathcal{S}$.

   On désigne par $(u~;~v)$ un couple d'entiers relatifs tel que $17u + 5v = 1$.

   1. Justifier l'existence d'un tel couple $(u~;~v)$.

   2. On pose $n_{0} = 3 \times 17u + 9 \times 5v$

   Démontrer que $n_{0}$ appartient à $\mathcal{S}$.

   3. Donner un exemple d'entier $n_{0}$ appartenant à $\mathcal{S}$.

2. Caractérisation des éléments de $\mathcal{S}$.

   1. Soit $n$ un entier relatif appartenant à $\mathcal{S}$.

      Démontrer que $n - n_{0} \equiv 0\quad [85]$.

   2. En déduire qu'un entier relatif $n$ appartient à $\mathcal{S}$ si et seulement si il peut s'écrire sous la forme $n = 43 + 85k$ où $k$ est un entier relatif.

3. Application

   Zoé sait qu'elle a entre 300 et 400 jetons.

   Si elle fait des tas de 17 jetons, il lui en reste 9.

   Si elle fait des tas de 5 jetons, il lui en reste 3.

   Combien a-t-elle de jetons ?

Code de déblocage de la correction :

1. Recherche d'un élément de $\mathcal{S}$.

   On désigne par $(u~;~v)$ un couple d'entiers relatifs tel que $17u + 5v = 1$.

   1. 17 et 5 sont premiers entre eux, donc, d'après le théorème de Bézout, il existe $u$ et $v$ entiers relatifs tels que $17u+5v=1$.

   2. On pose $n_{0} = 3 \times 17u + 9 \times 5v$. Démontrer que $n_{0}$ appartient à $\mathcal{S}$.

      Soit $(u~;~v)$ un couple solution, donc $17u+5v=1$. On en déduit que $17u\equiv 1~[5]$ et $5v\equiv 1~[17]$.

      Alors $n_{0}=3 \times 17u + 9 \times 5v\equiv 9\times 5v~[17]\equiv 9\times 1~[17]\equiv 9~[17]$.

      De même : $n_{0}=3 \times 17u + 9 \times 5v\equiv 3\times 17u~[5]\equiv 3\times 1~[5]\equiv 3~[5]$.

      Par conséquent, $n_{0}\in\mathcal{S}$.

   3. Donner un exemple d'entier $n_{0}$ appartenant à $\mathcal{S}$.

      Appliquons l'algorithme d'Euclide :

      $17=3\times 5$+2 et $5=2\times 2+1$, d'où $1=5-2\times 2$

      $1 = 5-(17-5\times 3)\times 2=17\times (-2)+5\times 7$.

      On peut prendre $(u~;~v) = (-2~;~7)$.

      On obtient alors $n_{0} = 213$ (ce n'est évidemment pas la seule valeur !)

2. Caractérisation des éléments de $\mathcal{S}$.

   1. Soit $n$ un entier relatif appartenant à $\mathcal{S}$. Démontrer que $n - n_{0} \equiv 0\quad [85]$.

      $n\equiv 9~[17]$ et $n_{0}\equiv 9~[17]$ donc $n-n_{0}\equiv 0~[17]$.

      De même, $n\equiv 3~[5]$ et $n_{0}\equiv 3~[5]$ donc $n-n_{0}\equiv 0~[5]$.

      Or $5~|~n-n_{0}$, $17~|~n-n_{0}$, 17 et 5 sont premiers entre eux, d'après le corollaire de Gauss, $5\times 17~|~n-n_{0}$, ainsi $n-n_{0}\equiv 0~[85]$ (car $5\times 17=85$).

   2. En déduire qu'un entier relatif $n$ appartient à $\mathcal{S}$ si et seulement s'il peut s'écrire sous la forme $n = 43 + 85k$ où $k$ est un entier relatif.

      On en déduit que, si $n\in\mathcal{S}$, $n\equiv n_{0}~[85]$ donc $n\equiv 213~[85]$.

      Or $213 = 170 + 43=2\times 85+43 \equiv 43~[85]$ donc $213\equiv 43~[85]$.

      Par conséquent : $n\in\mathcal{S}\iff n \equiv 43~[85]$ donc $n=43+85k$, $k\in\mathbb{Z}$.

      Réciproquement, si $n\equiv 43+85k$, $k \in \mathbb{Z}$ , il est clair que $n\equiv 9~[17]$ et $n\equiv 3~[5]$.

3. Application :

   Combien a-t-elle de jetons ?

   Soit $n$ le nombre de jetons. On a : $n\equiv 9~[17]$ et $n\equiv 3~[5]$.

   D'après ce qui précède, on a : $n=43+85k$.

   On sait que $300 \leqslant n\leqslant 400$, donc $300\leqslant 43+85k\leqslant 400$. On en déduit que $k=4$ et que Zoé a $383$ jetons.

$\textbf{Partie A : Inverse de 23 modulo 26}$

On considère l'équation : $(E) \::\quad 23x - 26y = 1,$ où $x$ et $y$ désignent deux entiers relatifs.

1. Vérifier que le couple $(-9~;~-8)$ est solution de l'équation $(E)$.

2. Résoudre alors l'équation $(E)$.

3. En déduire un entier $a$ tel que $0 \leqslant a \leqslant 25$ et $23a \equiv 1 \pmod {26}$.

.

Code de déblocage de la correction :

$\textbf{Partie A : Inverse de 23 modulo 26}$

1. Vérifier que le couple $(-9~;~-8)$ est solution de l'équation $(E)$.

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

2. Résoudre alors l'équation $(E)$.

   $\left\{\begin{array}{l c l} 23x - 26y &=& 1\\ 23\times (- 9) - 26 \times (- 8) &=& 1 \end{array}\right.\Longrightarrow $ (par différence membre à membre)

   $23(x + 9) - 26(y + 8) = 0 \iff 23(x + 9) = 26(y + 8) \quad (1)$.

   Donc 23 divise $26(y + 8)$ et comme il est premier avec 26; il divise $y + 8$ (théorème de Gauss) : il existe donc un entier $k$ tel que $y + 8 = 23k \iff y = - 8 + 23k$.

   En remplaçant dans (1) $y + 8$ par $23k$, on obtient :

   $23(x + 9) = 26 \times 23k \iff x + 9 = 26 \iff x = - 9 + 26k$.

   Réciproquement les couples $(- 9 + 26k~;~- 8 + 23k)$ vérifient $(E)$ car $23(- 9 + 26k) - 26(- 8 + 23k) = - 207 + 23 \times 26k + 208 - 26 \times 23k = 1$.

   Les couples solutions de $(E)$ sont donc de la forme : $(-9 + 26k~;~- 8 + 23k), \: k \in \mathbb{Z}$.

3. En déduire un entier $a$ tel que $0 \leqslant a \leqslant 25$ et $23a \equiv 1 \pmod {26}$.

   Il faut trouver un (ou des) couple(s) de premier terme $a$ tel que $0 \leqslant a \leqslant 25$, donc vérifiant :

   $0 \leqslant - 9 + 26k \leqslant 25 \iff 9 \leqslant 26k \leqslant 34$. La solution $k = 1$ est évidente ce qui donne $a = - 9 + 26 = 17$.

   Donc comme $26b \equiv 0 \pmod {26}$, on a $23 \times 17 \equiv 1 \pmod {26}$.

$\textbf{Partie B : Chiffrement de Hill}$

On veut coder un mot de deux lettres selon la procédure suivante :

Exemple : \[\underbrace{\text{TE}}_{{\text{mot en clair}}}\stackrel{\text{étape} 1}{\Longrightarrow} (19,4) \stackrel{\text{étape}\: 2}{\Longrightarrow} (13,19) \stackrel{\text{étape}\: 3}{\Longrightarrow} \underbrace{\text{NT}}_{{\text{mot codé}}}\]

1. Coder le mot ST.
2. On veut maintenant déterminer la procédure de décodage:
   1. Montrer que tout couple $\left(x_{1}~;~x_{2}\right)$ vérifiant les équations du système $\left(S_{1}\right)$, vérifie les équations du système : \[\left(S_{2}\right)\:\: \left\{\begin{array}{l c l l} 23x_{1} &\equiv& \phantom{1}4y_{1} + 23y_{2} &\pmod {26}\\ 23x_{2}&\equiv& 19y_{1} + 11y_{2} &\pmod {26} \end{array}\right.\]
   2. A l'aide de la partie B, montrer que tout couple $\left(x_{1}~;~x_{2}\right)$ vérifiant les équations du système $\left(S_{2}\right)$, vérifie les équations du système \[\left(S_{3}\right)\:\: \left\{\begin{array}{l c l l} x_{1}&\equiv& 16y_{1} + y_{2} &\pmod {26}\\ x_{2}&\equiv& 11y_{1} + 5y_{2} &\pmod {26} \end{array}\right.\]
   3. Montrer que tout couple $\left(x_{1}~;~x_{2}\right)$ vérifiant les équations du système $\left(S_{3}\right)$, vérifie les équations du système $\left(S_{1}\right)$
   4. Décoder le mot $\textbf{YJ}$.

Code de déblocage de la correction :

$\textbf{Partie B : Chiffrement de Hill}$

1. Coder le mot ST.

   $\underbrace{\text{ST}}_{{\text{mot en clair}}}\stackrel{\text{étape} 1}{\Longrightarrow} (18,~19) \stackrel{\text{étape}\: 2}{\Longrightarrow} (21,~20) \stackrel{\text{étape}\: 3}{\Longrightarrow} \underbrace{\text{VU}}_{{\text{mot codé}}}$

2. On veut maintenant déterminer la procédure de décodage:
   1. Montrer que tout couple $\left(x_{1}~;~x_{2}\right)$ vérifiant les équations du système

      $\left(S_{1}\right)$, vérifie les équations du système : \[\left(S_{2}\right)\:\: \left\{\begin{array}{l c l l} 23x_{1} &\equiv& 4y_{1} + 23y_{2} &\pmod {26}\\ 23x_{2}&\equiv& 19y_{1} + 11y_{2} &\pmod {26} \end{array}\right.\] ~ $\left(S_{1}\right)\:\: \left\{\begin{array}{l c r l} y_{1} &\equiv& 11x_{1} + 3x_{2} &\pmod {26}\\ y_{2} &\equiv& 7x_{1} + 4x_{2} &\pmod {26} \end{array}\right. \Longrightarrow$

      $ \left\{\begin{array}{r c r l} - 44x_{1} - 12x_{2}&=& - 4y_{1}&\pmod {26}\\ 21x_{1} + 12x_{2}&=&3y_{2}&\pmod {26} \end{array}\right.\Rightarrow$ (par somme)

      $- 23x_{1}= - 4y_{1} + 3y_{2}\quad \pmod {26}$.

      De même :

      $\left(S_{1}\right)\:\: \left\{\begin{array}{l c r l} y_{1} &\equiv& 11x_{1} + 3x_{2} &\pmod {26}\\ y_{2} &\equiv& 7x_{1} + 4x_{2} &\pmod {26} \end{array}\right. \Longrightarrow$ $ \left\{\begin{array}{r c r l} - 77x_{1} - 21x_{2}&=&- 7y_{1}&\pmod {26}\\ 77x_{1} + 44x_{2}&=&11y_{2}&\pmod {26} \end{array}\right.$

      $\Longrightarrow$ (par somme) $23x_{2} = - 7y_{1} + 11y_{2} \pmod{26}$ ou encore puisque $- 7 \equiv 19 \pmod{26}$ : $23x_{2} = 19y_{1} + 11y_{2} \pmod{26}$.

      Donc, tout couple $\left(x_{1}~;~x_{2}\right)$ vérifiant les équations du système $\left(S_{1}\right)$, vérifie les équations du système : \[\left(S_{2}\right)\:\: \left\{\begin{array}{l c r l} 23x_{1} &\equiv& 4y_{1} + 23y_{2} &\pmod {26}\\ 23x_{2}&\equiv& 19y_{1} + 11y_{2} &\pmod {26} \end{array}\right.\]

   2. A l'aide de la partie B, montrer que tout couple $\left(x_{1}~;~x_{2}\right)$ vérifiant les équations du système $\left(S_{2}\right)$, vérifie les équations du système : \[\left(S_{3}\right)\:\: \left\{\begin{array}{l c l l} x_{1}&\equiv& 16y_{1} + y_{2} &\pmod {26}\\ x_{2}&\equiv& 11y_{1} + 5y_{2} &\pmod {26} \end{array}\right.\]

      On a vu à la partie B que $23 \times 17 \equiv 1 \:\pmod{26}$ (23 a pour inverse 17 modulo 26), donc en multipliant chaque membre du système $\left(S_{2}\right)$ par 17, on obtient :

      $\left(S_{2}\right)\:\: \iff \left\{\begin{array}{l c l l} 23x_{1}\times 17 &\equiv& 4y_{1}\times 17 + 23y_{2}\times 17 &\pmod {26}\\ 23x_{2}\times 17&\equiv& 19y_{1}\times 17 + 11y_{2}\times 17 &\pmod {26} \end{array}\right. \Longrightarrow $

      $\left\{\begin{array}{l c l l} x_{1}&\equiv& 68y_{1} + 391y_{2}&\pmod {26}\\ x_{2}&\equiv &323y_{1} + 187y_{2}&\pmod {26} \end{array}\right.$

      Or $68 \equiv 16\:\pmod{26}, \quad 391 \equiv 1 \:\pmod{26}, \quad 323 \equiv 11 \:\pmod{26},$

      $187 \equiv 5 \:\pmod{26}$, donc finalement tout couple $\left(x_{1}~;~x_{2}\right)$ vérifiant les équations du système $\left(S_{2}\right)$, vérifie les équations du système :

      \[\left(S_{3}\right)\:\: \left\{\begin{array}{l c l l} x_{1}&\equiv& 16y_{1} + y_{2} &\pmod {26}\\ x_{2}&\equiv& 11y_{1} + 5y_{2} &\pmod {26} \end{array}\right.\]
   3. Montrer que tout couple $\left(x_{1}~;~x_{2}\right)$ vérifiant les équations du système $\left(S_{3}\right)$, vérifie les équations du système $\left(S_{1}\right)$.

      On calcule $11x_{1} + 3x_{2} = 11\left(16y_{1} + y_{2}\right) + 3\left(11y_{1} + 5y_{2}\right) = $ $176y_{1} + 11y_{2} + 33y_{1} + 15y_{2} = 209y_{1} + 26y_{2}$.

      Or $209 \equiv 1 \:\pmod{26}$ et $26 \equiv 0 \: \pmod{26}$, donc $11x_{1} + 3x_{2} \equiv 1y_{1} + 0y_{2} \:\pmod{26}$.

      De même $7x_{1} + 4x_{2} = 7\left(16y_{1} + y_{2}\right) + 4\left(11y_{1} + 5y_{2}\right) = 112y_{1} + 7y_{2} + 44y_{1} + 20y_{2} = 156y_{1} + 27y_{2}$.

      Or $146 \equiv 0 \: \pmod{26}$ et $27 \equiv 1 \:\pmod{26}$, donc $7x_{1} + 4x_{2} \equiv 0y_{1} + 1y_{2} \: \pmod{26}$.

      Conclusion : tout couple $\left(x_{1}~;~x_{2}\right)$ vérifiant les équations du système $\left(S_{3}\right)$, vérifie les équations du système $\left(S_{1}\right)$.

      Finalement les systèmes $\left(S_{1}\right)$ et $\left(S_{3}\right)$ sont équivalents.

   4. Décoder le mot $\textbf{YJ}$.

      Pour YJ le couple $\left(y_{1}~;~y_{2}\right) = (24~;~9)$. En appliquant les équations de $\left(S_{3}\right)$ on obtient :

      $\left\{\begin{array}{l c l l} x_{1}&\equiv&16 \times 24 + 9&\pmod{26}\\ x_{2}&\equiv&11 \times 24 + 5 \times 9&\pmod{26} \end{array}\right. \iff \left\{\begin{array}{l c l l} x_{1}&\equiv&393&\pmod{26}\\ x_{2}&\equiv&309&\pmod{26} \end{array}\right.$

      Or $393 = 26 \times 15 + 3$, donc $393 \equiv 3 \: \pmod{26}$ ;

      $309 = 26 \times 11 + 23$, donc $269 \equiv 23 \: \pmod{26}$.

      On a donc $\left(x_{1}~;~x_{2}\right) = (3~;~23)$ et en utilisant le tableau le mot décodé est donc $\textbf{DX}$.

Une personne a mis au point le procédé de cryptage suivant :

• A chaque lettre de l'alphabet, on associe un entier $n$ comme indiqué ci-dessous :

A	B	C	D	E	F	G	H	I	J	K	L	M
0	1	2	3	4	5	6	7	8	9	10	11	12




N	O	P	Q	R	S	T	U	V	W	X	Y	Z
13	14	15	16	17	18	19	20	21	22	23	24	25

• On choisit deux entiers $a$ et $b$ compris entre 0 et 25.
• Tout nombre entier $n$ compris entre 0 et 25 est codé par le reste de la division euclidienne de $an+ b$ par 26.

Le tableau suivant donne les fréquences $f$ en pourcentage des lettres utilisées dans un texte écrit en français.

Un texte écrit en français et suffisamment long a été codé selon ce procédé. L'analyse fréquentielle du texte codé a montré qu'il contient $15,9\:\%$ de O et $9,4\:\%$ de E.

On souhaite déterminer les nombres a et b qui ont permis le codage.

1. Quelles lettres ont été codées par les lettres O et E ?
2. Montrer que les entiers $a$ et $b$ sont solutions du système
\[\begin{cases}4a + b\equiv 14~[26] \\b \equiv 4~[26]. \end{cases}\]
3. Déterminer tous les couples d'entiers $(a~,~b)$ ayant pu permettre le codage de ce texte.

Code de déblocage de la correction :

Une personne a mis au point le procédé de cryptage suivant :

• A chaque lettre de l'alphabet, on associe un entier $n$ comme indiqué ci-dessous :

A	B	C	D	E	F	G	H	I	J	K	L	M
0	1	2	3	4	5	6	7	8	9	10	11	12




N	O	P	Q	R	S	T	U	V	W	X	Y	Z
13	14	15	16	17	18	19	20	21	22	23	24	25

• On choisit deux entiers $a$ et $b$ compris entre 0 et 25.
• Tout nombre entier $n$ compris entre 0 et 25 est codé par le reste de la division euclidienne de $an+ b$ par 26.

Le tableau suivant donne les fréquences $f$ en pourcentage des lettres utilisées dans un texte écrit en français.

Lettre	A	B	C	D	E	F	G	H	I	J	K	L	M
Fréquence	9,42	1,02	2,64	3,38	15,87	0,94	1,04	0,77	8,41	0,89	0,00	5,33	3,23




Lettre	N	O	P	Q	R	S	T	U	V	W	X	Y	Z
Fréquence	7,14	5,13	2,86	1,06	6,46	7,90	7,26	6,24	2,15	0,00	0,30	0,24	0,32

$\textbf{Partie A }$

Un texte écrit en français et suffisamment long a été codé selon ce procédé. L'analyse fréquentielle du texte codé a montré qu'il contient $15,9\:\%$ de O et $9,4\:\%$ de E.

On souhaite déterminer les nombres $a$ et $b$ qui ont permis le codage.

1. Quelles lettres ont été codées par les lettres O et E ?

   Dans le tableau des fréquences, la fréquence la plus proche de $15,9\%$ est $15,87\%$ associée à la lettre E

   De même la fréquence la plus proche de $9,4\,\%$ est $9,42\,\%$ associée à la lettre A

   Finalement E a été codé par O et A a été codé par E.

2. Montrer que les entiers $a$ et $b$ sont solutions du système : \[\begin{cases}4a + b\equiv 14~[26] \\b \equiv 4~[26]. \end{cases}\]

   l'entier associé à E est $4$, celui associé à A est $0$ et celui associé à O est $14$

   Comme E (associé à $n=4$) est codé par O associé à $14$, donc, le reste de la division euclidienne de $4a+b$ par $26$ est $14$, ainsi, $4a+b \equiv 14 [26]$.

   De même, A (associé à $n=0$) est codé par E associé à $4$, donc, le reste de la division euclidienne de $0a+b$ par $26$ est $4$, ainsi, $b \equiv 4 [26]$.

   Finalement on a bien $\begin{cases}4a + b\equiv 14~[26] \\b \equiv 4~[26]. \end{cases}$

3. Déterminer tous les couples d'entiers $(a~,~b)$ ayant pu permettre le codage de ce texte.

   Le système précédent nous donne $b = 4$ car $0 \leqslant b \leqslant 25$

   On a donc $4a + b\equiv 14~[26] \equiv 4a \equiv 10 [26]$ alors il existe un entier naturel $k$ tel que $4a=26k+10$

   $4a = 26k+10$, donc $2a = 13k+5$. $k$ est nécessairement impair, puisque $0\leq a\leq 25$, donc $0\leq k\leq 3$

   Pour $k=1$ on obtient $a=9$ et pour $k=3$ on obtient $a=22$

   Finalement les couples d'entiers $(a~,~b)$ qui ont permis le codage sont d'entiers $(9~,~4)$ et d'entiers $(22~,~4)$

$\textbf{Partie B }$

1. On choisit $a = 22$ et $b = 4$.

   1. Coder les lettres K et X.

   2. Ce codage est-il envisageable ?

2. On choisit $a = 9$ et $b = 4$.

   1. Montrer que pour tous entiers naturels $n$ et $m$, on a : \[m \equiv 9 n + 4~[26]\iff n\equiv 3 m + 14~[26]$\]

   2. Décoder le mot AQ.

Code de déblocage de la correction :

1. On choisit $a = 22$ et $b = 4$.
   1. Coder les lettres K et X.

      K est associé à $n=10$ et $10a+b=224\equiv 16 [26]$

      X est associé à $n=23$ et $23a+b=510\equiv 16 [26]$

      donc K et X ont été codé par la même lettre Q

   2. Ce codage est-il envisageable ?

      Deux lettres différentes étant codées par la même lettre, le codage est inenvisageable.

2. On choisit $a = 9$ et $b = 4$.
   1. Montrer que pour tous entiers naturels $n$ et $m$, on a : $m \equiv 9 n + 4~[26]\iff n\equiv 3 m + 14~[26] $

      $m \equiv 9 n + 4~[26] \Longrightarrow 3m \equiv 27n+12~ [26]$

      $\hphantom{m \equiv 9 n + 4~[26]} \Longrightarrow 3m \equiv n+12+26n ~[26]$

      $\hphantom{m \equiv 9 n + 4~[26]} \Longrightarrow 3m \equiv n+12 ~[26]$

      $\hphantom{m \equiv 9 n + 4~[26]} \Longrightarrow n\equiv 3m-12~[26]$

      $\hphantom{m \equiv 9 n + 4~[26]} \Longrightarrow n\equiv 3m+14~[26]$

      Réciproquement :

      $n\equiv 3m+14~[26] \Longrightarrow 9n \equiv 27m+126 ~[26]$

      $\hphantom{n\equiv 3m+14~[26]} \Longrightarrow 9n \equiv m+22+26(m+4)~ [26]$

      $\hphantom{n\equiv 3m+14~[26]} \Longrightarrow 9n \equiv m+22~ [26]$

      $\hphantom{n\equiv 3m+14~[26]} \Longrightarrow m\equiv 9n-22~[26]$

      $\hphantom{n\equiv 3m+14~[26]} \Longrightarrow m\equiv 9n+4~[26]$

      On a donc bien $m \equiv 9 n + 4~[26]\iff n\equiv 3 m + 14~[26]$

   2. Décoder le mot AQ.

      A est associé à $m=0$ il code la lettre associée à l'entier $n$ tel que et $n\equiv 3m+14~[26]$ on a donc $n = 14$ associé à O

      Q est associé à $m=16$ il code la lettre associée à l'entier $n$ tel que et $n\equiv 3m+14~[26]$ on a donc $n = 10$ associé à K

      le mot AQ est le codage de OK.

$\textbf{Partie A}$

On considère l'équation (E) : $15x - 26k = m$ où $x$ et $k$ désignent des nombres entiers relatifs et $m$ est un paramètre entier non nul.

1. Justifier, en énonçant un théorème, qu'il existe un couple d'entiers relatifs $(u~;~v)$ tel que $15u - 26v = 1$. Trouver un tel couple.

2. En déduire une solution particulière $\left(x_0~;~k_0\right)$ de l'équation (E).

3. Montrer que $(x~;~k)$ est solution de l'équation (E) si et seulement si $15\left(x - x_0\right) - 26\left(k - k_0\right) = 0$.

4. Montrer que les solutions de l'équation (E) sont exactement les couples $(x~;~k)$ d'entiers relatifs tels que : \[\left\{\begin{array}{l c l} x&=&26q + 7m \\ k&=&15q +4m \end{array}\right.\:\text{où}\: q \in \mathbb{Z}.\]

$\textbf{Partie B}$

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

On définit un système de codage :

• à chaque lettre de l'alphabet, on associe l'entier $x$ correspondant,

• on associe ensuite à $x$ l'entier $y$ qui est le reste de la division euclidienne de $15x + 7$ par $26$,

• on associe à $y$ la lettre correspondante.

Ainsi, par cette méthode, la lettre E est associée à 4, 4 est transformé en 15 et 15 correspond à la lettre P et donc la lettre E est codée par la lettre P.

1. Coder le mot $\textbf{MATHS}$.

2. Soit $x$ le nombre associé à une lettre de l'alphabet à l'aide du tableau initial et $y$ le reste de la division euclidienne de $15x + 7$ par $26$.

   1. Montrer alors qu'il existe un entier relatif $k$ tel que $15x - 26k = y -7$.

   2. En déduire que $x \equiv 7y + 3 \quad [26]$.

   3. En déduire une description du système de décodage associé au système de codage considéré.

3. Expliquer pourquoi la lettre W dans un message codé sera décodée par la lettre B. Décoder le mot $\textbf{WHL}$.

4. Montrer que, par ce système de codage, deux lettres différentes sont codées par deux lettres différentes.

On note $E$ l'ensemble des vingt-sept nombres entiers compris entre $0$ et $26$.

On note $A$ l'ensemble dont les éléments sont les vingt-six lettres de l'alphabet et un séparateur entre deux mots, noté \og $\star$ \fg{} considéré comme un caractère.

Pour coder les éléments de $A$, on procède de la façon suivante :

$\bullet~~$Premièrement : On associe à chacune des lettres de l'alphabet, rangées par ordre alphabétique, un nombre entier naturel compris entre 0 et 25, rangés par ordre croissant. On a donc $a \to 0,\: b \to 1, \ldots z \to 25$.

On associe au séparateur "$\star$" le nombre 26.

On dit que $a$ a pour rang $0, b$ a pour rang 1, ... , $z$ a pour rang $25$ et le séparateur " $\star$ " a pour rang $26$.

$\bullet~~$ Deuxièmement : à chaque élément $x$ de $E$, l'application $g$ associe le reste de la division euclidienne de $4x + 3$ par $27$.

On remarquera que pour tout $x$ de $E,\: g(x)$ appartient à $E$.

$\bullet~~$ Troisièmement : Le caractère initial est alors remplacé par le caractère de rang $g(x)$.

Exemple :

$s \to 18, \quad g(18) = 21$ et $21 \to v$. Donc la lettre $s$ est remplacée lors du codage par la lettre $v$.

1. Trouver tous les entiers $x$ de $E$ tels que $g(x) = x$ c'est-à -dire invariants par $g$.

   En déduire les caractères invariants dans ce codage.

2. Démontrer que, pour tout entier naturel $x$ appartenant à $E$ et tout entier naturel $y$ appartenant à $E$, si $y \equiv 4x + 3$ modulo 27 alors $x \equiv 7y + 6$ modulo 27.

En déduire que deux caractères distincts sont codés par deux caractères distincts.

3. Proposer une méthode de décodage.

4. Décoder le mot " $vfv$ ".

1. On considère l'équation $(E) : 8x + 5y = 1$ , où $(x~;~y)$ est un couple de nombres entiers relatifs.
1. Donner une solution particulière de l'équation $(E)$.
2. Résoudre l'équation $(E)$.
2. Soit $N$ un entier naturel tel qu'il existe un couple $(a~;~b)$ de nombres entiers vérifiant : $\left\{ \begin{array}{l} N = 8a + 1\\ N = 5b + 2 \end{array} \right.$
1. Montrer que le couple $(a~;~b)$ est solution de $(E)$.
2. Quel est le reste, dans la division de $N$ par $40$.
3. Résoudre l'équation $8x + 5y = 100$, où $(x~;~y)$ est un couple d'entiers relatifs.
4. Un groupe composé d'hommes et de femmes a dépensé $100 €$ dans une auberge. Les hommes ont dépensé $8 €$ et les femmes $5 €$ chacune. Combien pouvait-il y avoir d'hommes et de femmes dans le groupe.

Un astronome a observé au jour $j_0$ le corps céleste A. Il apparaît périodiquement tous les 105 jours. Six jours plus tard $(J_0 + 6)$, il observe le corps $B$, dont la période d'apparition est de 81 jours. On appelle $J_1$ le jour de la prochaine apparition simultannée des deux objets aux yeux de l'astronome. Le but de cet exercice est de déterminer la date de ce jour $J_1$.

1. Soient $u$ et $v$ le nombre de périodes effectuées respectivement par $A$ et $B$ entre $J_0$ et $J_1$.

   Montrer que le couple $(u~;~v)$ est solution de l'équation $(E1) : 35x - 27y = 2$.

2. 1. Déterminer un couple d'entiers relatifs $(x_0~;~y_0)$ une solution particulière de l'équation $35x - 27y = 1$.
   2. En déduire une solution particulière $(u_0~;~v_0)$ de $(E1)$.
   3. Déterminer toutes les solutions de l'équation $(E1)$.
   4. Déterminer la solution $(u~;~v)$ permettant de déterminer de déterminer $J_1$. Combien de jours s'écouleront entre $J_0$ et $J_1$.
3. 1. Le jour $J_0$ était le samedi 16 décembre 2011, quelle est la date exacte du jour $J_1$ ? (L'année 2012 était bissextile).
   2. Si l'astronome manque ce futur rendez-vous, combien de jours devra-t-il attendre jusqu'à la prochaine conjonction des deux astres ?

Chloé joue avec des jetons. Si elle fait des tas de 7 jetons, il lui reste 5. Si elle fait des tas de 5 jetons il lui en reste 3. L'objectif de cet exercice est de déterminer le nombre de jetons. Soit $n$ le nombre de jetons.

1. 1. Montrer que $n$ vérifie le système $(1) \left\{ \begin{array}{l} n \equiv 5 [7]\\ n \equiv 3 [5]\end{array} \right.$

   2. En utilisant la calculatrice ou un tableur déterminer le plus petit entier $n_0$ répondant à la question.

      Quel est le nombre suivant répondant à la question ?

      Quelle conjecture faire sur tous les nombres répondant à la question ?

2. On désigne par $S$ l'ensemble des solutions du système $(1)$. On désigne par $(u~;~v)$ un couple d'entiers tels que $7u + 5v = 1$.
   1. Justifier l'existence d'un tel couple.
   2. On pose $n = 3\times 7u + 5\times 5v$. En utilisant les congruences, démontrer que $n_2$ appartient à $S$.
   3. Donner un exemple d'entier $n$ appartenant à $S$.
3. Caractérisation des éléments de $S$.
   1. Soit $n$ un entier relatif appartenant à $S$. Démontrer que $n - n_2 \equiv [35]$.
   2. En déduire qu'un entier relatif $n$ appartient à $s$ si et seulement si il peut s'écrire sous la forme $n = 33 + 35k$ où $k$ est un entier relatif.
4. Sachant que Chloé a entre 150 et 200 jetons, combien en a-t-elle ?

Elias sait qu'il a entre 60 et 100 paires de chaussettes. Elias est maniaque et aime bien qu'il y ait autant de paire de chaussettes dans chaque tiroir.

Qu'il ait 3 ou 5 tiroirs, il peut ranger autant de paire de chaussettes dans chaque tiroir, mais s'il a 4 tiroirs, alors il lui reste 3 paires non rangées.

Elias se demande combien il a de paires de chaussettes.

1. Montrer que le nombre de chaussettes est un multiple de 15.
2. Justifier que le nombre de paires de chaussettes est impair.
3. Conclure.

Dans cet exercice, on appelle numéro du jour de naissance le rang de ce jour dans le mois et numéro du mois de naissance, le rang du mois dans l'année.

Par exemple, pour une personne née le 14 mai, le numéro du jour de naissance est 14 et le numéro du mois de naissance est 5.

$\textbf{Partie A}$

Lors d'une représentation, un magicien demande aux spectateurs d'effectuer le programme de calcul (A) suivant :

"Prenez le numéro de votre jour de naissance et multipliez-le par 12. Prenez le numéro de votre mois de naissance et multipliez-le par 37. Ajoutez les deux nombres obtenus. Je pourrai alors vous donner la date de votre anniversaire".

Un spectateur annonce $308$ et en quelques secondes, le magicien déclare : "Votre anniversaire tombe le 1\up{er} août !".

1. Vérifier que pour une personne née le 1\up{er} août, le programme de calcul (A) donne effectivement le nombre $308$.

2. 1. Pour un spectateur donné, on note $j$ le numéro de son jour de naissance, $m$ celui de son mois de naissance et $z$ le résultat obtenu en appliquant le programme de calcul (A).

      Exprimer $z$ en fonction de $j$ et de $m$ et démontrer que $z$ et $m$ sont congrus modulo 12.

   2. Retrouver alors la date de l'anniversaire d'un spectateur ayant obtenu le nombre $474$ en appliquant le programme de calcul (A).

$\textbf{Partie B}$

Lors d'une autre représentation, le magicien décide de changer son programme de calcul. Pour un spectateur dont le numéro du jour de naissance est $j$ et le numéro du mois de naissance est $m$, le magicien demande de calculer le nombre $z$ défini par $z = 12j + 31m$.

Dans les questions suivantes, on étudie différentes méthodes permettant de retrouver la date d'anniversaire du spectateur.

1. Première méthode :

   On considère l'algorithme suivant :

   Pour m allant de 1 à  12
   	Pour j allant de 1 à  31
   		z ← 12j + 31m
   		afficher z
   	Fin Pour
   Fin Pour

   Modifier cet algorithme afin qu'il affiche toutes les valeurs de $j$ et de $m$ telles que $12j + 31m = 503$.

2. Deuxième méthode :

   1. Démontrer que $7m$ et $z$ ont le màªme reste dans la division euclidienne par 12.

   2. Pour $m$ variant de 1 à 12, donner le reste de la division euclidienne de $7m$ par 12.

   3. En déduire la date de l'anniversaire d'un spectateur ayant obtenu le nombre $503$ avec le programme de calcul (B).

3. Troisième méthode :

   1. Démontrer que le couple $(-2~;~17)$ est solution de l'équation $12x + 31y = 503$.

   2. En déduire que si un couple d'entiers relatifs $(x~;~y)$ est solution de l'équation $12x + 31y = 503$, alors $12(x + 2) = 31 (17 - y)$.

   3. Déterminer l'ensemble de tous les couples d'entiers relatifs $(x~;~y)$, solutions de l'équation $12x + 31y = 503$.

   4. Démontrer qu'il existe un unique couple d'entiers relatifs $(x~;~y)$ tel que $1 \leqslant y \leqslant 12$.

      En déduire la date d'anniversaire d'un spectateur ayant obtenu le nombre $503$ avec le programme de calcul (B).