Aritmética modular

Um problema de periodicidade

Frequentemente sempre estamos nos deparando com eventos periódicos, ou seja, fatos que ocorrem com repetidas vezes em um determinado intervalo de tempo. A terra demora 365 dias e 4 horas para dar um voltar completa em torno do sol, e 24 horas para completar uma volta em torno de si, a Lua demora 27 dias para dar uma volta em torno da Terra e 27 dias para rotacionar em torno de si mesma (já reparou que a Lua tem apenas uma face voltada para a Terra?), a cada 7 dias repetimos o dia da semana que estamos.

Alguns eventos periódicos entretanto são criados pelo homem para organizar suas tarefas, o calendário escolar é uma delas que distribui discretamente os horários de aula durante os dias da semana. Assim, dado um determinaro dia, você pode saber ou não se terá aula de matemática.

Suponha que hoje é dia 3 de julho de 2009, uma sexta-feira e você queira saber se dia 11 de outubro terá aula de matemática, porem, não dispões de um calendário.

Como julho tem 31 dias, até o final do mês se passará 31-3=28 dias, para chegar ao final de agosto, que tem mais 31 dias, levaremos 28+31=59 dias, para chegar ao final de setembro somamos os 30 dias do mês, temos 59+30=89 dias. Para o dia 11 de outubro faltam somar mais 11 dias, ou seja, do dia 3 de julho a 11 de outubro se passarão 100 dias.

Sabemos que o calendário se repete de 7 em sete dias, assim, a cada 7 dias voltamos a cair numa sexta-feira. Isso significa que em 100 dias vamos passa exatamente o quociente da divisão 100:7 vezes pela sexta-feira, precisamos saber quantos dias sobram.

100=98+2=7x14+2

Dessa forma, após 98 dias estaremos numa sexta-feira novamente, e após mais 2 dias, chegamos ao domingo. E com certeza você não terá aula no domingo do dia 11 de outubro de 2009.

A aritmética modular

Repare que o que nos importou mas para resolver este problema do calendário escolar não foi toda a divisão mas apenas o resto dela, pododeriamos ter simplificados nossas contas se conhececemos as aritmética modular.

Por definição, dizemos que doi números a e b são comgruêntem módulo n se o resto da divisão de a por n é igual ao resto da divisão de b por n, podemos escrever matemáticamente isso como.

a=k₁n+r

b=k₂n+r

com 0≤r≤n-1

E escrevemos

a≡b(mod n)

Uma equivalência a essa definição é dizer que o número a-b é multiplo de n. De fato:

a-b=(k₁n+r)-(k₂n+r)=(k₁-k₂)n

Usando o exemplo do problema que resolvemos.

100≡2(mod 7)

A aritmética modular goza das mesmas propriedades da iguadade, para quaisquer a, b, c e n número inteiros, sempre se tem.

Propriedade reflexiava:

a≡a(mod n)

pois a-a=0n

Propriedade simétrica:

Se a≡b(mod n), então b≡a(mod n)

que é verificado pela definição

Propriedade transitiva:

Se a≡b(mod n) e b≡c(mod n), então a≡c(mod n)

Temos que:

a-b=k₁n (1)

b-c=k₂n (2)

Fazendo (1)-(2) temos

a-c=(k₁-k₂)n

Propriedades da soma, multiplicação e potênciação

As propriedades relacionadas a soma multiplicação e potenciação são:

P1: Se a≡r₁(mod n) e b≡r₂(mod n). então

a+b≡r₁+r₂(mod n)

Demons: Temos que

a-r₁=k₁n (1)

b-r₂=k₂n (2)

Somando (1) com (2) temos que:

(a+b)-(r₁+r₂)=(k₁+k₂)n

P2:Se a≡r₁(mod n) e b≡r₂(mod n). então

ab≡r₁r₂(mod n)

Demons: Escrevendo as congruências em forma de divisão temos que:

a=k₁n+r₁(1)

b=k₂n+r₂(2)

E multiplicando (1) com (2) temos:

ab= (k₁n+r₁ )(k₂n+r₂)

ab=(k₁k₂n+k₁r₂+k₂r₁)n+r₁r₂

P3: Se a≡b(mod n) e k é um inteiro positivo, então a^k≡b^k(mod n)

Demons: Vamos demonstrar por indução em k. Pela hipótese, para k=1 a propriedade é válida, digamos que para algum k inteiro positívo vale a propriedade a^k≡b^k(mod n). Usando a propriedade P2 da multiplicação temo que também é válido:

aa^k≡bb^k(mod n),

ou seja.

a^k+1≡b^k+1(mod n)

Logo, pelo princípio da indução matemática, a propriedade P3 é valida para qualquer que seja k inteiro positivo

Resolvendo um problema usando Aritmética modular.

Problema 1: Vamos resolver o problema que fizemos no exemplo: Se hoje é dia 3 de julho, faltam 31-3 dias para o fim do mês, mais 31 dias do mês de agosto, 30 de setembro e 11 para chegar ao dia 11 de outubro, em congruência, montamos a equação:

31-3+31+30+11≡ x(mod 7)

28+31+30+11≡ x(mod 7)

Usando a propriedade P1, vamos encontrar o menor valor de x que satisfaça a equação. temos assim:

28≡0(mod 7)

31≡3(mod 7)

30≡2(mod 7)

11≡-3(mod 7)

Repare que não nos restringimos aos número possitivos, como a definição de congruência comtempla todos os inteiros podemos tem a ultima congruência com tranquilidade. De fato:

11-(-3)=11+3=14=7x2

Usando a propriedade P1 temos que

28+31+30+11≡ x(mod 7)

0+3+2-3≡ x(mod 7)

2≡ x(mod 7)

Basta agora interpretar o resultado, se estamos na sexta-feira, e chegar ao 11 de outubro equivale a mais dois dias da semana, então 11 de outrubro cai em um domingo.

Problema 2: Qual o resto da divisão de 2⁷³⁴⁸ por 31?

Sem a aritmética modular esse problema nos daria uma boa dor de cabeça, mas com a nova teoria que conhecemos fica fácil resolve-lo.

Vamos calcular as primeiras potências de 2 módulo 31, temos:

2≡2(mod 31)

2²=4≡4(mod 31)

2³=8≡8(mod 31)

2⁴=16≡16(mod 31)

2⁵=32≡1(mod 31)

Não precisamos ir além disso, se a 5ª potência de 2 (que é 32) módulo 31 é 1, qualquer potência de 32 também será igual a 1 módulo 31, isso por causa de P3. Assim, escrevendo 7348=5x1469+3 temos que.

2⁷³⁴⁸≡2^5x1469+3(mod 31)

2⁷³⁴⁸≡(2⁵)¹⁴⁶⁹x2³(mod 31)

2⁷³⁴⁸≡1¹⁴⁶⁹x8(mod 31)

2⁷³⁴⁸≡8(mod 31)

O resto da divisão de 2⁷³⁴⁸ por 31 é 8.