CONGUENCIA MODULO M E ARITMÉTICA MODULAR : CONCEITO S, RESULTADOS E APLICAÇOES

Viviane Azevedo Da Silva ¹

Clicia Valladares Peixoto Friedmann ²

Além da aritmética usual no conjunto dos numéros inteiros, podemos explorar uma ritmética

modular que envolve o conceito de congruência módulo m (m inteiro maior que 1) . As operações

de adição e multiplicação são definidas em um conjunto finito Zm cujos elementos são classes

residuais, sendo cada classe, um subconjunto de números inteiros que têm restos da divisão por m

sempre iguais a um determinado resto r. A congruência modulo m e aritmética modular têm muitas

aplicações. Dentre elas,a justificativa para critérios de divisibilidade, exemplificação de conceitos

que envolvem as propriedades das operações, construção de códigos e no estudo e modelagem de

fenômenos periódicos que envolvem diferentes campos do conhecimento como: matemática (teoria

dos jogos, teoria dos grafos), física, artes, música e etc..

Este trabalho está baseado numa parte das atividades que foram desenvolvidas num projeto de

Iniciação Científica que findou em agosto de 2011. O projeto foi sobre congruência modulo m, suas

propriedades, equações diofantinas lineares e aritmética modular. Neste texto, temos como objetivo

introduzir o conceito de congruência módulo m, a aritmética modular e exemplificar algumas

aplicações iniciais do conceito de congruência módulo m que foram pesquisadas pela bolsista de

Iniciação Científica.

CONGRUÊNCIA MÓDULO M

A congruência módulo m é uma relação de equivalência no conjunto dos números inteiros de tal

forma que dados dois inteiros a e b, a é congruente a b módulo m, onde m é um número inteiro

positivo, se e somente se, a diferença a - b for divisível por m. Usaremos a notação por a ≡ b (mod

m), se os números inteiros a e b são congruentes módulo m (m pertencente a Z, m >0).

São válidos os seguintes resultados:

Se a e b são inteiros, temos que a ≡ b (mod m) se, e somente se, existir um inteiro k tal que a-b =

km.

A congruência define uma relação de equivalência, pois atende às propriedades reflexiva, simétrica

e Transitiva.

Se a, b, c e m são inteiros, m>0, tais que a ≡ b (mod m), então

a + c ≡ b + c (mod m) 2) a – c ≡ b – c (mod m) 3) ac ≡ bc(mod m)

____________________ ¹ Discente do Curso de Matemática, UNIGRANRIO ² Docente da Escola de Educação, Ciências, Letras, Artes e Humanidades, UNIGRANRIO

Se a, b, c, d e m são inteiros, m>0 tais que a ≡ b(mod m) e c ≡ d(mod m), então

a + c ≡ b + d (mod m) 2) a – c ≡ b – d (mod m) 3) ac ≡ bd(mod m)

Temos que as propriedades 3.1 e 3.3 podem ser estendidas respectivamente para um número finito

de parcelas e de fatores.

ARITMÉTICA MODULAR

Neste texto, vamos considerar o conjunto Zm = { 0, 1, 2, . . , m-1}, sendo m um número inteiro

positivo e r pertencente a Zm uma classe residual, ou seja, r = { y pertencentes a Z : r ≡ y (mod

m)}. Podemos observar que a classe residual r é formada por todos os números inteiros cuja divisão

por m tem resto r. Definimos então as seguintes operações módulo m.

Para todo a e b pertencentes a Zm

a + b = r , se r é o resto da divisão de (a + b) por m, r ≡ (a+b) (mod m) (adição modular)

a x b = s, se s é o resto da divisão de (a x b) por m, s ≡ (axb) (mod m) (multiplicação modular)

Por exemplo, dado Z7 = { 0, 1, 2, . . , 7-1} = { 0, 1, 2, . . , 6} então, 3 + 5 = (3 + 5) = 1, pois 3+5 = 8

e o resto da divisão de 8 por 7 é 1 , logo 8 ≡ 1 (mod 7) e 4 . 5 = (4 . 5) = 6, pois 4x5 = 20 e o resto

da divisão de 20 por 7 é 6, logo 20 ≡ 6 ( mod 7)

As operaçoes acima estão bem definidas e independem do representantes das clasess. Na aritmética

modular, trabalhamos com o conceito de congruência módulo m. São válidas as seguintes

propriedades em relação às operações de adição e multiplicação modular:

Sejam a, b, c elementos quaisquer de Zm e m um número inteiro positivo então,

a + b e a x b pertencem a Zm (fechamento) 2 ) a + b = b+a e a x b = b x a (comutatividade)

(a + b) + c = a +( b + c) e (a x b) x c = a x( b x c) (associatividade)

a+ 0 = 0+a = a e ax1=1xa = a ( existência de elemento neutro, sendo 0 e 1 ,respectivamente, os

elementos neutros da adição e da multiplicação em Zm). No caso da multiplicação, a não pode ser

igual a 0.

ax( b+c) = axb+ axc ( distributividade)

a+ (m-a) = (m-a) + a = 0 ( sendo m- a o elemento simétrico aditivo de a em Zm)

Além das propriedades acima, podemos garantir que, um elemento de Zm terá simétrico

multiplicativo (inverso) se ele e m forem primos entre si e diferentes de 0. Nesse caso, dado a

pertencente a Zm tal que MDC(a, m) = 1 então existe b pertencente a Zm, tal que axb=1. Em Z6

,todos os elementos têm simétrico aditivo, o mesmo não acontece quanto aos simétricos

multiplicativos. Por exemplo, como o MDC( 2, 6) = 2, logo não existe y tal que 2 x y = 1. De fato,

2 x 0 =0 , 2 x 1 =2, 2x 2 =4, 2 x 3 =0, 2 x 4 =2, 2 x 5 =4.

APLICAÇÕES DE CONGRUÊNCIA MÓDULO M E ARITMÉTICA MODULAR

Usamos congruência modulo m e aritmética modular em diversas aplicações, tais como: critérios de

divisibilidade, códigos numéricos de identificação (códigos de barras, números dos documentos de

identidade, CPF, CNPJ, ISBN, criptografia e outros) e otimização de redes de computadores, entre

outros. A seguir, mostramos três exemplos dessas utilizações.

CRITÉRIO DE DIVISIBILIDADE POR 11

Seja n um número inteiro positivo de algarismos a0 a1 a2 a3 ... as. Como a base de nosso sistema

de numeração é 10, podemos escrever n= a0 a1 a2 a3 ... as da seguinte forma: a0 a1 a2 a3 ... as=

a0+ a110+ a2102+ a3103+. . . + as10s. Temos que 10 ≡ -1 (mod11) então 10 i ≡ 1 ( mod11) se i for

par, caso contrário, 10 i ≡ -1 ( mod11). Aplicando as propriedades de congruência módulo 11,

vemos que a0 ≡ a0 (mod 11), a2102≡ a2 (mod 11), . . ., a2k 102k≡ a2k (mod 11) e a1 10≡ - a1

(mod 11), a3 103≡ - a3 (mod 11), . . . ,a2k+1 102k+1≡ -a2k+1 (mod 11). Somando os termos pares

temos a0 + a2 + . . . + a2k ≡ a0 + a2102 + . . . + a2k 102k+. . . (mod 11) e os termos ímpares (-a1 -

a3 - . . . - a2k+1 )≡ a1 10+ a3103 + . . . + a2k+1 102k+1+. . . (mod 11), logo (a0 + a2 + . . . + a2k )–

(a1 + a3 + . . . + a2k+1 ) ≡ a0+ a110+ a2102+ a3103+. . . + as10s (mod11) Se n é divisível por 11

então n ≡ 0 ( mod 11), logo a0+ a110+ a2102+ a3103+. . . + as10s ≡ 0 ( mod 11) e portanto (a0 + a2

+ . . . + a2k )– (a1 + a3 + . . . + a2k+1 ) ≡ 0 ( mod 11), o que acarreta que (a0 + a2 + . . . + a2k ) ≡

(a1 + a3 + . . . + a2k+1 ( mod 11). Então n será divisível por 11 se e somente se (a0 + a2 + . . . + a2k

)– (a1 + a3 + . . . + a2k+1 ) também for.

CÓDIGOS

Um dos códigos de barras mais usados no mundo todo é o EAN-13, constituído de 13 algarismos

(dígitos). Os três primeiros dígitos do código representam o país de registro do produto; os quatro

dígitos seguintes identificam o fabricante; os próximos cinco identificam o produto e o último, é o

dígito de controle, que é calculado através da congruência, módulo 10, sendo que os fatores que

compõem a base de multiplicação são os dígitos 1 e 3, que vão se repetindo da esquerda para a

direita.

Se a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 é a seqüência formada pelos 12 primeiros dígitos,

devemos multiplicá-los, nessa ordem, por {1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3} e somar os produtos

obtidos. Vamos representar por S a soma obtida. O dígito que está faltando, representado por a13,

deve ser tal que ao ser somado com S, obtemos um múltiplo de 10, isto é, o número S + a13 deve

ser múltiplo de 10, ou seja, S + a13 ≡ 0 (mod 10).

Vejamos um exemplo: código de barras dado por: 0 12 3456 78900X ( X é o dígito de controle)

Cálculos para a determinação do dígito de controle

0 1 2 3 4 5 6 7 8 9 0 0

1 3 1 3 1 3 1 3 1 3 1 3

Efetuando os produtos, temos: 0 + 3 + 2 + 9 + 4 + 15 + 6 + 21 + 8 + 27 + 0 + 0 = 95

Dividindo 95 por 10, obtemos quociente 9 e resto 5. Logo, o dígito de controle X será igual a 5 (10

– 5). Podemos observar que 95 + 5 = 100 (múltiplo de 10).

REDE DE INTERCONEXÃO

Algumas das topologias usuais em redes de interconexão têm relação com figuras geométricas

conhecidas: ciclos (polígonos), grades, toro discreto e hipercubo. Os vértices representam

processadores e os lados ou arestas são as ligações entre processadores. Podemos usar congruência

módulo m para designar atividades conjuntamente, entre processadores e ligações sem gerar

conflitos e de forma equilibrada. Apresentamos um exemplo simples: funcionamento de uma rede

poligonal múltipla de 3, com n lados, n maior ou migual 3. Ao associarmos um mesmo número a

processadores e ligações, permitimos que eles sejam acionados ao mesmo tempo. Seja V= {v0, v2,

v3, . . , vn-1}o conjunto de vértices de Cn e E= {l0, l2, l3, . . , ln-1} seus lados (ligações). Como n

é múltiplo de 3 então n= 3k, k maior ou igual a 1. Construímos a função c: VUE {0, 1, 2} tal que

c(vi) = i ( mod3) e c(li) = i+2 (mod3) e otimizamos a situação.

Podemos observar que os exemplos acima servem como elementos motivadores para aprendermos

congruência modulo m e verificarmos o uso da aritmética modular, sendo que o ultimo exemplo

dado não é usualmente explorado nos livros textos que tratam do assunto. .

REFERÊNCIAS BIBLIOGRÁFICAS

COUTINHO, S. C. Números inteiros e criptografia RSA. Rio de Janeiro: IMPA, 2005.

DOMINGUES H., IEZZI G. Álgebra Moderna. São Paulo: Atual Editora, 1982.

LOZANO, FRIEDMANN, JURKIEWICZ , Coloração total equilibrada de grafos – Um modelo

para redes de interconexão. Pesqui. Oper. vol.28 no.1 Rio de Janeiro Jan./Apr. 2008

HEFEZ, Abramo. Elementos de Aritmética. Rio de Janeiro: Sociedade Brasileira de

Matemática, 2005.

SANTOS, José Plínio de Oliveira. Introdução à Teoria dos números. Rio de Janeiro: IMPA, 2010.

PEREIRA DE SÁ, I. A aritmética modular e suas aplicações no cotidiano.

Disponível em : <www.magiadamatematica.com> Acesso em: 25 Fev. 2011