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
, where
represents 10 in Roman numerals. Let
, for
, refer to the 10 symbols. The symbol
is chosen as the remainder of the sum
when divided by 11. In our example we see that
2026 Error-Correcting Codes
and
.
(a) Show that this code can detect an error in one digit.
(b) Show that the sum
is divisible by 11.
(c) Find the last digit of the following ISBN code:
ISBN 0-7267-3514-?.
(a) Show that this code can detect an error in one digit.
(b) Show that the sum
(c) Find the last digit of the following ISBN code:
Passo 1
Vou listar claramente o que o enunciado dá e o que pede.
-
Dados fornecidos:
- Existem 10 símbolos
. Cada vale um número em , sendo o símbolo equivalente ao número . - Define-se
- O dígito de verificação
é escolhido como o resto da divisão de por . Ou seja, existe um inteiro tal que - O conjunto de símbolos para
inclui quando o resto é .
- Existem 10 símbolos
-
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é divisível por.\n
(c) Encontrar o último dígito (o) do ISBN . Aqui os nove primeiros símbolos são, na ordem, .
Passo 2
Noções básicas necessárias (explicadas de forma simples e com calma).
-
Resto da divisão por
: dizer que um número é o resto de por significa que existe com Em linguagem modular, escreve-se. -
Propriedade útil: se um produto
é múltiplo de e não é múltiplo de , então também é múltiplo de . Aqui usamos que é primo, logo não divide para . Em particular, para existe um inverso multiplicativo módulo , portanto . -
Interpretação para este código: a verificação é feita testando se a soma ponderada
é múltiplo de . Se essa soma não for múltipla de , 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
e que por erro apenas o símbolo na posição (com ) foi alterado para (com ). Todos os outros permanecem iguais. -
A soma ponderada original valeDepois do erro, a nova soma é
-
Como o código foi construído, a soma correta
é múltipla de (veremos a demonstração formal no Passo 4). Logo . Portanto -
Agora,
é um inteiro entre e . Como é primo, nenhum desses é múltiplo de ; portanto tem inverso módulo . Assim, se então necessariamente , o que implica (pois ambos estão no intervalo ). Mas isso contradiz a hipótese . Logo necessariamente isto é, a soma ponderada deixa de ser múltipla dee o erro é detectado. -
Conclusão do (a): qualquer alteração em apenas um símbolo (em qualquer posição
) altera o valor da soma módulo , portanto o código detecta um erro em um único dígito.
Passo 4
Prova do item (b): mostrar que
é divisível por
.
-
Lembre que
e que foi escolhido como o resto da divisão de por . Então existe tal que -
Calcule a soma total:
-
Substituindo
obtemos -
Portanto
é múltiplo de . Isto conclui (b).
Passo 5
Cálculo do item (c): encontrar o último dígito para ISBN
.
-
Primeiro identifique os nove primeiros símbolos
pela leitura da esquerda para a direita (ignorando traços): -
Calcular
-
Faço as multiplicações uma a uma e somo (mostrando passo a passo):
-
Somando em ordem:
Logo
.
Passo 6
Determinar o resto de
por
e o dígito
.
-
Dividindo
por : . Portanto o resto é . Em notação de divisão, -
Pelo modo como
foi definido (resto de por ), temos . (Se o resto fosse usar-se-ia o símbolo .) -
Verificação rápida: com
, que é, como já vimos, múltiplo de, consistente com (b).
Resposta
(a) Sim. Um erro em um único dígito altera a soma ponderada por um valor
com
; como
não é múltiplo de
, isso não pode ser congruente a zero salvo se
, logo o erro é detectado.
(b)
é divisível por
.
(c)