Un exercice de codage

Codage au bac S

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 écrire ou les saisir sur Internet. 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.

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.

Exercice

Une association gère des activités pour enfants (…).

L’association affecte à chaque enfant un numéro à 6 chiffres c1c2c3c4c5c6k. 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 = c1 + c3 + c5 + a × (c2 + c4) 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 08c3c4c5k est transformé en 11c3c4c5k. Cette erreur est-elle détectée grâce à la clé ?

2. On note c1c2c3c4c5k 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 c3 et c4 sont invertis. On suppose donc que les chiffres c3 et c4 sont distincts.

a. Montrer que la clé ne détecte pas l’erreur d’inversion des chiffres c3 et c4 si et seulement si (a – 1)(c4 – c3) 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 ≡ 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 c3 et c4.

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. S1 = 0 + c3 + c5 + 3(8 + c4)
S1 = c3 + c5 + 3c4 + 24

S2 = 1 + c3c5 + 3(1 + c4)
S2 = c3 + c5 + 3c4 + 4

Donc S1 = S2 + 20.

Ainsi S1 et S2 sont congrus modulo 20 (donc modulo 10). S1 ≡ S2[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 Sa = c1 + c3c5a(c2 + c4) et Sb = c1 + c4 + c5a(c2c3).

La clé ne peut pas alerter d'une erreur si Sa ≡ Sb[10].

Autrement dit si Sa – Sb ≡ 0[10]
 c3 – c4 + a(c2 + c4) – a(c2 + c3) ≡ 0[10]
 c3 – c4 + ac4 – ac3 ≡ 0[10]

Or (a – 1)(c4 – c3) = ac4 – ac3 – c4c3

Effectivement, la clé ne détecte rien si et seulement si (a – 1)(c4 – c3) ≡ 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 ≡ 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)(c4 – c3) ≡ 0[10].

On ne peut pas détecter une inversion entre c3 et c4 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 c3 et c4, a doit être égal à 2, 4 ou 8 (d'ailleurs nous avons remarqué à la question 1 qu'il était malvenu de choisir 3).