aplicacoes_congruencia_modulo_m

Prévia do material em texto

ÁLGEBRA 1
APLICAÇÕES DA 
CONGRUÊNCIA MÓDULO ܯ
Prof. Msc. Cassius Gomes de Oliveira
2013/2
 Uma das ferramentas mais importantes na
teoria dos números é a aritmética modular que
envolve o conceito de congruência;
Definição: Uma congruência pode ser definida
como uma relação entre dois números inteiros
que divididos por um terceiro – chamado
módulo de congruência – deixam o mesmo
resto.
EXEMPLO: 9 é congruente a 2 módulo 7,
pois, ambos deixam resto 2 quando divididos
por 7.
Notação: ૢ ≡ ૛(࢓࢕ࢊ		ૠ)
Carl Friedrich Gauss (1777 - 1855)
foi o primeiro a observar que
com muita frequência ocorriam 
situações do tipo: 
“ܽ dá o mesmo resto que ܾ
quando divididos por ݉	"	
Exemplos Iniciais
EXEMPLO 1: ܣ,ܤ,ܥ,ܦ,ܧ,ܨ,ܩ,ܪ são os fios de apoio
que uma aranha usa para construir sua teia conforme a
figura (1) a seguir. A aranha continua seu trabalho.
Sobre qual fio de apoio estará o número 118 ?
Solução:
 Note que os fios se repetem a cada oito
números e assim, termos uma progressão
aritmética de razão 8.
 Note que o fio ܤ, corresponde aos números
que divididos por 8, deixam resto 1	 8݊ + 1 ;
 Note que o fio ܥ corresponde aos números
que divididos por 8, deixam resto 2	 8݊ + 2 .
 Note que está lógica se mantém até o fio ܪ.
 Obviamente, para saber sobre qual fio estará
o número 118, basta verificarmos a qual
destas famílias tal número pertence e isso é
obtido ao dividirmos 118 por 8. Logo, temos:118 = 8 ∙ 14 + 6
Assim, o número 118, pertence a família dos
números que estão no fio ܩ.
 Note que todos os números que estão no
mesmo fio, deixam o mesmo resto ao serem
divididos por 8.
Por exemplo, o número 14 é congruente ao22	módulo 8, pois, deixam o mesmo resto ao
serem divididos por 8, ou seja,14	 ≡ 22	(݉݋݀	8)
EXEMPLO 2: Nos relógios analógicos, note que13 é congruente a 1 módulo 12, 17 é congruente
a 5 módulo 12, e assim sucessivamente, ou seja,1 ≡ 13 ≡ 25 ≡ ⋯ ݉݋݀	125 ≡ 17 ≡ 29	 ≡ ⋯ ݉݋݀	12
Portanto, as horas marcadas num relógio
analógico também são um caso clássico de
congruência módulo 12.
EXEMPLO 3: Vamos supor que você saiba em
qual dia da semana caiu o dia 1º de janeiro de
um determinado ano. Por exemplo, em 2006 foi
um domingo.
Questão: Quando cairá um outro dia qualquer
(vale para qualquer ano) ?
Neste caso, vamos montar uma tabela para
essa primeira semana, ou seja,
Note que temos neste caso, um caso de
congruência módulo 7.
Por exemplo, em dia da semana caiu o dia 5 de
julho de 2006 ?
Domingo Segunda Terça Quarta Quinta Sexta Sábado
1 2 3 4 5 6 7
 Inicialmente, vamos verificar quantos dias
existem de 1 de janeiro até 5 de julho:
Janeiro 31 dias
Fevereiro 28 dias
Março 31 dias
Abril 30 dias
Maio 31 dias
Junho 30 dias
Julho 5 dias
TOTAL 186 dias
 Assim, temos uma “fila” de 186 dias e estamos
desejando saber, na congruência de módulo 7
(7 dias da semana), qual o correspondente ao
186. Logo, utilizando o algoritmo da divisão,
temos:186 = 7 ∗ 26 + 4	 ⟺ 186 ≡ 4	 ݉݋݀	7
 Portanto, como 4 de janeiro de 2006 foi uma
quarta-feira, o 186º desse mesmo ano também
será e, é claro que todas as demais quarta-
feiras deste ano serão ocupados por números
congruentes ao 4 módulo 7.
ISBN (International Standard Book Number)
 Este é o sistema internacional de catalogação de
livros, CD-roms e publicações em braile que foi criado
em 1969.
 Neste sistema, as publicações são identificadas
através de 10 algarismos, sendo que o último (dígito
de controle) é calculado através da aritmética modular
envolvendo operações matemáticas com os outros
nove dígitos.
 Por exemplo, a língua inglesa é identificada somente
pelo algarismo 0 e a editora McGraw-Hill tem um
código de 2 algarismos que a indentifica. Logo, restam
ainda 6 algarismos para a identificação de suas
publicações, havendo pois a possibilidade de10 ଺ = 1000000	ݐíݐݑ݈݋ݏ
Cálculo do dígito final do ISBN (controle)
 Seja, ܽ଴, ܽଵ, ܽଶ, … , ܽଽ	a sequência formada pelos 9 dígitos;
 Vamos multiplicá-los nessa ordem, pela base10,9,8,7,6,5,4,3,2
e somar os produtos obtidos.
 O dígito que está faltando, representado por ܽଵ଴ deve ser o
menor valor possível, tal que ao ser acrescentado à soma obtida,
deve gerar um múltiplo de 11, ou seja, se a soma obtida é ܵ, o
número ܵ + ܽଵ଴	 deve ser múltiplo de 11, ou seja,
ܵ + ܽଵ଴ ≡ 0	(݉݋݀	11)
EXEMPLO: Na contracapa do livro Temas e Problemas
Elementares, da Coleção Professor de Matemática, da SBM, temos
o seguinte código ISBN:
ܫܵܤܰ: 85 − 85818 − 29 − ૡ
Vejamos o cálculo do dígito de controle que como estamos 
observando é igual a 8.	
 Logo, efetuando as multiplicações correspondentes e somando 
os produtos obtidos, obtemos:8 ∙ 10 + 5 ∙ 9 + 8 ∙ 8 + 5 ∙ 7 + 8 ∙ 6 + 1 ∙ 5 + 8 ∙ 4 + 2 ∙ 3 + 9 ∙ 2 = 333
8 5 8 5 8 1 8 2 9
10 9 8 7 6 5 4 3 2
 Utilizando o algoritmo da divisão, temos:333 = 11 ∙ 30 + 3
 Assim, para atendermos a condição:
“a soma obtida é ܵ, o número ܵ + ܽଵ଴	 deve ser múltiplo de 11, ou 
seja,ܵ + ܽଵ଴ ≡ 0	(݉݋݀	11)”
 Assim, para obtermos um múltiplo de 11 ao acrescentarmos o
décimo algarismo, o menor valor que atende a tal condição será o
número 8, pois: 11 − 3 = 8
EXERCÍCIO: O livro Matemática Aplicada a Administração,
Economia e Contabilidade, da Editora Thompson, tem o seguinte
ISBN: 85 – 221 – 0399 – x .
Qual é o dígito de controle x ?
Solução: Neste caso, temos:
Efetuando a soma dos produtos correspondentes, obtemos:80 + 45 + 16 + 14 + 6 + 0 + 12 + 27 + 18 = 218
Logo, temos: 218 = 11 ∙ 19 + 9
Portanto, o código de controle é igual a 2 = 11 − 9
8 5 2 2 1 0 3 9 9
10 9 8 7 6 5 4 3 2
Observações:
 No ISBN, se o dígito for igual a 10 (no caso do resto da divisão
por 11 ser igual a 1), é utilizada a representação do 10 em
algarismos romanos, ou seja, ܺ.
 Em todos os casos apresentados, são utilizadas bases de
multiplicação que operadas com os dígitos do número geram um
determinado valor ܵ. A esse valor obtido deve ser somado ou
subtraído um valor ݔ, que modo que exista um congruência ao
zero, num módulo que normalmente é 11 ou 10.
 A partir de janeiro de 2007, os códigos do ISBN estão sendo
representados com 13 dígitos. No caso dos livros editados no
Brasil há um acréscimo dos dígitos 978 antes do 85.
Cadastro de Pessoas Físicas na Receita Federal – CPF
 O número de CPF de uma pessoa, no Brasil, é constituído de 11
dígitos sendo um primeiro bloco com 9 algarismos e um segundo
com mais dois algarismos que são como no ISBN, dígitos de
controle ou de verificação. A determinação desses dois dígitos de
controle é mais um caso de aplicação da congruência.
 No caso do CPF, o décimo dígito (que é o primeiro dígito
verificador) é o resultado de uma congruência módulo 11 de um
número obtido por uma operação dos primeiros nove algarismos.
 Seja , ܽ଴, ܽଵ, ܽଶ, … , ܽଽ	a sequência formada pelos 9 dígitos.Vamos
multiplicá-los nessa ordem, pela base1,2,3,4,5,6,7,8,9
E somar os produtos obtidos.
 O dígito que está faltando representado por ܽଵ଴	 deve ser tal que
ao ser subtraído da soma obtida deve gerar um múltiplo de 11, ou
seja, se a soma obtida é ܵ, o número ܵ − ܽଵ଴	 deve ser múltiplo de11. Logo,
ܵ − ܽଵ଴ ≡ 0	(݉݋݀	11)
EXEMPLO: Se o CPF de uma pessoa tem os seguintes 9 primeiros
dígitos:
૛૜૞	 − ૜૝૜	 − ૚૙૝
O primeiro dígito de controle é obtido da seguinte forma:
EXEMPLO: Se o CPF de uma pessoa tem os seguintes 9 primeiros
dígitos:
૛૜૞	 − ૜૝૜	 − ૚૙૝
O primeiro dígito de controle é obtido da seguinte forma:
 Escrevemos os nove primeiros e abaixo deles a base de
multiplicação com os dígitos de 1 a 9.
Efetuando as operações correspondentes, obtemos:2 ∙ 1 + 3 ∙ 2 + 5 ∙ 3 + 3 ∙ 4 + 4 ∙ 5 + 3 ∙ 6 + 1 ∙ 7 + 0 ∙ 8 + 4 ∙ 9 = 116
2 3 5 3 4 3 1 0 4
1 2 3 4 5 6 7 8 9
 Assim, dividindo 116 por 11, obtemos:116 = 11 ∙ 10 + 6
Portanto, o primeiro dígito de controle é o algarismo 6.
 A determinação do segundo dígito de controle é feita de modo
similar, entretanto, acrescentamos o décimo dígito (o primeiro
dígito de controle) e usamos uma base de multiplicação de 0 a 9.
Logo, temos:
2 3 5 3 4 3 1 0 4 6
0 1 2 3 4 5 6 7 8 9
 Efetuando asmultiplicações, temos:2 ∙ 0 + 3 ∙ 1 + 5 ∙ 2 + 3 ∙ 3 + 4 ∙ 4 + 3 ∙ 5 + 1 ∙ 6 + 0 ∙ 7 + 4 ∙ 8 + 6 ∙ 9= 145
 Dividindo o número 145 por 11 obtemos:145 = 11 ∙ 13 + 2
 Logo o segundo dígito de controle é 2 . Portanto, o CPF da
pessoa é: 235	 − 343	 − 104	 − 62
 Se o resto da divisão fosse 10, ou seja, se o número obtido fosse
congruente ao 10 módulo 11, utilizamos neste caso, o dígito 0.
PROPOSTA DE ATIVIDADES:
(1) APLICAÇÕES DA ARITMÉTICA MODULAR NA
CRIPTOGRAFIA;
(2) CRIPTOGRAFIA E CALENDÁRIO: EM QUE DIA DA SEMANA
VOCÊ NASCEU ?
REFERÊNCIAS:
 BRASIL, RPM; Revista do Professor de Matemática. Volumes 12
e 45. Sociedade Brasileira de Matemática.
 BUCHMANN, J. Introdução à Criptografia. São Paulo: Berkeley,
2002.
 BURNETT, S. & PAINE, S. Criptografia e Segurança: o Guia
Oficial RSA. São Paulo: Campus, 2002.
 CRATO, N. Alice e Bob. Expresso / Revista, 22 de Setembro, pp.
118-120 (2001)