Teoria dos números - congruências (1)

Dando uma continuação ao meu post introdutório sobre teoria dos números, adoto aqui uma abordagem prática de alguns tópicos interessantes sobre congruências. Não sei quanto a você, mas uma dificuldade que enfrento é encontrar materiais de estudo que atendam aos seguintes requisitos: a) abordem temas relevantes e possíveis de serem compreendidos por estudantes de ensino médio, b) deem explicações claras e c) mostrem como aplicar os conhecimentos.

Então vou tentar usar minha experiência de frustrações e ver se consigo transformá-la em algo bom ;P

Pré-requisitos

Nesta mini-aula eu não quero simplesmente jogar teoremas e conceitos: é tudo sobre resolução de problemas. Desta vez são congruências, mas poderia ser combinatória, equações diofantinas, geometria, não importa. Se você não curte ou talvez não seja tão bom assim, há um e somente um remédio: treinar — e divertir-se ao fazê-lo, claro. Alguns links legais:

10 questões de raciocínio lógico + respostas
Desafios Só Matemática
Jogos de DS para amantes de enigmas
Jogos matemáticos online
Queimando alguns neurônios

Por que algo tão besta como resolver desafios e problemas de lógica ou matemática simples é importante? Ora, do contrário as olimpíadas perderiam todo o sentido. Você não vai magicamente desenvolver essa habilidade lendo o post, mas pode obter ferramentas úteis para ajudá-lo. Com isso esclarecido, vamos a um conceito preliminar importante:

• Divisibilidade: Dizemos que a divide b, representado por a|b, se b = ac para algum inteiro c. Ou seja: a é um divisor de b e b é um múltiplo de a. Note que 3|12 pois 12 = 3 * 4, mas 12∤3 (12 não divide 3), pois não existe nenhum c tal que 3 = 12 * c.

Introdução

Toda nossa exploração será em cima da seguinte definição:

• Definição 1 - Se a deixa resto x na divisão por b, então a ≡ x (mod b). Dizemos que a é congruente a x módulo b. Por exemplo, 3 ≡ 1 (mod 2) e 15 ≡ 0 (mod 3).

Sempre que lidamos com essa "matemática dos restos" que costuma aparecer em situações periódicas — que se repetem seguindo um padrão —, estamos falando de aritmética modular, que usa as congruências como fundamentos cruciais. Mas aqui vamos além e aprenderemos alguns modos muito engenhosos de resolver vários problemas pelas congruências:

-> Alguns dos tais problemas com dígitos. Em particular, como determinar o último ou os últimos dígitos de um número?

-> É possível determinar o resto da divisão de um número muito grande, como \(2^{2011}\), por um inteiro n, sem precisar calculá-lo?

-> Como podemos saber se um inteiro n é múltiplo de um inteiro m? E mais ainda: é possível mostrar que qualquer número da forma... digamos, \(2^n + n\) é sempre divisível por outro?

-> Também podemos usar congruências para auxiliar na resolução das equações diofantinas, que admitem apenas inteiros como soluções. Mas não vou cobrir esta aplicação no momento.

Classes de congruência

Antes de entrar nas aplicações diretas, vamos conhecer um pouco sobre as classes de congruência. Considere o número 2, bonitão, parado no canto dele.

Fonte.

Se de repente surgir um número n qualquer e quiser ser dividido por 2, mesmo não sabendo quem ele é, temos certeza absoluta de que há apenas 2 possibilidades:

Ou n é divisível por 2, ou seja, n ≡ 0 (mod 2);
Ou n não é divisível por 2, ou seja, n ≡ 1 (mod 2).

Então podemos colocá-los em 2 filas: os pares, que deixam resto 0, e os ímpares, que deixam resto 1. O mesmo acontece com, digamos, 3, mas neste caso há 3 possibilidades de resto: 0, 1 e 2. Essas tais filas ou classificações correspondem justamente às classes de congruência módulo n. Mais claramente:

• Definição 2 - Um inteiro n possui um conjunto S de elementos tal que S = {\(\overline{0}, \overline{1}, ..., \overline{n-1}\)}. Cada um desses elementos é chamado classe de congruência módulo n.

• Definição 3 - Um inteiro a está contido na classe de congruência \(\overline{m}\) módulo n se a ≡ m (mod n). Ou seja: todo número na classe de congruência \(\overline{m}\) deixa resto m na divisão inteira por a.

Muito abstrato? Sem problemas, daqui a pouco você pega o jeito. Consideremos o caso no qual escolhemos 3 como módulo. Temos as seguintes classes de congruência:

\(\overline{0}\) = {..., -6, -3, 0, 3, 6, ...}
\(\overline{1}\) = {..., -5, -2, 1, 4, 7, ...}
\(\overline{2}\) = {..., -4, -1, 2, 5, 8, ...}

Assim, 11 claramente está na classe \(\overline{2}\) de congruência, pois 11 ≡ 2 (mod 3), já que 11 = 3 * 3 + 2. Antes de encerrar, quero deixar algumas propriedades que serão úteis, mas não vou demonstrá-las:

• Propriedade 1 - Se i ∈ \(\overline{a}\) módulo n e j ∈ \(\overline{b}\) módulo n, então i + j = \(\overline{a + b}\). Por exemplo, \(\overline{12} + \overline{3} = \overline{15}\), desde que 12 e 3 sejam classes de congruência de um mesmo inteiro.

• Propriedade 2 - Se i ∈ \(\overline{a}\) módulo n e j ∈ \(\overline{b}\) módulo n, então i - j = \(\overline{a - b}\). Por exemplo, \(\overline{12} - \overline{3} = \overline{9}\), desde que 12 e 3 sejam classes de congruência de um mesmo inteiro.

• Propriedade 3 - Se i ∈ \(\overline{a}\) módulo n e j ∈ \(\overline{b}\) módulo n, então \(i \times j = \overline{ab}\). Por exemplo, \(\overline{12} \times \overline{3} = \overline{36}\), desde que 12 e 3 sejam classes de congruência de um mesmo inteiro.

Infelizmente por enquanto não há muito o que fazer, mas fica aqui um estimulante para o próximo post, quando as coisas começam a ficar mais interessantes:

-> Determine o resto de \(2^{34}\) por 33. Ou seja: a qual classe de congruência módulo 33 essa potência de 2 pertence? Dica: encontre uma potência próxima de 33, descubra sua classe de congruência e use as propriedades acima.

Ué, acabou?

Calma, foi só mesmo para dar um gostinho da coisa. Confira a sequência aqui.

Fontes

Contest Number Theory
Imersão Olímpica - Introdução à Teoria dos Números
Number Theory