Exercices transversaux

Les exercices transversaux sont des exercices qui mélangent les notions de plusieurs chapitres.
Cette banque d’exercices peut être utilisée indépendamment de la progression suivie en classe : vous pouvez piocher dedans dans l’ordre que vous le souhaitez en fonction de ce que vous voulez travailler.
Chaque exercice est accompagné de la liste des chapitres concernés pour vous permettre de mieux les retrouver.
Ces exercices sont, par nature, plus complexes et permettent alors de valider la compréhension des notions et les raisonnements associés.

1

② Nombres complexes : point de vue géométrique
⑥ Calcul matriciel

Soient $n$ un entier naturel supérieur ou égal à $2$ et $\omega$ le nombre complexe $\omega ={\mathrm{e}}^{\frac{2\mathrm{i}\pi }{n}}$.

1. Justifier que, pour tout entier $k$ compris entre $0$ et $n-1$ on a $\overline{{\omega }^k}=\frac{1}{{\omega }^k}$.


2. Soit $\text{A}$ la matrice carrée d’ordre $n$ définie par : La matrice $\overline{\mathrm{A}}$ est obtenue en conjuguant chacun des coefficients de la matrice $\text{A}$.
Soit $\mathrm{B}=\mathrm{A}\overline{\mathrm{A}}$dont on note $b_{i,j}$ les coefficients.
a. Montrer que, pour tous entiers $i$ et $j$ compris entre $1$ et $n$, le coefficient $b_{i,j}$ vérifie $b_{i,j}=\sum _{k=1}^n{\left({\omega }^{i-j}\right)}^{k-1}$.




b. En déduire que $\mathrm{B}=n{\mathrm{I}}_n$.


3. En déduire que la matrice $\text{A}$ est inversible et déterminer ${\mathrm{A}}^{-1}$.

2

③ Divisibilité dans $\mathbb{Z}$   ⑥ Calcul matriciel

Soient $\text{A}$ et $\text{B}$ deux matrices carrées d’ordre 2 à coefficients réels.
On note $\mathrm{A}=\left(\begin{array}{ll}a& b\\ c& d\end{array}\right)$ et $\mathrm{B}=\left(\begin{array}{ll}e& f\\ g& h\end{array}\right)$.

1. a. Montrer que $\det (\mathrm{A}\mathrm{B})=\det (\mathrm{A})\det (\mathrm{B})$.


b. Montrer que si $\text{A}$ est inversible, alors $ad-bc\ne 0$ et ${\mathrm{A}}^{-1}=\frac{1}{ad-bc}\left(\begin{array}{cc}d& -b\\ -c& a\end{array}\right)$.


2. On suppose maintenant que $\text{A}$ est une matrice à coefficients entiers.
a. Justifier que $\det (\mathrm{A})$ est un nombre entier.


b. On souhaite que $\text{A}$ soit inversible et que ${\mathrm{A}}^{-1}$ ait des coefficients entiers.
Montrer à l’aide de la question 1. a. que si ces deux conditions sont vérifiées, alors $\det (\mathrm{A})=\det \left({\mathrm{A}}^{-1}\right)=\pm 1$.


c. Montrer à l’aide de la question 1. b. que la réciproque est également vraie, c’est‑à‑dire que si $\text{A}$ est une matrice à coefficients entiers vérifiant $\det (\mathrm{A})=\det \left({\mathrm{A}}^{-1}\right)=\pm 1$, alors la matrice $\text{A}$ est inversible et ${\mathrm{A}}^{-1}$ est à coefficients entiers.

3

① Nombres complexes : point de vue algébrique
⑥ Calcul matriciel

Soit $\text{A}$ une matrice carrée d’ordre 2 dont les coefficients sont des nombres complexes.
La matrice $\overline{\mathrm{A}}$ est obtenue en conjuguant chacun des coefficients de la matrice $\text{A}$.
Montrer que $\overline{\det (\mathrm{A})}=\det (\overline{\mathrm{A}})$.

4

① Nombres complexes : point de vue algébrique
③ Divisibilité dans $\mathbb{Z}$   ⑥ Calcul matriciel

Soient la matrice $\mathrm{A}=\left(\begin{array}{cc}0& -1\\ 1& 0\end{array}\right)$ et la matrice $\mathrm{D}=\left(\begin{array}{cc}\mathrm{i}& 0\\ 0& -\mathrm{i}\end{array}\right)$.

Partie A : Diagonalisation de la matrice $\mathbf{A}$
1. Soit $\text{P}$ la matrice à coefficients complexes $\left(\begin{array}{cc}1& 1\\ -\mathrm{i}& \mathrm{i}\end{array}\right)$.
Calculer $\mathrm{P}\times \left(\begin{array}{cc}1& \mathrm{i}\\ 1& -\mathrm{i}\end{array}\right)$ et en déduire l’expression de ${\mathrm{P}}^{-1}$.


2. Montrer que $\mathrm{A}={\mathrm{P}\mathrm{D}\mathrm{P}}^{-1}$.


Partie B : Détermination de ${\mathbf{A}}^{\mathbf{n}}$
On considère dans cette partie un entier naturel $n$.

1. Montrer par récurrence que pour tout $n\in \mathbb{N}$ :

2. Montrer par récurrence que pour tout $n\in \mathbb{N}$ :

3. a. On suppose dans cette question seulement que $n\equiv 0[4]$.
Montrer alors que ${\mathrm{D}}^n=\left(\begin{array}{ll}1& 0\\ 0& 1\end{array}\right)$.


b. Déterminer de la même manière une expression de ${\mathrm{D}}^n$ lorsque $n\equiv 1[4]$, $n\equiv 2[4]$ et $n\equiv 3[4]$.


c. Déterminer alors une expression de ${\mathrm{A}}^n$ dans chacun de ces quatre cas.


4. Déterminer la matrice ${\mathrm{A}}^{2019}$.

5

① Nombres complexes : point de vue algébrique
⑦ Suites et matrices

On considère deux suites de nombres complexes $(z_n)$ et $(z_n^{\prime })$ définies par $z_0=1$ , $z_0^{\prime }=\mathrm{i}$ et, pour tout entier $n\in \mathbb{N}$ :
1. Calculer $z_1$ et $z_1^{\prime }$.


2. Justifier que ce système s’écrit sous la forme matricielle ${\mathrm{Z}}_{n+1}=\mathrm{A}\times {\mathrm{Z}}_n$, où ${\mathrm{Z}}_{n+1}$, ${\mathrm{Z}}_n$ et $\text{A}$ sont trois matrices dont on explicitera les coefficients.


3. Montrer par récurrence que pour tout $n\in \mathbb{N}$ :

4. On cherche dans cette partie à déterminer les coefficients de la matrice ${\mathrm{A}}^n$.
a. Soit la matrice $\mathrm{P}=\left(\begin{array}{ll}1& 2\\ 3& 4\end{array}\right)$.
Justifier que $\text{P}$ est inversible puis déterminer ${\mathrm{P}}^{-1}$.


b. Montrer que $\mathrm{A}={\mathrm{P}\mathrm{D}\mathrm{P}}^{-1}$ où $\mathrm{D}=\left(\begin{array}{cc}2\mathrm{i}& 0\\ 0& 3\end{array}\right)$.


c. En utilisant un raisonnement par récurrence, montrer que, pour tout $n\in \mathbb{N}$, ${\mathrm{A}}^n={\mathrm{P}\mathrm{D}}^n{\mathrm{P}}^{-1}$.


d. Déterminer, pour tout $n\in \mathbb{N}$, les coefficients de la matrice ${\mathrm{D}}^n$ puis en déduire ceux de la matrice ${\mathrm{A}}^n$.


e. Exprimer, pour tout $n\in \mathbb{N}$, $z_n$ et $z_n^{\prime }$ en fonction de $n$.

6

③ Divisibilité dans $\mathbb{Z}$   ⑥ Calcul matriciel

On considère un graphe à dix sommets correspondant aux entiers de $1$ à $10$.
Pour deux sommets $a$ et $b$, il existe une arête allant de $a$ vers $b$ si $a$ divise $b$.

1. Ce graphe peut‑il être complet ? Justifier.


2. Représenter ce graphe.

7

① Nombres complexes : point de vue algébrique
③ Divisibilité dans $\mathbb{Z}$

On cherche dans cet exercice à résoudre dans $\mathbb{C}$ l’équation $(\mathrm{E}):4z^3-8z^2-27z-20=0$.

Partie A : Recherche d’une solution « évidente »
On cherche dans cette partie à déterminer une solution rationnelle de l’équation.

1. Montrer que $0$ n’est pas une solution de l’équation.


2. Justifier que s’il existe deux entiers relatifs non nuls $p$ et $q$ premiers entre eux tels que $z=\frac{p}{q}$ soit une solution de l’équation, alors $p|20$ et $q|4$.


3. En déduire les valeurs possibles d’une solution rationnelle de l’équation $(\mathrm{E})$.


4. Déterminer une solution de l’équation $(\mathrm{E})$.


Partie B : Résolution de l’équation

1. À l’aide de la solution déterminée à la question 4. de la partie A, déterminer une factorisation de

2. Déterminer alors l’ensemble des solutions de l’équation $(\mathrm{E})$.

8

① Nombres complexes : point de vue algébrique
⑥ Calcul matriciel

Soient $a$ et $b$ deux nombres réels. Tout nombre complexe $z=a+\mathrm{i}b$ peut s’écrire de manière unique sous la forme matricielle suivante : $\mathrm{A}=\left(\begin{array}{cc}a& -b\\ b& a\end{array}\right)$.

1. Soient $c$ et $d$ deux nombres réels et $z^{\prime }$ le nombre complexe défini par $z^{\prime }=c+\mathrm{i}d$.
Écrire la matrice correspondant au nombre complexe $z^{\prime }$ puis vérifier que l’addition et la mutiplication matricielles sont naturellement compatibles avec celles définies sur $\mathbb{C}$.


2. Écrire la matrice $\text{B}$ correspondant au nombre complexe $\overline{z^{\prime }}$.


3. Calculer le produit $\text{AB}$. Quel résultat retrouve‑t‑on ?

9

② Nombres complexes : point de vue géométrique
⑥ Calcul matriciel

On considère la définition des nombres complexes écrits sous forme matricielle décrite dans l’exercice précédent.

1. Soit $\theta \in \mathbb{R}$. Écrire la matrice associée au nombre complexe ${\mathrm{e}}^{\mathrm{i}\theta }$.


2. La matrice obtenue correspond à celle d’une transformation géométrique du plan muni d’un repère orthonormé direct $(\mathrm{O};\overrightarrow{i},\overrightarrow{j})$. Laquelle ?


3. Conjecturer alors, pour tout entier relatif $n$, une expression de la matrice associée au nombre $({\mathrm{e}}^{\mathrm{i}\theta }{)}^n$.
Démontrer cette conjecture.


4. Retrouver alors la formule de Moivre.

10

② Nombres complexes : point de vue géométrique
③ Divisibilité dans $\mathbb{Z}$

On considère le plan complexe muni d’un repère orthonormé $(\mathrm{O};\overrightarrow{u},\overrightarrow{v})$ et on définit, pour tout $k\in \mathbb{N}$, le point ${\mathrm{M}}_k$ d’affixe $z_k={\mathrm{e}}^{\mathrm{i}\frac{k\pi }{3}}$?

1. Calculer l’affixe de ${\mathrm{M}}_0$ et de ${\mathrm{M}}_6$.


2. Pour tout entier $k\in \{0;\dots ;5\}$, placer ${\mathrm{M}}_k$ dans le plan.

3. Compléter la congruence $2020\equiv \dots [6]$.


4. En déduire, sous forme algébrique, l’affixe de ${\mathrm{M}}_{2020}$.

11

① Nombres complexes : point de vue algébrique
⑥ Calcul matriciel

Soient $a$ et $b$ deux nombres réels et on note $z$ et $z^{\prime }$ deux nombres complexes vérifiant : On cherche à déterminer à quelle(s) condition(s) les nombres $z$ et $z^{\prime }$ sont égaux.

1. Justifier que $z$ et $z^{\prime }$ sont égaux si, et seulement si, $a$ et $b$ sont solutions du système $\{\begin{array}{rl}3a-2b& =18\\ -a-4b& =8\end{array}$.


2. Écrire ce système sous la forme $\mathrm{A}\mathrm{X}=\mathrm{B}$, où $\mathrm{A}$, $\mathrm{X}$ et $\mathrm{B}$ sont trois matrices qu’on déterminera.


3. Résoudre ce système et répondre au problème posé en explicitant $z$ et $z^{\prime }$.

12

① Divisibilité dans $\mathbb{Z}$  ⑥ Calcul matriciel

Inverse d’une matrice modulo 5.

Soient $\text{A}$ et $\text{B}$ deux matrices dont les coefficients sont donnés modulo $5$.
On donne $\mathrm{A}=\left(\begin{array}{cc}4& 1\\ -4& 1\end{array}\right)$ et $\mathrm{B}=\left(\begin{array}{cc}1& -1\\ 4& 4\end{array}\right)$.

1. Montrer que $\mathrm{A}\times \mathrm{B}=\left(\begin{array}{ll}8& 0\\ 0& 8\end{array}\right)=\left(\begin{array}{ll}3& 0\\ 0& 3\end{array}\right)$.


2. Déterminer un inverse de $3$ modulo $5$.


3. En déduire que $\text{A}$ est inversible et que ${\mathrm{A}}^{-1}=\left(\begin{array}{cc}2& -2\\ 3& 3\end{array}\right)$.

Remarque

On trouvera une généralisation de ce résultat dans l’exercice suivant.

13

④ $\mathbf{P}\mathbf{G}\mathbf{C}\mathbf{D}$ et applications  ⑥ Calcul matriciel

Inverse d’une matrice modulo $\mathbf{n}$

Soit $n$ un entier naturel supérieur ou égal à $2$ et soient $a$, $b$, $c$ et $d$ quatre entiers donnés modulo $n$.
Soient $\text{A}$ la matrice $\left(\begin{array}{ll}a& b\\ c& d\end{array}\right)$ et$\text{ B}$ la matrice $\left(\begin{array}{cc}d& -b\\ -c& a\end{array}\right)$.
On note $\det (\mathrm{A})$ la quantité $\det (\mathrm{A})=ad-bc$.

1. Montrer que $\mathrm{A}\times \mathrm{B}=\det (\mathrm{A})\times \left(\begin{array}{ll}1& 0\\ 0& 1\end{array}\right)$.


2. En déduire que si $\det (\mathrm{A})$ est inversible modulo $n$ d’inverse $\det (\mathrm{A}{)}^{-1}$, alors $\text{A}$ est inversible.
Déterminer une écriture de ${\mathrm{A}}^{-1}$.


3. On suppose maintenant que $\det (\mathrm{A})$ n’est pas inversible modulo $n$. Montrer, en utilisant un raisonnement par l’absurde, que $\text{A}$ ne peut pas être inversible.
On pourra admettre le résultat suivant : « Pour toutes matrices $\text{A}$ et $\text{B}$, $\det (\mathrm{A}\mathrm{B})=\det (\mathrm{A})\det (\mathrm{B})$. »


4. À quelle condition sur le couple $(\det (\mathrm{A});n)$ la matrice $\text{A}$ est‑elle inversible ?


5. Déterminer un inverse modulo $8$ de la matrice $\left(\begin{array}{ll}2& 1\\ 1& 3\end{array}\right)$.


6. Expliquer pourquoi la matrice $\left(\begin{array}{ll}1& 2\\ 1& 4\end{array}\right)$ n’est pas inversible modulo $8$.

14

③ Divisibilité dans $\mathbb{Z}$  ④ $\mathbf{P}\mathbf{G}\mathbf{C}\mathbf{D}$ et applications  ⑥ Calcul matriciel

D’après bac S, Métropole, juin 2019

Dans cet exercice, on étudie l’ensemble $\text{S}$ des matrices qui s’écrivent sous la forme $\mathrm{A}=\left(\begin{array}{ll}a& b\\ c& d\end{array}\right)$ où $a$, $b$, $c$ et $d$ appartiennent à l’ensemble $\mathbb{Z}$ et vérifient : $ad-bc=1$.
On note $\text{I}$ la matrice identité d’ordre $2$ : $\mathrm{I}=\left(\begin{array}{ll}1& 0\\ 0& 1\end{array}\right)$.

Partie A
1. Vérifier que la matrice $\mathrm{A}=\left(\begin{array}{cc}6& 5\\ -5& -4\end{array}\right)$ appartient à l’ensemble $\text{S}$.


2. Montrer qu’il existe exactement quatre matrices de la forme $\mathrm{A}=\left(\begin{array}{ll}a& 2\\ 3& d\end{array}\right)$ appartenant à l’ensemble $\text{S}$ puis les expliciter.


3. a. Résoudre dans $\mathbb{Z}$ l’équation $(\mathrm{E}):5x-2y=1$.
On pourra remarquer que le couple $(1;2)$ est une solution particulière de cette équation.


b. En déduire qu’il existe une infinité de matrices de la forme $\mathrm{A}=\left(\begin{array}{ll}a& b\\ 2& 5\end{array}\right)$ qui appartiennent à l’ensemble $\text{S}$.
Décrire ces matrices.


Partie B
Dans cette partie, on note $\mathrm{A}=\left(\begin{array}{ll}a& b\\ c& d\end{array}\right)$ une matrice appartenant à l’ensemble $\text{S}$. On rappelle que $a$, $b$, $c$ et $d$ sont des entiers relatifs tels que $ad-bc=1$.

1. Justifier que les entiers $a$ et $b$ sont premiers entre eux.


2. Soit $\text{B}$ la matrice $\left(\begin{array}{cc}d& -b\\ -c& a\end{array}\right)$.
a. Calculer le produit $\text{AB}$. On admet que $\mathrm{A}\mathrm{B}=\mathrm{B}\mathrm{A}$.


b. En déduire que la matrice $\text{A}$ est inversible et donner sa matrice inverse ${\mathrm{A}}^{-1}$.


c. Montrer que ${\mathrm{A}}^{-1}$ appartient à l’ensemble $\text{S}$.


3. Soient $x$ et $y$ deux entiers relatifs. On note $x^{\prime }$ et $y^{\prime }$ les entiers relatifs tels que $\left(\begin{array}{l}{x}^{\prime }\\ y^{\prime }\end{array}\right)=\mathrm{A}\left(\begin{array}{l}x\\ y\end{array}\right)$.
a. Montrer que $x=d{x}^{\prime }-b{y}^{\prime }$.


On admet de même que $y=a{y}^{\prime }-c{x}^{\prime }$.

b. On note $\text{D}$ le $\text{PGCD}$ de $x$ et $y$ et on note ${\mathrm{D}}^{\prime }$ le $\text{PGCD}$ de $x^{\prime }$ et $y^{\prime }$. Montrer que $\mathrm{D}={\mathrm{D}}^{\prime }$.


4. On considère les suites d’entiers naturels $(x_n)$ et $(y_n)$ définies par $x_0=2019$, $y_0=673$ et, pour tout entier naturel $n$, $\{\begin{array}{rl}{x}_{n+1}& =2x_n+3y_n\\ y_{n+1}& =x_n+2y_n\end{array}$.
En utilisant la question précédente, déterminer, pour tout entier naturel $n$, le $\text{PGCD}$ des entiers $x_n$ et $y_n$.

15

① Nombres complexes : point de vue algébrique   ③ Divisibilité dans $\mathbb{Z}$

Étude des sommes de deux carrés par les entiers de Gauss

Partie A : Définition des entiers de Gauss
Soient $a$ et $b$ deux nombres entiers relatifs.
On appelle entier de Gauss tout nombre complexe $z$ s’écrivant sous la forme $z=a+\mathrm{i}b$.
On note $\mathbb{Z}[\mathrm{i}]$ l’ensemble des entiers de Gauss.

1. Le nombre $\frac{100}{3+4\mathrm{i}}$ est‑il un entier de Gauss ?


2. Justifier que si $z\in \mathbb{Z}[\mathrm{i}]$, alors $\overline{z}\in \mathbb{Z}[\mathrm{i}]$.


3. Montrer que la somme de deux entiers de Gauss est un entier de Gauss.


4. Montrer que le produit de deux entiers de Gauss est un entier de Gauss.


5. Si $z$ est un entier de Gauss non nul, $\frac{1}{z}$ est‑il un entier de Gauss ?


Partie B : Norme et applications
Si $z$ est un entier de Gauss, on appelle norme la fonction $\text{N}$ : $z⟼z\times \overline{z}$.

1. Soient $a$ et $b$ deux entiers relatifs et $z=a+\mathrm{i}b$.
Déterminer $\mathrm{N}(z)$ en fonction de $a$ et $b$.


2. Montrer que si $z$ et $z^{\prime }$ sont deux entiers de Gauss, alors $\mathrm{N}\left(z{z}^{\prime }\right)=\mathrm{N}(z)\mathrm{N}\left(z^{\prime }\right)$.


3. Première application
a. Montrer que, pour tous entiers relatifs $a$, $b$, $c$ et $d$, $\left(a^2+b^2\right)\left(c^2+d^2\right)=(ac-bd{)}^2+(ad+bc{)}^2$.




b. Soient $m$ et $n$ deux entiers naturels s’écrivant comme la somme de deux carrés parfaits.
Montrer que $m\times n$ s’écrit également comme la somme de deux carrés parfaits.


4. Seconde application
Soit $z\in \mathbb{Z}[\mathrm{i}]$.
On dit que $z$ est inversible dans $\mathbb{Z}[\mathrm{i}]$ lorsqu’il existe un nombre complexe $z^{\prime }\in \mathbb{Z}[\mathrm{i}]$ tel que $z{z}^{\prime }=1$.
Montrer que $z\in \mathbb{Z}[\mathrm{i}]$ est inversible dans $\mathbb{Z}[\mathrm{i}]$ si, et seulement si, $z\in \{1;-1;\mathrm{i};-\mathrm{i}\}$.

16

④ $\mathbf{P}\mathbf{G}\mathbf{C}\mathbf{D}$ et applications  ⑥ Calcul matriciel

D’après bac S, Asie, juin 2015

Une équation de Pell‑Fermat
On dit qu’un entier naturel non nul $\text{N}$ est un nombre triangulaire s’il existe un entier naturel $n$ tel que $\mathrm{N}=1+2+\dots +n$.
Par exemple, $10$ est un nombre triangulaire car $10=1+2+3+4$.
Le but de ce problème est de déterminer des nombres triangulaires qui sont les carrés d’un entier.
On rappelle que, pour tout $n\in {\mathbb{N}}^{\ast }$, on a :
Partie A : Nombres triangulaires et carrés d’entiers
1. Montrer que $36$ est un nombre triangulaire et qu’il est aussi le carré d’un entier.


2. a. Montrer que le nombre $1+2+\dots +n$ est le carré d’un entier si, et seulement si, il existe un entier naturel $p$ tel que $n^2+n-2p^2=0$.


b. Montrer que le nombre $1+2+\dots +n$ est le carré d’un entier si, et seulement si, il existe un entier naturel $p$ tel que $(2n+1{)}^2-8p^2=1$.


Partie B : Étude de l’équation diophantienne associée
On considère $(\mathrm{E})$ l’équation diophantienne $x^2-8y^2=1$, où $x$ et $y$ désignent deux entiers relatifs.

1. Donner deux couples d’entiers naturels inférieurs à $20$ qui sont solutions de $(\mathrm{E})$.


2. Démontrer que si un couple d’entiers relatifs non nuls $(x;y)$ est solution de $(\mathrm{E})$, alors les entiers relatifs $x$ et $y$ sont premiers entre eux.


Partie C : Lien avec le calcul matriciel
Soient $x$ et $y$ deux entiers relatifs. On considère la matrice $\mathrm{A}=\left(\begin{array}{ll}3& 8\\ 1& 3\end{array}\right)$.
On définit les entiers relatifs $x^{\prime }$ et $y^{\prime }$ par l’égalité :
1. Exprimer $x^{\prime }$ et $y^{\prime }$ en fonction de $x$ et de $y$.


2. Déterminer la matrice ${\mathrm{A}}^{-1}$, puis exprimer $x$ et $y$ en fonction de $x^{\prime }$ et $y^{\prime }$.


3. Démontrer que $(x;y)$ est solution de $(\mathrm{E})$ si, et seulement si, $(x^{\prime };y^{\prime })$ est solution de $(\mathrm{E})$.


4. On considère les suites $(x_n)$ et $(y_n)$ définies par $x_0=3$, $y_0=1$ et, pour tout entier naturel $n$ : On admet que, ainsi définis, les nombres $x_n$ et $y_n$ sont des entiers naturels pour toute valeur de l’entier $n$.
Démontrer par récurrence que, pour tout entier naturel $n$, le couple $(x_n;y_n)$ est solution de $(\mathrm{E})$.


Partie D : Retour au problème initial
À l’aide des parties précédentes, déterminer un nombre triangulaire supérieur à $2015$ qui est le carré d’un entier.

17

③ Divisibilité dans $\mathbb{Z}$  ④ $\mathbf{P}\mathbf{G}\mathbf{C}\mathbf{D}$ et applications  ⑥ Calcul matriciel

Chiffrement de Hill
En 1929, le mathématicien et cryptologue Hill publie ses travaux concernant une méthode de chiffrement qui porte aujourd’hui son nom.
Le principe repose sur le choix d’une matrice $\text{A}$ vérifiant les conditions suivantes :

• $\det (\mathrm{A})$ est non nul ;
• $\det (\mathrm{A})$ est premier avec $26$.

On travaillera ici avec la matrice $\mathrm{A}=\left(\begin{array}{ll}7& 2\\ 1& 3\end{array}\right)$.

Partie A : Étude de la matrice $\mathbf{A}$
1. Justifier que la matrice $\text{A}$ vérifie bien les conditions demandées par l’énoncé.


2. À l’aide de la calculatrice, déterminer ${\mathrm{A}}^{-1}$.


Partie B : Étude du chiffrement
Le chiffrement de Hill repose uniquement sur le choix de la matrice $\text{A}$.
Pour coder un mot ayant un nombre pair $n$ de lettres, on procède de la manière suivante :

• on associe à chaque lettre de l’alphabet un nombre entre $0$ et $25$ en suivant l’ordre alphabétique ;
• on divise le mot à chiffrer en blocs de deux lettres successives. On obtient donc plusieurs blocs de nombres $\left(x_1;x_2\right);\dots ;\left(x_{n-1};x_n\right)$ ;
• on utilise alors la matrice $\text{A}$ pour procéder au chiffrement : on calcule, pour tout entier $k\in \left\{0;\dots ;\frac{n-2}{2}\right\}$, $\left(\begin{array}{l}{y}_{2k+1}\\ y_{2k+2}\end{array}\right)=\mathrm{A}\times \left(\begin{array}{l}{x}_{2k+1}\\ x_{2k+2}\end{array}\right)$.
  On obtient alors les blocs $\left(y_1;y_2\right);\dots ;\left(y_{n-1};y_n\right)$ qu’on juxtapose : le mot initialement choisi est alors codé par une suite de nombres $y_1{y}_2\dots y_n$ ;
• on réduit modulo $26$ chacun de ces nombres : pour tout entier $k\in \{1;\dots ;n\}$, on détermine le reste $r_k$ de la division euclidienne de $y_k$ par $26$ ;
• le mot choisi est donc maintenant codé par une suite de nombres $r_1{r}_2\dots r_n$ ;
• on associe à chacun de ces nombres compris entre $0$ et $25$ une lettre selon le procédé décrit précédemment.

1. En utilisant la matrice $\text{A}$ décrite au début de l’exercice, coder le mot JUIN par ce procédé.


2. Coder un mot de votre choix en utilisant ce procédé.
Compte tenu du processus de codage décrit ici, le mot doit être constitué d’un nombre pair de lettres.


3. Compléter le programme ci‑après afin qu’il transforme la liste initiale de nombres en la suite codée de nombres.

def Hill(L):
	n = len(L)
	if n%2 != 0:
		return 'Il faut un nombre de lettres pair !'
	else:
		for k in range(int(n/2)):
			L[2*k], L[2*k + 1] = ... , ...
			L[2*k] = L[2*k]%26
			L[2*k + 1] = L[2*k + 1]%26
	return L

Partie C : Étude du déchiffrement
On cherche ici à déterminer un moyen de déchiffrer un mot chiffré par le procédé précédent. Sans perte de généralité, on étudie uniquement le bloc codé $\left(r_1;r_2\right)$ correspondant au couple de nombres $\left(y_1;y_2\right)$ obtenu après transformation des nombres $\left(x_1;x_2\right)$ du mot initial.
On note donc $\mathrm{Y}=\left(\begin{array}{l}{y}_1\\ y_2\end{array}\right)$ la matrice correspondant aux nombres obtenus suite à la multiplication à gauche de la matrice $\mathrm{X}=\left(\begin{array}{l}{x}_1\\ x_2\end{array}\right)$ par $\text{A}$.
1. Justifier que $\left(x_1;x_2\right)$ est une solution du système d’équations suivant : $\{\begin{array}{l}19x_1=3y_1-2y_2\\ 19x_2=-y_1+7y_2\end{array}$.


2. Montrer que $\left(x_1;x_2\right)$ est une solution du système de congruences suivant : $\{\begin{array}{l}19x_1\equiv 3r_1-2r_2[26]\\ 19x_2\equiv -r_1+7r_2[26]\end{array}$.


3. Déterminer un inverse de $19$ modulo $26$.


4. En déduire que $x_1$ et $x_2$ vérifient le système :

5. Le codage d’un mot a donné OCRR, c’est‑à‑dire la liste $\left(r_1;r_2;r_1^{\prime };r_2^{\prime }\right)=(14;2;17;17)$. On cherche à retrouver le mot initial.
En appliquant le résultat de la question 4. à $\left(\begin{array}{c}14\\ 2\end{array}\right)$ et $\left(\begin{array}{c}17\\ 17\end{array}\right)$, retrouver le mot initial.

18

③ Divisibilité dans $\mathbb{Z}$  ⑥ Calcul matriciel

D’après bac S, Asie, 2017

Exemple simple de code correcteur
Un bit est un symbole informatique élémentaire valant soit $0$, soit $1$.

Partie A : Ligne de transmission
Une ligne de transmission transporte des bits de données selon le modèle suivant :

• elle transmet le bit de façon correcte avec une probabilité $p$ ;
• elle transmet le bit de façon erronée (en changeant le $1$ en $0$ ou le $0$ en $1$) avec une probabilité $1-p$.

On assemble bout à bout plusieurs lignes de ce type et on suppose qu’elles introduisent des erreurs de façon indépendante les unes des autres.
On étudie la transmission d’un seul bit, ayant pour valeur $1$ au début de la transmission.
Après avoir traversé $n$ lignes de transmission, on note :

• $p_n$ la probabilité que le bit reçu ait pour valeur $1$ ;
• $q_n$ la probabilité que le bit reçu ait pour valeur $0$.

On a donc $p_0=1$ et $q_0=0$. On définit les matrices suivantes : $\mathrm{A}=\left(\begin{array}{cc}p& 1-p\\ 1-p& p\end{array}\right)$, ${\mathrm{X}}_n=\left(\begin{array}{l}{p}_n\\ q_n\end{array}\right)$ et $\mathrm{P}=\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)$.
On admet que, pour tout entier $n$, on a ${\mathrm{X}}_{n+1}={\mathrm{A}\mathrm{X}}_n$ et donc ${\mathrm{X}}_n={\mathrm{A}}^n{\mathrm{X}}_0$.

1. a. Montrer que $\text{P}$ est inversible et déterminer ${\mathrm{P}}^{-1}$.


b. On pose $\mathrm{D}=\left(\begin{array}{cc}1& 0\\ 0& 2p-1\end{array}\right)$. Vérifier que $\mathrm{A}={\mathrm{P}\mathrm{D}\mathrm{P}}^{-1}$.


c. Montrer que, pour tout entier $n⩾1$, ${\mathrm{A}}^n={\mathrm{P}\mathrm{D}}^n{\mathrm{P}}^{-1}$.


d. En vous appuyant sur la copie d’écran d’un logiciel de calcul formel donnée ci‑dessous, déterminer une expression de $q_n$ en fonction de $n$.




2. On suppose dans cette question que $p$ vaut $0,98$. On rappelle que le bit avant transmission a pour valeur $1$.
On souhaite que la probabilité que le bit reçu ait pour valeur $0$ soit inférieure ou égale à $0,25$.
Combien peut‑on, au maximum, aligner de telles lignes de transmission ?


Partie B : Le code de Hamming $(7,4)$
On rappelle qu’un bit est un symbole informatique élémentaire valant soit $0$, soit $1$. On considère un « mot » formé de quatre bits que l’on note $b_1$, $b_2$, $b_3$ et $b_4$.
Par exemple, pour le mot $1101$, on a $b_1=1$, $b_2=1$, $b_3=0$ et $b_4=1$.
On ajoute à cette liste une clé de contrôle $c_1{c}_2{c}_3$ formée de trois bits :

• $c_1$ est le reste de la division euclidienne de $b_2+b_3+b_4$ par $2$ ;
• $c_2$ est le reste de la division euclidienne de $b_1+b_3+b_4$ par $2$ ;
• $c_3$ est le reste de la division euclidienne de $b_1+b_2+b_4$ par $2$.

On appelle alors « message » la suite de sept bits formée des quatres bits du mot et des trois bits de contrôle.

1. Préliminaires
a. Justifier que $c_1$, $c_2$ et $c_3$ ne peuvent prendre comme valeurs que $0$ ou $1$.


b. Calculer la clé de contrôle associée au mot $1001$.


2. Soit $b_1{b}_2{b}_3{b}_4$ un mot de quatre bits et $c_1{c}_2{c}_3$ la clé associée.
Démontrer que si on change la valeur de $b_1$ et que l’on recalcule la clé, alors $c_1$ est inchangée, $c_2$ est modifiée et $c_3$ est modifiée.