Un exercice de codage

Codage au bac

Nous sommes cernés par des codes. Nous avons un numéro de sécurité sociale, un ou plusieurs comptes en banque, peut-être un matricule dans notre entreprise ou notre université, notre mutuelle nous en attribue un autre, et ainsi de suite. Ces codes vous sont régulièrement demandés (c’est la preuve qu’ils servent à quelque chose). Donc vous devez les saisir sur un clavier ou un écran tactile. Mais comme ils représentent une suite de chiffres et parfois de lettres dans laquelle vous ne détectez aucune logique, vous pouvez vous tromper et mal les retranscrire. C’est là qu’intervient la CLÉ ! Il s’agit d’un ou deux caractères qui se trouvent à la fin du code et qui permet à un algorithme de détecter si vous avez commis une erreur de frappe.

clé

La notion de congruence est à la base de cet algorithme.

Vous vous demandez pourquoi ? Alors découvrez-le sur cet exercice. C’est celui de la spé maths de l’épreuve du bac S, Amérique du nord, juin 2017. Un autre exercice de codage se trouve en page de codage RSA.

 

Exercice

    Une association gère des activités pour enfants (…).
    L’association affecte à chaque enfant un numéro à 6 chiffres \(c_1c_2c_3c_4c_5c_6k.\) Les deux premiers chiffres représentent l’année de naissance de l’enfant, les trois suivants sont attribués à l’enfant au moment de sa première inscription. Le dernier chiffre, appelé clé de contrôle, est calculé automatiquement de la façon suivante :
  • On effectue la somme \(S\) \(=\) \(c_1 + c_3 + c_5 + a \times (c_2 + c_4)\) où \(a\) est un entier compris entre 1 et 9 ;
  • On effectue la division euclidienne de \(S\) par 10, le reste obtenu est la clé \(k.\)
    Lorsqu’un employé saisit le numéro 6 chiffres d’un enfant, on peut détecter une erreur de saisie lorsque le sixième chiffre n’est pas égal à la clé de contrôle calculée à partir des cinq premiers chiffres.
    1. Dans cette question seulement, on choisit \(a = 3.\)
    a. Le numéro 111383 peut-il être celui d’un enfant inscrit à l’association ?
    b. L’employé, confondant un frère et une sœur, échange leurs années de naissance : 2008 et 2011. Ainsi le numéro \(08c_3c_4c_5k\) est transformé en \(11c_3c_4c_5k.\) Cette erreur est-elle détectée grâce à la clé ?
    2. On note \(c_1c_2c_3c_4c_5k\) le numéro d’un enfant. On cherche les valeurs de l’entier \(a\) pour lesquelles la clé détecte systématiquement la faute de frappe lorsque les chiffres \(c_3\) et \(c_4\) sont invertis. On suppose donc que les chiffres \(c_3\) et \(c_4\) sont distincts.
    a. Montrer que la clé ne détecte pas l’erreur d’inversion des chiffres \(c_3\) et \(c_4\) si et seulement si \((a - 1)(c_4 - c_3)\) est congru à 0 modulo 10.
    b. Déterminer les entiers \(n\) compris entre 0 et 9 pour lesquels il existe un entier \(p\) compris entre 1 et 9 tel que \(np \equiv 0(10).\)
    c. En déduire les valeurs de l’entier \(a\) qui permettent ; grâce à la clé, de détecter systématiquement l’interversion des chiffres \(c_3\) et \(c_4.\)

 

Corrigé

1. a. Calculons \(S.\)

\(S\) \(=\) \(1 + 1 + 8 + 3(1 + 3)\) \(=\) \(22.\) Si l’on divise 22 par 10, le reste est 2 et non 3. Le numéro ne peut pas être celui d’un enfant inscrit à l’association.

b. \(S_1\) \(=\) \(0 + c_3 + c_5 + 3(8 + c_4)\)
\(S_1\) \(=\) \(c_3 + c_5 + 3c_4 + 24\)

\(S_2\) \(=\) \(1 + c_3 + c_5 + 3(1 + c_4)\)
\(S_2\) \(=\) \(c_3 + c_5 + 3c_4 + 4\)

Donc \(S_1 = S_2 + 20.\)

Ainsi \(S_1\) et \(S_2\) sont congrus modulo 20 (donc modulo 10). \(S_1 \equiv S_2[10].\) Les clés associées aux deux numéros étant les mêmes, l’erreur ne peut pas être détectée.

2. a. Soit \(S_a\) \(=\) \(c_1 + c_3 + c_5 + a(c_2 + c_4)\) et \(S_b\) \(=\) \(c_1 + c_4 + c_5 + a(c_2 + c_3).\)

La clé ne peut pas alerter d'une erreur si \(S_a \equiv S_b[10].\)

Autrement dit si \(S_a - S_b \equiv 0[10]\)
\(⇔ c_3 - c_4 + a(c_2 + c_4) - a(c_2 + c_3)\) \(\equiv\) \(0[10]\)
\(⇔ c_3 - c_4 + ac_4 - ac_3\) \(\equiv\) \(0[10]\)

Or \((a - 1)(c_4 - c_3)\) \(=\) \(ac_4 - ac_3 - c_4 + c_3\)

Effectivement, la clé ne détecte rien si et seulement si \((a - 1)(c_4 - c_3)\) \(\equiv\) \(0[10].\)

b. Pour cette question, nous déterminerons les restes d’une division par 10 de tous les produits \(np\) avec \(n\) et \(p\) entiers compris entre 0 et 9.

Il n’est pas difficile de répondre à cette question sans le moindre outil informatique. Toutefois, dans un souci de clarté, nous emploierons Excel (ce qui était impossible lors de l’épreuve du bac).

Construisons un premier tableau qui n’est autre… que la table de multiplication.

table de multiplication

Un second tableau nous indique les restes d'une division par 10 grâce à la fonction MOD (qui fait référence au tableau précédent).

restes

Les entiers \(n\) pour lesquels il existe un entier \(p\) compris entre 1 et 9 et qui vérifient \(np \equiv 0[10]\) sont 0, 2, 4, 5, 6 et 8 (colonnes dans lesquelles se trouve au moins un zéro).

c. Nous savons que \((a - 1)(c_4 - c_3)\) \(\equiv\) \(0[10].\)

On ne peut pas détecter une inversion entre \(c_3\) et \(c_4\) si \(a - 1\) est égal à 0, 2, 4, 5, 6 ou 8.

Donc il faut que \(a - 1\) soit égal à 1, 3 ou 7 (il est impossible que cette expression soit égale à 9 puisque \(a\) ne peut être égal à 10).

Pour que l’inversion soit détectée entre \(c_3\) et \(c_4,\) \(a\) doit être égal à 2, 4 ou 8 (d'ailleurs nous avons remarqué à la question 1 qu'il était malvenu de choisir 3).

 

clé de codage