ARITMÉTICA MODULAR E ALGUMAS DE SUAS APLICAÇÕES - 01

Uma das ferramentas mais importantes na teoria dos números é a aritmética modular, que envolve o conceito de congruência. Uma congruência é a relação entre dois números que, divididos por um terceiro - chamado módulo de congruência - deixam o mesmo resto. Por exemplo, o número 9 é congruente ao número 2, módulo 7, pois ambos deixam resto 2, ao serem divididos por 7. Representamos essa congruência do exemplo por 9 ≡ 2, mod. 7. Foi o brilhante Gauss que observou que usávamos com muita freqüência frases do tipo “a dá o mesmo resto que b quando divididos por m” e que essa relação tinha um comportamento semelhante à igualdade. Foi Gauss então que introduziu uma notação específica para este fato e que denominou de “congruência”.

Muito se tem escrito sobre esse tema, principalmente nos livros sobre teoria dos números. É um conceito muito importante e que está relacionado com divisibilidade e os restos de uma divisão de números inteiros.

O que não é muito comum é o estudo das muitas aplicações que o tema possui no cotidiano de todas as pessoas. Diferentes códigos numéricos de identificação, como códigos de barras, números dos documentos de identidade, CPF, CNPJ, ISBN, ISSN, criptografia, calendários e diversos fenômenos periódicos estão diretamente ligados ao tema, conforme mostraremos em nosso estudo.

É um tema bastante atual e que pode ser trabalhado já nas classes do Ensino Fundamental e gerador de excelentes oportunidades de contextualização no processo de ensino / aprendizagem de matemática.

Inicialmente vamos mostrar alguns elementos teóricos sobre a aritmética modular e, na segunda parte do trabalho teremos a apresentação de alguns exemplos de aplicação desse importante e interessante tema da área de teoria dos números.

1) Noções básicas da aritmética modular

1.1) Exemplos iniciais:

Antes de apresentarmos as definições e propriedades relacionadas à congruência, vamos desenvolver três exemplos que poderiam ser colocados a alunos da Educação Básica, ainda não familiarizados com o tema, como introdução ao assunto.

Exemplo 1:

Vamos apresentar uma questão retirada do banco de questões do site da OBMEP (Olimpíada Brasileira de Matemática das Escolas Públicas). Lá sempre temos encontrado questões interessantes e provocativas para o preparo de nossos alunos da Educação Básica.

A, B, C, D, E, F, G e H são os fios de apoio que uma aranha usa para construir sua teia, conforme mostra a figura. A aranha continua seu trabalho. Sobre qual fio de apoio estará o número 118?

1 Ilydio Pereira de Sá – Mestre em Educação Matemática, professor da UERJ, da Universidade Severino Sombra e do

Colégio Pedro I, Rio de Janeiro.

Aritmética modular e algumas de suas aplicações – Ilydio P. de Sá 2

SOLUÇÃO: Vejamos o que está acontecendo?

É claro que alguma pessoa bem paciente poderia continuar construindo a tabela até que aparecesse o número 118. Assim ela saberia em qual fio a aranha iria estar. Convenhamos que não seria uma solução muito prática e nem rápida. Imagine se a questão perguntasse o fio correspondente ao número 890?

Podemos observar que os fios se repetem a cada oito números e essa periodicidade faz com que os números de cada fio formem uma progressão aritmética de razão igual a 8, ou seja, aumentem de oito em oito. Observamos também que cada fio pode ser representado a partir dos múltiplos de 8. O fio A corresponde aos números que são múltiplos de 8, ou seja, números que divididos por 8 deixam resto zero (8. n, com n ∈ IN). O fio B corresponde aos números que são múltiplos de 8, mais 1, ou seja, números que divididos por 8 deixam resto 1 (8.n + 1, com n ∈ IN). O fio C corresponde aos números que são múltiplos de 8, mais 2, ou seja, números que divididos por 8 deixam resto 2 (8.n + 2, com n ∈ IN) e essa lógica se mantém até o fio H, definido pelos números que divididos por oito deixam resto 7. É claro que para saber sobre qual fio estará o número 118, basta verificarmos a qual dessas famílias tal número pertence e isso pode ser facilmente obtido ao dividirmos 118 por 8. Vejamos:

118	8
6	14

Todos os números de nosso exemplo, que estão no mesmo fio, tem uma particularidade em comum, deixam o mesmo resto ao serem divididos por 8 e, como já comentamos na introdução, são congruentes entre si, no módulo 8. O número 14, por exemplo, é congruente ao número 2, no módulo 8, e isso significa que esses dois números deixam o mesmo resto quando divididos por 8 (verifique que ambos estão sobre o fio G). Verificando:

Verificamos que o número 118 é igual a 8 . 14 + 6, ou seja, pertence à família dos números que estão no fio G.

14	8 2 8
6	1 6 2

Aritmética modular e algumas de suas aplicações – Ilydio P. de Sá 3

Simbolicamente, poderemos escrever: 14 ≡≡≡≡ 2, mod. 6 Exemplo 2: Aritmética do relógio

horas é congruente a 5 horas, módulo 12. Tanto 17, como 5, divididos por 12, deixam resto 5

Trata-se de um caso de congruência, módulo 12 (nos relógios analógicos, é claro). Note que 13 horas é congruente a 1 hora, no módulo 12. Ambos divididos por 12, deixam resto 1. 17 e assim, sucessivamente.

1 ≡ 13 ≡ 25 ≡	, mod 12
5 ≡ 17 ≡ 29 ≡	, mod 12

Assim as horas marcadas num relógio analógico constituem também um caso clássico de congruência, nesse caso com módulo 12.

Exemplo 3: Vejamos uma aplicação interessante sobre o tema, relacionada aos calendários:

Vamos supor que você saiba em qual dia da semana caiu o dia 1º de janeiro de um determinado ano. Em 2006, por exemplo, foi um domingo. Imaginemos que você deseja saber quando cairá um outro dia qualquer (vale para qualquer ano). É só montar uma tabela para essa primeira semana, que no caso será:

Verificamos aqui que estamos novamente diante de um caso de congruência, módulo 7 nesse caso. Digamos que estivéssemos interessados em descobrir em que dia da semana caiu o dia 5 de julho (e não temos um calendário em mãos, é claro). Primeiro precisamos ver quantos dias existem de 1 de janeiro até 5 de julho. Vejamos:

Janeiro	= 31 dias
Fevereiro =	28 dias (2006 não é bissexto)
Março	= 31 dias
Abril	= 30 dias
Maio	= 31 dias
Junho	= 30 dias
Julho	= 5 dias
Total	= 186 dias.

Agora, é como se tivéssemos uma fila de 186 dias e estamos desejando saber, na congruência de módulo 7 (7 dias da semana) qual o correspondente ao186. Acho que você concorda que estamos

Aritmética modular e algumas de suas aplicações – Ilydio P. de Sá 4 diante de uma situação bem semelhante à que vimos no problema da aranha e também no problema dos relógios analógicos.

186	7
4	26

Se dividirmos 186 por 7, teremos:

Logo, o 186 é congruente ao 4, no módulo 7. Como o dia 4 de janeiro de 2006 foi uma quartafeira, o 186º desse mesmo ano também o será e, é claro, que todas as demais quarta-feiras deste ano serão ocupados por números congruentes ao 4, módulo 7.

Assim, com os três exemplos que mostramos, podemos observar que em nosso cotidiano existem inúmeras situações onde se faz presente a noção de congruência, módulo k. Calendários, relógios analógicos e problemas em geral envolvendo repetições periódicas. Mostraremos em nosso estudo que na criptografia e em diversos números de documentos de identificação (como no CPF, por exemplo), também está presente a Aritmética Modular e a noção de congruência.

1.2) Conceitos Básicos da Congruência módulo k

Se os inteiros a e b dão o mesmo resto quando divididos pelo inteiro k (k > 0) então podemos dizer que a e b são côngruos, módulo k e podemos representar:

a ≡ b mod k

Uma maneira equivalente de dizer isso é afirmar que a diferença (a – b) ou (b – a) é divisível por k, ou que k é divisor dessa diferença. Veja um exemplo:

A congruência define uma equivalência, pois atende às propriedades reflexiva, simétrica e transitiva, ou seja:

a ≡ a, mod k (reflexiva) a ≡ b, mod k, então b ≡ a, mod k (simétrica) a ≡ b, mod k e b ≡ c, mod k, então a ≡ c, mod k (transitiva)

Algumas propriedades da congruência Se a ≡ b, mod k e c ≡ d, mod k, então: a + c ≡ b + d, mod k; a - c ≡ b - d, mod k; a . c ≡ b . d, mod k

É claro que todas essas propriedades precisam ser demonstradas. Vejamos a demonstração da primeira.

é divisível por k, para provarmos que a + c ≡ b + d, teremos que mostrar que

(a + c) – (b + d) é

Se a ≡ b, mod k, então a – b é divisível por k, analogamente, se c ≡ d, mod k, então c – d também divisível por k. Vamos colocar essa diferença na forma (a – b) + (c – d) e verificar se é divisível por k. Como, pela hipótese, (a – b) e (c – d) eram divisíveis por k, é claro que a soma (a – b) + (c – d) é também divisível por k, o que demonstra a primeira propriedade. Tente fazer as demais demonstrações, de modo análogo.

Aritmética modular e algumas de suas aplicações – Ilydio P. de Sá 5 2) Algumas aplicações da congruência

2.1) Sistemas de identificação

Em qualquer texto, um erro de ortografia numa palavra pode ser facilmente percebido, pois ou a palavra não faz parte do idioma ou não faz sentido com o contexto. Por exemplo, se digitamos engenheior, logo percebemos que fizemos uma inversão das duas últimas letras. Mas, quando isso ocorre com os algarismos de um número, de um código de identificação qualquer, não teríamos como perceber a troca num simples olhar. Para isso e também para minimizar fraudes, foram criados os chamados dígitos de controle ou verificação. Tais dígitos são normalmente baseados na noção de congruência que mostramos anteriormente.

Mostraremos a seguir alguns desses casos de dígitos de controle usados como identificadores. 2.1.1) ISBN

Um dos exemplos mais antigos é o sistema International Standard Book Number (ISBN) de catalogação de livros, CD-Roms e publicações em braile, que foi criado em 1969. A necessidade que as editoras têm de catalogar os seus livros e informatizar o sistema de encomendas serviu de motivação na geração desse código.

A vantagem é que, por ser um código numérico, ultrapassa as dificuldades geradas pelos diversos idiomas do mundo, bem como a grande diversidade de alfabetos existentes. Dessa forma, poderíamos, por exemplo, identificar através do ISBN um livro japonês.

Em tal 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. Esses nove primeiros dígitos são sempre subdivididos em 3 partes, de tamanho variável, separadas por hífen, que transmitem informações sobre o país, editora e sobre o livro em questão.

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 identifica, dessa forma, restam ainda 6 algarismos para a identificação de suas publicações, havendo pois a possibilidade de 10 6 = 1 0 0 de títulos.