De nombreuses traces sur l'arithmétiques ont vu le jour dans le monde entier : des babyloniens, des phéniciens en passant par les chinois, les indiens, les Egyptiens ou les grecs.

Vers 300 avant notre ère, Euclide décrit, dans ses livres "les éléments", un algorithme du PGCD de deux nombres.

Vers le III siècle avant Jésus-Christ Diophante résout des problèmes d'arithmétique et laisse son nom à un groupe d’équations (équations diophantiennes) qui ont poussé beaucoup de mathématiciens à s'y intéresser, Bachet de Méziriac, Fermat, Bézout, Gauss ...etc.

En 1612, Bachet de Méziriac développe l'algorithme d'Euclide étendu et donne une condition nécessaire et suffisante pour que deux entiers soient premiers entre eux.

En 1766, Etienne Bézout généralise le résultat de Bachet.

En 1801, Carl Friedrich Gauss énonce un résultat fondamental en arithmétique, connu sous le nom de Théorème de Gauss.

Théorème de Bézout

Théorème de Bézout

$a$ et $b$ sont deux entiers relatifs non nuls.

$a$ et $b$ sont premiers entre eux si, et seulement si, il existe des entiers relatifs $u$ et $v$ tels que $au + bv = 1$.

Soient $a$ et $b$ deux entiers relatifs non nuls et $d=PGCD(a~;~b)$.

  1. On suppose qu'il existe deux entiers $u$ et $v$ tels que $au + bv = 1$.

    1. Montrer que $d$ divise $au + bv$.

      Code de déblocage de la correction :

    2. En déduire que $a$ et $b$ sont premiers entre eux.

      Code de déblocage de la correction :

  2. Dans la suite, on suppose que $a$ et $b$ sont premiers entre eux. ($d=1$). On va chercher à démontrer qu'il existe deux entiers $u$ et $v$ tels que $au + bv = 1$.

  3. On note $E=\{n\in \mathbb{N}^*\textrm{tel que } n=au+bv \textrm{ avec } (u~;~v)\in\mathbb{Z}^2 \}$.

    Justifier que $E$ n'est pas vide (on peut montrer que $|a| \in E$).
    On admet donc que $E$ a un plus petit élément que l'on note $D$.

    Code de déblocage de la correction :

    1. Écrire la division euclidienne de $a$ par $D$ en notant $q$ le quotient et $r$ le reste.

      Code de déblocage de la correction :

    2. Justifier qu'il existe deux entiers $U$ et $V$ tels que $r = Ua + bV$ et en déduire que si $r > 0$, alors $r \in E$.

      Code de déblocage de la correction :

    3. En déduire alors que $r = 0$ et donc que $D | a$.

      Code de déblocage de la correction :

    1. Démontrer que $D | b$.

      Code de déblocage de la correction :

    2. En déduire alors que $D = 1$.

      Code de déblocage de la correction :

    3. Conclure en énonçant la propriété démontrée par les questions 2. à 4.

      Code de déblocage de la correction :

  4. Cet exercice a permis de démontrer une équivalence. Enoncer cette équivalence.

    Code de déblocage de la correction :

Méthode pour calculer des coefficients de Bézout $u$ et $v$ pour deux entiers relatifs $a$ et $b$ premiers entre eux.

  1. On justifie l'existence d'un couple d'entiers $(u~;~v)$ tel que $a\times u + b\times v = 1$.
  2. On utilise l'algorithme d'Euclide pour déterminer tous les restes successifs jusqu'au reste égal à 1 (le dernier non nul).
  3. On remonte les égalités des divisions euclidiennes obtenues par l'algorithme d'Euclide en isolant les restes non nuls obtenus.

Voici appliquée la démarche pour déterminer deux entiers $u$ et $v$ tels que $41u + 12v = 1$.

  1. Existence:
    $41$ est un nombre premier, donc $41$ et $12$ sont premiers entre eux. D'après le théorème de Bézout, il existe donc deux entiers relatifs $u$ et $v$ tels que $41u + 12v = 1$

  2. Algorithme d'Euclide :

    • $41 = 12 \times$ $3 +$ 5

    • $12 =$ 5 $\times 2 + $ 2

    • 5 $ = $ 2$\times$ 2 + 1

  3. On remonte successivement les égalités des divisions euclidiennnes en isolant les restes et en remplaçant ceux connus :

    Première manière de voir :

    • Dans la ligne 3, on isole le reste 1 :
      1$ = $5 $- 2 \times$ 2.

    • Dans la ligne 2, on isole le reste 2 et on remplace ce reste dans l'expression déjà obtenue :
      2 $= 12 - $5$\times 2$ donc :
      1$ = $5 $- 2 \times (12 - $5 $\times 2)$, soit 1$ = $5 $- 2 \times 12 +4\times $5, d'où : 1$ = - 2 \times 12 +5\times $5.

    • Dans la ligne 1, on isole le reste 5 et on remplace ce reste dans l'expression déjà obtenue :
      5 = $41 - 12 \times 3$ donc :
      1$ = -2 \times 12 +5\times $5, soit 1$ = -2 \times 12 +5\times (41 - 12 \times 3)$, d'où : 1$ = -2 \times 12 +5\times 41 - 12 \times 15$.

      Ainsi, 1$ = 5\times 41 +(- 17) \times 12$.

    Autre manière de voir :
    En posant $a=41$ et $b=12$, on isole les restes de chaque ligne ; reste que l'on remplace dans les deux lignes suivantes où il apparaît :

    • Dans la ligne 1, on isole le reste 5 :
      5 = $a - b \times 3 = a - 3b$.

    • Dans la ligne 2, on isole le reste 2 et on remplace l'ancien reste 5 :
      2 $= b - $5 $\times 2 = b - 2\times(a-3b) = b - 2a + 6b = -2a + 7b$.

    • Dans la ligne 3, on isole le reste 1 et on remplace les deux anciens restes 5 et 2 :
      1 = 5 $- 2 \times$ 2 $= a - 3b - 2\times (-2a + 7b) = a - 3b + 4a - 14b = 5a - 17b$.

      Donc, en remplaçant $a$ et $b$ par leur valeur, on a : $5\times 41 +(-17)\times 12 = 1$.

  4. Ainsi, pour $u=5$ et $v=-17$, on a : $41u + 12v = 1$.

  1. Montrer que $25$ et $72$ sont premiers entre eux à l'aide de l'algorithme d'Euclide.

    Code de déblocage de la correction :

  2. Justifier qu'il existe un couple $(u~;~v)$ d'entiers de Bézout tel que $25u + 72v = 1$.

    Code de déblocage de la correction :

  3. En utilisant la méthode de l'exemple 1, déterminer un couple d'entiers relatifs $(u~;~v)$ tels que : $25u + 72v = 1$.

    Code de déblocage de la correction :

    Dans chacun des cas suivants, justifier l'existence d'un couple $(u~;~v)$ d'entiers vérifiant l'équation donnée puis en déterminer un.

  1. $36u + 19v = 1$.

    Code de déblocage de la correction :

  2. $99u + 56v = 1$.

    Code de déblocage de la correction :

  1. Montrer que deux entiers naturels consécutifs sont premiers entre eux.

    Code de déblocage de la correction :

  2. Montrer que deux entiers naturels impairs consécutifs sont premiers entre eux.

    Code de déblocage de la correction :

  3. Montrer que, pour tout entier naturel $n$, $(2n + 1)$ et $(3n + 2)$ sont premiers entre eux.

    Code de déblocage de la correction :

  1. Montrer que la fraction $\dfrac{9n+1}{6n+1}$ est irréductible, pour tout entier naturel $n$.

    Code de déblocage de la correction :

  2. Montrer que la fraction $\dfrac{14n+3}{5n+1}$ est irréductible, pour tout entier naturel $n$.

    Code de déblocage de la correction :

Soient $a$ un entier relatif non nul et $n$ un entier naturel supérieur ou égal à 2.

On dit que l'entier $a$ admet un inverse modulo $n$ ou encore qu'il est inversible modulo $n$ lorsqu'il existe un entier relatif $b$ tel que $ab \equiv 1~[n]$.

D'après l'exemple 1, $41 \times 5 + (-17)\times 12 = 1$, on déduit $41 \times 5 \equiv 1~[12]$.

Ainsi, $41$ est inversible modulo $12$ et un inverse de $41$ modulo $12$ est $5$.

$a$ est inversible modulo $n$ si, et seulement s'il existe $(u~;~v)\in \mathbb{Z^2}$ tel que $au+nv = 1$.

Soient $a$ un entier relatif non nul et $n$ un entier naturel supérieur ou égal à 2.

  1. Montrer que si $a$ est inversible modulo $n$ alors il existe $(u~;~v)\in \mathbb{Z^2}$ tel que $au+nv = 1$.

    Code de déblocage de la correction :

  2. Montrer que s'il existe $(u~;~v)\in \mathbb{Z^2}$ tel que $au+nv = 1$ alors $a$ est inversible modulo $n$.

    Code de déblocage de la correction :

  3. Conclure.

    Code de déblocage de la correction :

$a$ est inversible modulo $n$ si, et seulement $a$ et $n$ sont premiers entre eux.

La démonstration de cette propriété est une conséquence directe de la propriété précédente.

  1. Démontrer que $87$ est inversible modulo $31$.

    Code de déblocage de la correction :

  2. Résoudre dans $\mathbb{Z}$ l'équation $87x\equiv 15~[31]$.

    Code de déblocage de la correction :

Dans chaque cas, résoudre dans $\mathbb{Z}$ l'équation :

  1. $7x\equiv 5~[9]$

    Code de déblocage de la correction :

  2. Résoudre l'équation $70x\equiv 17~[31]$.

    Code de déblocage de la correction :

Caractérisation du PGCD

Théorème de Bézout généralisé

$a$ et $b$ sont deux entiers relatifs non nuls.

$PGCD(a~;~b) = d$ si, et seulement si $d$ divise $a$ et $b$ et s'il existe deux entiers relatifs $u$ et $v$ tels que $au + bv = d$.

  1. Soit $d=PGCD(a~;~b)$.

    1. Montrer qu'il existe deux entiers $a'$ et $b'$ tels que $a=da'$ et $b=db'$ et $PGCD(a'~;~b')=1$.

      Code de déblocage de la correction :

    2. En déduire qu'il existe deux entiers $u$ et $v$ tels que $au + bv = d$.

      Code de déblocage de la correction :

  2. On suppose que $d$ divise $a$ et $b$ et qu'il existe deux entiers relatifs $u$ et $v$ tels que $au + bv = d$. Soit $d'$ un diviseur commun à $a$ et $b$.

    1. Justifier que $d'$ divise $d$.

      Code de déblocage de la correction :

    2. En déduire que $d=PGCD(a~;~b)$.

      Code de déblocage de la correction :

  3. Conclure.

    Code de déblocage de la correction :

La condition $d$ divise $a$ et $b$ est nécessaire car $3\times 1 + 2\times 1 = 5$ mais $5$ n'est pas le PGCD de $2$ et $3$.

Corollaire du théorème de Bézout

L'équation $ax + by = c$ admet des solutions entières si, et seulement si, $c$ est un multiple du $PGCD(a~;~b)$.

  1. On suppose que le couple $(x_0~;~y_0)$ soit solution de l'équation $ax + by = c$.

    Montrer que le $PGCD$ de $a$ et $b$ est un diviseur de $c$.

    Code de déblocage de la correction :

  2. On suppose que $d = PGCD(a~;~b)$ et que $c$ est un multiple de $d$, c.à.d. qu'il existe un entier $c'$ tel que $c=dc'$.

    1. Justifier que $ax + by = c$ équivaut à l'équation $a'x + b'y = c'$ où $a'$ et $b'$ sont des entiers tels que $PGCD(a'~;~b') = 1$.

      Code de déblocage de la correction :

    2. En déduire que l'équation $ax + by = c$ a des solutions entières.

      Code de déblocage de la correction :

  3. Conclure

    Code de déblocage de la correction :

  1. L'équation $15x + 12y = 6$ a des couples d'entiers solutions car $PGCD(15~;~12) = 3$ et $3$ divise $6$.
  2. L'équation $15x + 12y = 28$ n'a pas de couples solutions entières car $PGCD(15~;~12) = 3$ et $3$ ne divise pas $28$.

    On donne $a=84$ et $b=27$

  1. Déterminer $PGCD(a~;~b)$ à l'aide de l'algorithme d'Euclide.

    Code de déblocage de la correction :

  2. Déterminer un couple $(u~;~v)$ d'entiers relatifs tels que $au + bv = PGCD(a~;~b)$

    Code de déblocage de la correction :

Théorème de Gauss

Théorème de Gauss et son corollaire

Théorème de Gauss

Soient $a$, $b$ et $c$ trois entiers relatifs non nuls.

Si $a$ divise le produit $bc$ et si $a$ et $b$ sont premiers entre eux alors $a$ divise $c$.

Autrement dit : $\begin{cases} a|bc\\ PGCD(a,b)=1 \end{cases}\rightarrow a|c$

Démonstration du théorème de Gauss.
Soient $a$, $b$ et $c$ trois entiers naturels non nuls.

  1. On suppose que $a$ divise $bc$ et que $a$ et $b$ sont premiers entre eux.

    En déduire une écriture de $bc$ en fonction de $a$.

    Code de déblocage de la correction :

  2. Justifier l'existence de deux entiers relatifs $u$ et $v$ tels que $au + bv = 1$.

    Code de déblocage de la correction :

  3. Multiplier cette égalité par $c$.

    Code de déblocage de la correction :

  4. En utilisant l'écriture de $bc$ obtenu au premier point. Factoriser par $a$ et conclure.

    Code de déblocage de la correction :

Attention la condition "$a$ et $b$ sont premiers entre eux" est essentielle dans le théorème de Gauss, en effet :

21 divise $6\times 7$ mais 21 ne divise ni 6 ni 7.

On souhaite trouver tous les couples d'entiers relatifs $(x~;~y)$ tels que $5x=7y$.

  1. On suppose qu'il existe des entiers $x$ et $y$ tels que $5x=7y$, en déduire à l'aide du théorème de Gauss que $7$ divise $x$ et qu'il existe un entier relatif $k$ tel que $y=5k$ et $x=7k$.

    Code de déblocage de la correction :

  2. Étudier la réciproque et conclure.

    Code de déblocage de la correction :

    Dans chaque cas, résoudre dans $\mathbb{Z^2}$ l'équation :

  1. $4(x-2)=5(y-3)$

    Code de déblocage de la correction :

  2. $55(x+2)=10(y-7)$

    Code de déblocage de la correction :

Corollaire du théorème de Gauss

Soient $a$, $b$ et $c$ trois entiers relatifs non nuls.

Si $a$ et $b$ divise $c$ et si $a$ et $b$ sont premiers entre eux alors $ab$ divise $c$.

Démontrer le corollaire du théorème de Gauss.

Code de déblocage de la correction :

8 et 11 divisent 2200, 8 et 11 sont premiers entre eux, donc 88 divise 2200.

Attention la condition "$a$ et $b$ sont premiers entre eux" est essentielle dans le corollaire du théorème de Gauss, voici un contre-exemple :

6 et 8 divise 24 mais $6\times 8$ ne divise pas 24.

Soit $n$ un entier naturel non nul et $N = n^3-n$. Montrer que $N$ est divisible par 6.

Code de déblocage de la correction :

Equations diophantiennes

On appelle une équation diophantienne toute équation polynomiale à coefficients entiers dont on cherche les solutions parmi les nombres entiers.

Une équation diophantienne du premier degré à deux inconnues est une équation qui peut s'écrire sous la forme $ax+by=c$, où $a$, $b$ et $c$ sont des entiers donnés.

D'après le corollaire du théorème de Bézout, une telle équation admet des solutions entières si $c$ est un multiple du $PGCD(a~;~b)$.

Une solution particulière et le théorème de Gauss permettent de trouver toutes les solutions entières de cette équation du premier degré.

Ce type d'équation doit son nom à Diophante d'Alexandrie, mathématicien de langue grec, vers le $III^e$ siècle de notre ère.

    On considère l'équation $7x - 11y = 3$, où $x$ et $y$ sont des nombres entiers relatifs.

  1. Vérifier que $(x_0~;~y_0)=(13~;~8)$ est solution de cette équation.

    Code de déblocage de la correction :

  2. Montrer que $7x - 11y = 3$ si, seulement si $7(x-13) = 11(y - 8)$.

    Code de déblocage de la correction :

  3. Résoudre l'équation $7(x-13) = 11(y - 8)$ et donner les solutions de l'équation $7x - 11y = 3$.

    Code de déblocage de la correction :

    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. 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 :

      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 :

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

    Code de déblocage de la correction :

    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 :

  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 :

    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 :

Exercices

$\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.

  3. Code de déblocage de la correction :

$\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.

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 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 ?

  4. Code de déblocage de la correction :

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

$\left\{\begin{array}{l c l} n &\equiv & 9 \quad [17]\\ n &\equiv &3 \quad [5] \end{array}\right.$
  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$

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

    4. 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 ?

  4. Code de déblocage de la correction :

$\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}$.

  4. .

    Code de déblocage de la correction :

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

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

$\textbf{Etape 1 :}$ Chaque lettre du mot est remplacée par un entier en utilisant le tableau 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 obtient un couple d'entiers $\left(x_{1}~;~x_{2}\right)$ où $x_{1}$ correspond à la première lettre du mot et $x_{2}$ correspond à la deuxième lettre du mot.

$\textbf{Etape 2 :} \left(x_{1}~;~x_{2}\right)$ est transformé en $\left(y_{1}~;~y_{2}\right)$ tel que : $\left(S_{1}\right)\:\: \left\{\begin{array}{l c l l} y_{1} &\equiv& 11x_{1} + 3x_{2} &\pmod {26}\\ y_{2} &\equiv& 7x_{1} + 4x_{2} &\pmod {26} \end{array}\right.\quad \text{avec } 0 \leqslant y_{1} \leqslant 25\:\: \text{et}\:\: 0 \leqslant y_{2} \leqslant 25.$

$\textbf{Etape 3 :} \left(y_{1}~;~y_{2}\right)$ est transformé en un mot de deux lettres en utilisant le tableau de correspondance donné dans l'étape 1.

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}$.
  3. Code de déblocage de la correction :

$\textbf{Les parties A et B sont indépendantes}.$

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

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 ?
  2. Montrer que les entiers $a$ et $b$ sont solutions du système
  3. \[\begin{cases}4a + b\equiv 14~[26] \\b \equiv 4~[26]. \end{cases}\]
  4. Déterminer tous les couples d'entiers $(a~,~b)$ ayant pu permettre le codage de ce texte.
  5. Code de déblocage de la correction :

$\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.

  3. Code de déblocage de la correction :

$\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}.\]

Code de déblocage de la correction :

$\textbf{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 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 définit un système de codage :

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.

Code de déblocage de la correction :

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é "$\star$" 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.

a b c d e f g h i j k l m n
0 1 2 3 4 5 6 7 8 9 10 11 12 13

o p q r s t u v w x y z $\star$
14 15 16 17 18 19 20 21 22 23 24 25 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.

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

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

  5. 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)$.

    Code de déblocage de la correction :

  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. Votre enseignant possède une collection de livres de mathématiques ainsi que trois bibliothèques.

      • Dans la première bibliothèque, très étroite, il peut mettre 5 livres de sa collection par rangées.
        Ainsi, seuls deux livres occupent la dernière rangée.

      • Dans la deuxième un peu plus large, il peut mettre 8 livres de sa collection par rangées.
        Ainsi, seul un livre occupe la dernière rangée.

      • Dans la dernière, bien large, il peut mettre 40 livres par rangées.

      Combien de lignes occuperont la dernière rangée si les autres rangées sont remplies intégralement ?

    Code de déblocage de la correction :

  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, sachant que le groupe était mixte avec une majorité de femmes ?

Code de déblocage de la correction :

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$.

céleste
  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$.

    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$.
    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. 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 ?

  1. 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$.
  2. 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.
  3. 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.

chaussettes

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 1er août !".

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

    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).

Avec une amie programmeuse, vous décidez de créer un petit jeu d'aventure sur smartphone.
Dans ce jeu, un personnage est généré de manière aléatoire à chaque nouvelle partie : il se voit doter d'un équipement particulier choisi dans une liste de 60 objets ou accessoires différents.
Ces ojets ou accessoires sont numérotés de 0 à 59.

Vous avez en charge de trouver des manières pour attribuer automatiquement ces objets à chaque début de partie de sorte que le joueur ne se lasse pas. Pour que le joueur se lasse moins vite, l'idée est de faire en sorte de commencer le plus longtemps possible avec un équipement différent de ceux déjà obtenus lors de démarrage précédent.

Première Idée

  1. Votre première idée est de choisir au hasard un nombre entre 0 et 59.
    Vous désirez avoir une idée du nombre moyenne de parties jouées avant que le joueur ne retombe sur un équipement déjà rencontré.
    Pour cela, vous allez utiliser le langage Python.

    1. Compléter le programme ci-dessous de sorte que la fonction choisir60(), qui ne prend pas de paramètre, renvoie une liste de 60 nombres entiers aléatoires entre 0 et 59, quitte à admettre que randint(0,59) renvoie un nombre entier aléatoire compris entre 0 et 59.

      from random import randint
      def choisir60():
          lst = ... 
      	for i in range(...):
      		...
          return ...

    2. Écrire une fonction extraire qui prend en paramètres une liste lst et un entier strictement positif n inférieur à la longueur de la liste lst et qui renvoie la liste extraite lst dont tous les éléments ont un indice compris entre 0 et $n-1$.

    3. Compléter le programme ci-dessous afin que la fonction premiere_redondance, qui prend en paramètre une liste renvoie l'indice du premier élément apparaissant une seconde fois dans la liste saisie comme argument.

      Utiliser la fonction extraire précédente.

      def premiere_redondance(lst):
          i=0
          redondant_trouve = False
          while redondant_trouve == False:
              i = ...
              if ...: # si l'élément de la liste a déjà été trouvé précédemment
                  redondant_trouve = ...
          return i
    4. Proposer un programme qui utilise les deux fonctions précédentes et qui permet d'estimer le nombre moyen de parties jouées avant que le joueur ne retombe sur un équipement déjà rencontré.

    5. Déterminer le nombre moyen de parties jouées avant que le joueur ne retombe sur un équipement déjà rencontré.

  2. Seconde Idée

  3. Votre deuxième idée est d'attribuer un objet ou accessoire à chaque nouvelle partie en parcourant la liste de leurs numéros en effectuant des sauts d'amplitude constante $c$, où $c$ est un nombre entier strictement compris entre 1 et 59 :

    • Lors de la première partie, le personnage se voit attribuer l'objet ou l'accessoire repéré par 0.

    • Pour les nouvelles parties suivantes, on obtient le numéro de l'objet ou de l'accessoire en ajoutant $c$ au numéro de l'objet obtenu lors de la nouvelle partie précédente.
      Ensuite, on calcule le reste de cette somme dans la division euclidienne par 60. Ce reste obtenu correspond alors au numéro de l'objet ou accessoire attribué au personnnage de la nouvelle partie.

  4. En choisissant la valeur $c=25$, déterminer la liste des numéros des objets successivement attribués avant de retomber sur un accessoire ou objet déjà donné.

  5. Le but désormais est d'obtenir une liste de numéro la plus longue possible sans retomber sur un numéro attribué.
    On cosidère dans la suite la liste des 60 premiers numéros obtenus par cette idée quitte à retomber sur le même numéro.

    1. Démontrer que le nombre $q$ indexé par l'entier $k$ dans la liste des numéros attribués est tel que $q\equiv kc~[60]$.

    2. Démontrer que s'il existe deux indices distincts $k$ et $k'$, compris entre 0 et 59, tels qu'en ces indices, la liste contienne le même nombre $n$ compris entre 0 et 59, alors $c$ et 60 ne sont pas premiers entre eux.

    3. Démontrer que si la liste des numéros attribués contient 60 nombres entiers tous dictincts et tous compris entre 0 et 59, alors il existe un entier naturel $m$ tel que $mc\equiv 1 ~[60]$.

    4. Conclure quant à l'ensemble des valeurs de $c$ qui permettent d'obtenir une liste de numéros attribués contenant 60 nombres entiers tous distincts et tous compris entre 0 et 59.

    5. Prendre une valeur de $c$ qui permet d'obtenir une liste de numéros attribués contenant 60 nombres entiers tous distincts et tous compris entre 0 et 59.
      Proposer un algorithme qui permet de connaître la liste des 60 nombres entiers distincts en suivant la démarche retenue dans cette seconde idée.

Code de déblocage de la correction :

Escape Game

Code pour accéder à l'escape game :

Demander le programme !

Licence Creative Commons
Les différents auteurs mettent l'ensemble du site à disposition selon les termes de la licence Creative Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International