Logo maths-cours.fr maths-cours.fr
Logo maths-cours.fr maths-cours.fr
Connexion Inscription
Divisibilité et congruences Exercices

Codage – Bac S Nouvelle Calédonie 2013

Durée estimée
20 minutes
Difficulté
Votre progression

Créez un compte gratuit pour suivre votre avancement et reprendre où vous avez laissé.

Créer un compte

Objectif travaillé

Exercices

Bac S Nouvelle Calédonie 2013

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é « * », considéré comme un caractère.

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

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 \mapsto 0$, $b \mapsto 1$, … $z \mapsto 25$.

On associe au séparateur « * » le nombre $26$.

a b c d e f g h i j k l m n o
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
p q r s t u v w x y z *
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 « * » a pour rang $26$.

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

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

Exemple : $s \mapsto 18$, $g(18) = 21$ et $21 \mapsto 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 \ \left[27\right]$ alors $x \equiv 7y+6 \ \left[27\right]$. 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 ».

Corrigé

  1. $g(x) = x$ si et seulement si $0 \leqslant x \leqslant 26$ et :

    $ 4x+3 \equiv x \ \left[27\right] $

    Cette congruence est vérifiée si et seulement s'il existe un entier relatif $k$ tel que :

    $ 4x+3 = x + 27k $

    $ 3x = 27k - 3 $

    $ x = 9k - 1 $

    Pour $k \leqslant 0$, les valeurs de $x$ obtenues sont strictement négatives ; pour $k > 3$, elles sont strictement supérieures à $26$.

    On obtient donc trois solutions comprises entre $0$ et $26$ :

    • $x = 8$ (pour $k = 1$)
    • $x = 17$ (pour $k = 2$)
    • $x = 26$ (pour $k = 3$)

    Par conséquent, les caractères invariants dans ce codage sont $i$, $r$ et *.

  2. Si $y \equiv 4x+3 \ \left[27\right]$ alors :

    $ 7y \equiv 7(4x+3) \ \left[27\right] $

    $ 7y \equiv 28x + 21 \ \left[27\right] $

    Comme $28 \equiv 1 \ \left[27\right]$ et $21 \equiv -6 \ \left[27\right]$, on a alors :

    $ 7y \equiv x - 6 \ \left[27\right] $

    donc $ x \equiv 7y + 6 \ \left[27\right] $.

    Soient deux entiers naturels $x$ et $x'$, compris entre $0$ et $26$, ayant la même image $y$ par $g$. Alors $g(x) = y$ et $g(x') = y$.

    Par conséquent, $x \equiv 7y + 6 \ \left[27\right]$ et $x' \equiv 7y + 6 \ \left[27\right]$.

    Donc, comme $x$ et $x'$ sont compris entre $0$ et $26$, ils sont tous deux le reste de la division euclidienne de $7y+6$ par $27$. L'unicité du reste entraîne que $x = x'$.

    Par conséquent, si deux caractères sont codés de façon identique, c'est qu'ils sont identiques. Autrement dit, deux caractères distincts sont codés par deux caractères distincts.

  3. La formule $x \equiv 7y + 6 \ \left[27\right]$ permet de décoder un caractère. Il suffit de procéder de la façon suivante :

    • 1ʳᵉ étape : à chaque lettre on associe son rang $y$.
    • 2ᵉ étape : à chaque valeur de $y$, l'application $h$ associe le reste de la division euclidienne de $7y+6$ par $27$.
    • 3ᵉ étape : le caractère initial est alors remplacé par le caractère de rang $h(y)$ trouvé à la seconde étape.

  4. On utilise la méthode décrite précédemment :

    • $v \mapsto y = 21$ ; $h(21)$ est le reste de la division de $7 \times 21 + 6 = 153$ par $27$. Or $153 = 27 \times 5 + 18$ donc $h(21) = 18$ et $18 \mapsto s$.
    • $f \mapsto y = 5$ ; $h(5)$ est le reste de la division de $7 \times 5 + 6 = 41$ par $27$. Or $41 = 27 \times 1 + 14$ donc $h(5) = 14$ et $14 \mapsto o$.

    Le mot « vfv » se décode donc en « sos ».