Baccalauréat S Antilles Guyane 22 juin 2015 - Correction Spécialité
Correction de l'exercice de Spécialité 5 points
Les parties A et B peuvent être traitées de façon indépendante
Partie A
Pour deux entiers naturels non nuls $a$ et $b$, on note $r(a,~b)$ le reste dans la division euclidienne de $a$ par $b$. On considère l'algorithme suivant : $$\begin{array}{|l|X|}\hline \text{ Variables :} & c \text{ est un entier naturel}\\ &a \text{ et } b \text{ sont des entiers naturels non nuls }\\ \text{ Entrées : }&\text{ Demander } a\\ &\text{ Demander } b\\ \text{ Traitement: }&\text{ Affecter à } c \text{ le nombre } r(a,~b)\\ &\text{ Tant que }c \ne 0\\ &\hspace{0.5cm}\text{ Affecter à } a \text{ le nombre } b\\ &\hspace{0.5cm}\text{ Affecter à } b \text{ la valeur de } c\\ &\hspace{0.5cm}\text{ Affecter à } c \text{ le nombre } r(a,~b)\\ &\text{ Fin Tant que }\\ Sortie : &\text{ Afficher } b\\ \hline \end{array}$$
- Faire fonctionner cet algorithme avec $a = 26$ et $b = 9$ en indiquant les valeurs de $a$, $b$ et $c$ à chaque étape. $\begin{array}{|c|c|c|c|c|}
- 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. Variables :
\hline
a&26&9&5&4\\ \hline
b&9&5&4&1\\ \hline
c&5&4&1&0\\ \hline
\end{array}$
L’algorithme affichera donc $1$
$\quad$ $c$ est un entier naturel
$\quad$ $a$ et $b$ sont des entiers naturels non nuls
Entrées :
$\quad$ Demander $a$
$\quad$ Demander $b$
Traitement :
$\quad$ affecter à $c$ le nombre $r(a,b)$
$\quad$ Tant que $c \neq 0$
$\qquad$ Affecter à $a$ le nombre $b$
$\qquad$ Affecter à $b$ la valeur de $c$
$\qquad$ Affecter à $c$ le nombre $r(a,b)$
$\quad$ Fin Tant que
$\quad$ Si $b=1$
$\qquad$ alors Afficher « $a$ et $b$ sont premiers entre eux »
$\qquad$ sinon Afficher « $a$ et $b$ ne sont pas premiers entre eux »
$\quad$ Fin Si
$\quad$
Partie B
À chaque lettre de l'alphabet on associe grâce au tableau ci-dessous un nombre entier compris entre 0 et 25. $$ \begin{array}{ |c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline A &B &C &D &E &F &G &H &I& J &K &L &M\\ \hline 0& 1 &2 &3 &4 &5 &6 &7 &8 &9 &10 &11 &12\\ \hline\hline N&O&P&Q&R&S&T&U&V&W&X&Y&Z\\ \hline 13&14&15&16&17&18&19&20&21&22&23&24&25\\ \hline \end{array} $$ On définit un procédé de codage de la façon suivante :
- Étape 1 : on choisit deux entiers naturels $p$ et $q$ compris entre $0$ et $25$.
- Étape 2 : à la lettre que l'on veut coder, on associe l'entier $x$ correspondant dans le tableau ci-dessus.
- Étape 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.\]
- Étape 4 : à l'entier $x'$, on associe la lettre correspondante dans le tableau.
- Dans cette question, on choisit $p = 9$ et $q = 2$.
- Démontrer que la lettre V est codée par la lettre J. Etape 1 : $p=9$ et $q=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. Les nombres $9$ et $26$ sont premiers entre eux (d’après la question A.1.).
- Démontrer que $x' \equiv 9x + 2\quad [26]$ équivaut à $x \equiv 3x' + 20\quad [26]$. $$\begin{array}{rl} x’ \equiv 9x + 2~[26] & \iff 3x’ \equiv 27x + 6 ~[26] \\ & \iff 3x’ \equiv x + 6~[26] \\ & \iff 3x’ – 6 \equiv x ~[26] \\ & \iff 3x’ + 20 \equiv x ~[26]\end{array}$$
- Décoder la lettre R.
Etape 2 : On choisit V. Donc $x=21$
Etape 3 : $px + q = 191 \equiv 9 ~[26]$
Etape 4 : La lettre associée à $9$ est J
$\quad$
D’après le théorème de Bezout, il existe alors au moins un couple d’entiers relatifs $(u,v)$ tel que $9u+26v=1$.
Si on obtient la lettre R, alors $x’= 17$ - 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 est codé par D. Cela signifie donc que si $x=9$ alors $x’=3$
- Dans cette question, on choisit $p = 13$ et $q = 2$. Coder les lettres B et D. Que peut-on dire de ce codage ? $p=13$ et $q=2$
Or $3 \times 17 + 20 = 71 \equiv 19~[26] $
La lettre initiale était donc T.
Avec $x’ \equiv px + 2~[26] $
Soit $3\equiv 9p + 2~[26]$
par conséquent $9p \equiv 1~[26] $
Or $9\times 3 = 27 \equiv 1~[26]$
Donc $p = 3$
Si on choisit la lettre $B$ alors $x=1$
Par conséquent $13 \times 1 + 2 = 15 \equiv 15~[26]$ donc $x’ = 15$
On obtient ainsi la lettre P.
$\quad$
Si on choisit la lettre $D$ alors $x= 3$
Par conséquent $13 \times 3 + 2 = 41 \equiv 15~[26]$ donc $x’=15$
On obtient ainsi la lettre P.
Ce codage n’est pas utilisable car deux lettres différentes sont codées par la même lettre. Il n’y a pas unicité du codage
- Vues: 27951