Most books have an ISBN code (for International Standard Book Number), and this code is unique to each book. This code consists of 10 numbers. For example, ISBN 2-12345-678-0. The first three segments identify the linguistic group, the publishing house, and the volume. The last is an error-detection symbol chosen from \{0,1,2,3,4,5,6,7,8,9, X\}, where X represents 10 in Roman numerals. Let a_{i}, for i=1, \ldots, 10, refer to the 10 symbols. The symbol a_{10} is chosen as the remainder of the sum b=\sum_{i=1}^{9} i a_{i} when divided by 11. In our example we see that
2026 Error-Correcting Codes
b=1 \times 2+2 \times 1+3 \times 2+4 \times 3+5 \times 4+6 \times 5+7 \times 6+8 \times 7+9 \times 8=242=11 \times 22+0 and a_{10}=0.
(a) Show that this code can detect an error in one digit.
(b) Show that the sum \sum_{i=1}^{10} i a_{i} is divisible by 11.
(c) Find the last digit of the following ISBN code:
ISBN 0-7267-3514-?.

Passo 1

Vou listar claramente o que o enunciado dá e o que pede.
  • Dados fornecidos:
    • Existem 10 símbolos a_{1},\dots,a_{10}. Cada a_i vale um número em \{0,1,\dots,9,10\}, sendo o símbolo X equivalente ao número 10.
    • Define-se b=\sum_{i=1}^{9} i\,a_{i}.
    • O dígito de verificação a_{10} é escolhido como o resto da divisão de b por 11. Ou seja, existe um inteiro q tal que b=11q + a_{10},\qquad 0\le a_{10}\le 10.
    • O conjunto de símbolos para a_{10} inclui X quando o resto é 10.
  • O que o enunciado pede:
    (a) Mostrar que esse código detecta um erro em um único dígito (ou seja, se apenas um símbolo é alterado, o erro é percebido).\n
    (b) Mostrar que
    \sum_{i=1}^{10} i\,a_{i}
    é divisível por 11.\n
    (c) Encontrar o último dígito (o a_{10}) do ISBN 0\text{-}7267\text{-}3514\text{-}?. Aqui os nove primeiros símbolos são, na ordem, 0,7,2,6,7,3,5,1,4.

Passo 2

Noções básicas necessárias (explicadas de forma simples e com calma).
  • Resto da divisão por 11: dizer que um número r é o resto de b por 11 significa que existe q\in\mathbb{Z} com
    b=11q + r,\qquad 0\le r\le 10.
    Em linguagem modular, escreve-se b\equiv r\pmod{11}.
  • Propriedade útil: se um produto k\cdot \Delta é múltiplo de 11 e k não é múltiplo de 11, então \Delta também é múltiplo de 11. Aqui usamos que 11 é primo, logo não divide k para k=1,\dots,10. Em particular, para k=1,\dots,10 existe um inverso multiplicativo módulo 11, portanto k\cdot \Delta\equiv 0\pmod{11}\Rightarrow \Delta\equiv 0\pmod{11}.
  • Interpretação para este código: a verificação é feita testando se a soma ponderada \sum_{i=1}^{10} i\,a_i é múltiplo de 11. Se essa soma não for múltipla de 11, detecta-se erro.

Passo 3

Prova do item (a): detecção de erro em um único dígito.
  • Suponha que na mensagem correta os símbolos são a_1,\dots,a_{10} e que por erro apenas o símbolo na posição k (com 1\le k\le 10) foi alterado para a_k' (com a_k'\neq a_k). Todos os outros a_i permanecem iguais.
  • A soma ponderada original vale
    S=\sum_{i=1}^{10} i\,a_i.
    Depois do erro, a nova soma é
    S'=\sum_{i=1}^{10} i\,a_i + k\,(a_k'-a_k) = S + k\,(a_k'-a_k).
  • Como o código foi construído, a soma correta S é múltipla de 11 (veremos a demonstração formal no Passo 4). Logo S\equiv 0\pmod{11}. Portanto
    S'\equiv k\,(a_k'-a_k)\pmod{11}.
  • Agora, k é um inteiro entre 1 e 10. Como 11 é primo, nenhum desses k é múltiplo de 11; portanto k tem inverso módulo 11. Assim, se k\,(a_k'-a_k)\equiv 0\pmod{11} então necessariamente a_k'-a_k\equiv 0\pmod{11}, o que implica a_k'=a_k (pois ambos estão no intervalo 0,\dots,10). Mas isso contradiz a hipótese a_k'\neq a_k. Logo necessariamente
    S'\not\equiv 0\pmod{11},
    isto é, a soma ponderada deixa de ser múltipla de 11 e o erro é detectado.
  • Conclusão do (a): qualquer alteração em apenas um símbolo (em qualquer posição 1\le k\le 10) altera o valor da soma módulo 11, portanto o código detecta um erro em um único dígito.

Passo 4

Prova do item (b): mostrar que \sum_{i=1}^{10} i\,a_i é divisível por 11.
  • Lembre que b=\sum_{i=1}^{9} i\,a_i e que a_{10} foi escolhido como o resto da divisão de b por 11. Então existe q\in\mathbb{Z} tal que
    b=11q + a_{10},\qquad 0\le a_{10}\le 10.
  • Calcule a soma total:
    \sum_{i=1}^{10} i\,a_i = \bigg(\sum_{i=1}^{9} i\,a_i\bigg) + 10\,a_{10} = b + 10\,a_{10}.
  • Substituindo b=11q+a_{10} obtemos
    b + 10\,a_{10} = (11q + a_{10}) + 10\,a_{10} = 11q + 11\,a_{10} = 11(q+a_{10}).
  • Portanto \sum_{i=1}^{10} i\,a_i é múltiplo de 11. Isto conclui (b).

Passo 5

Cálculo do item (c): encontrar o último dígito para ISBN 0\text{-}7267\text{-}3514\text{-}?.
  • Primeiro identifique os nove primeiros símbolos a_1,\dots,a_9 pela leitura da esquerda para a direita (ignorando traços):
    a_1=0,\\ a_2=7,\\ a_3=2,\\ a_4=6,\\ a_5=7,\\ a_6=3,\\ a_7=5,\\ a_8=1,\\ a_9=4.
  • Calcular
    b=\sum_{i=1}^{9} i\,a_i = 1\cdot 0 + 2\cdot 7 + 3\cdot 2 + 4\cdot 6 + 5\cdot 7 + 6\cdot 3 + 7\cdot 5 + 8\cdot 1 + 9\cdot 4.
  • Faço as multiplicações uma a uma e somo (mostrando passo a passo):
    \begin{aligned} 1\cdot 0 &= 0,\\\\ 2\cdot 7 &= 14,\\\\ 3\cdot 2 &= 6,\\\\ 4\cdot 6 &= 24,\\\\ 5\cdot 7 &= 35,\\\\ 6\cdot 3 &= 18,\\\\ 7\cdot 5 &= 35,\\\\ 8\cdot 1 &= 8,\\\\ 9\cdot 4 &= 36. \end{aligned}
  • Somando em ordem:
    14+6=20,\quad 20+24=44,\quad 44+35=79,\quad 79+18=97,
97+35=132,\quad 132+8=140,\quad 140+36=176.
Logo b=176.

Passo 6

Determinar o resto de b por 11 e o dígito a_{10}.
  • Dividindo 176 por 11: 11\times 16 = 176. Portanto o resto é 0. Em notação de divisão,
    176 = 11\cdot 16 + 0.
  • Pelo modo como a_{10} foi definido (resto de b por 11), temos a_{10}=0. (Se o resto fosse 10 usar-se-ia o símbolo X.)
  • Verificação rápida: com a_{10}=0,
    \sum_{i=1}^{10} i\,a_i = b + 10\cdot 0 = 176,
    que é, como já vimos, múltiplo de 11, consistente com (b).

Resposta

(a) Sim. Um erro em um único dígito altera a soma ponderada por um valor k(a_k'-a_k) com 1\le k\le 10; como k não é múltiplo de 11, isso não pode ser congruente a zero salvo se a_k'=a_k, logo o erro é detectado.
(b) \displaystyle \sum_{i=1}^{10} i\,a_i é divisível por 11.
(c) 0

Exercícios relacionados