Problème — Clé de contrôle (numéro ISBN)

Arithmétique · niveau 3 (difficile)

Énoncé

Problème — Clé de contrôle (numéro ISBN).

Le numéro ISBN-10 d'un livre est une suite de 10 symboles $c_{1} c_{2} \dots c_{10}$ où $c_{1}, \dots, c_{9}$ sont des chiffres et la clé $c_{10} \in {0, 1, \dots, 9, X}$ (X représentant 10) est choisie pour que :

$i = 1 \sum 10 i \cdot c_{i} \equiv 0 (mod 11)$

Calculer la clé $c_{10}$ du numéro commençant par 2-1234-5678 (c'est-à-dire $c_{1}, \dots, c_{9} = 2, 1, 2, 3, 4, 5, 6, 7, 8$ ).
Démontrer que ce code détecte toute erreur portant sur un seul symbole.

Corrigé

Calculons $S = \sum_{i = 1}^{9} i \cdot c_{i} = 1 (2) + 2 (1) + 3 (2) + 4 (3) + 5 (4) + 6 (5) + 7 (6) + 8 (7) + 9 (8)$ :

$S = 2 + 2 + 6 + 12 + 20 + 30 + 42 + 56 + 72 = 242$

On veut $S + 10 c_{10} \equiv 0 (mod 11)$ . Or $242 = 22 \times 11$ , donc $242 \equiv 0$ , et il reste $10 c_{10} \equiv 0 (mod 11)$ . Comme $pgcd (10, 11) = 1$ , on conclut $c_{10} \equiv 0$ : la clé est $c_{10} = 0$ .

Supposons qu'un seul symbole change : $c_{i}$ devient $c_{i}^{'} \neq = c_{i}$ (position $i$ fixée). La somme de contrôle varie de :

$Δ = i (c_{i}^{'} - c_{i})$

avec $1 \leq i \leq 10$ et $0 < ∣ c_{i}^{'} - c_{i} ∣ \leq 10$ . Comme $11$ est premier et ne divise ni $i$ ni $c_{i}^{'} - c_{i}$ (tous deux de valeur absolue $< 11$ et non nuls), il ne divise pas leur produit $Δ$ (conséquence du théorème de Gauss). La nouvelle somme n'est donc plus $\equiv 0 (mod 11)$ : l'erreur est détectée.