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 :

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 :

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 :

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

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

   Code de déblocage de la correction :

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

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

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 :

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

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 :

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 :

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

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

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 livres occuperont la dernière rangée de la troisième bibliothèque si les premières 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 ?

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 simultané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^er août !".

1. Vérifier que pour une personne née le 1^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).