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

GPG por mbernet (CC BY-NC-SA 2.0).

Para você que leu até o final a primeira parte da mini-aula sobre congruências, alegre-se! Enfim vamos pôr em prática os conceitos, junto com algumas artimanhas desenvolvidas ao longo do tempo, para resolver alguns problemas que havia comentado. Você que caiu de paraquedas também pode aproveitar o post, desde que tenha noções básicas de aritmética modular.

Resto da divisão e alguns artifícios

Recorde-se do problema apresentado no primeiro post.

• Problema 1 - Determine o resto de \(2^{34}\) por 33.

Logo percebemos que precisamos descobrir a classe de congruência módulo 33 à qual essa potência de 2 pertence, mas de preferência sem calculá-la. Como sabemos que a operação de multiplicação é válida quando tratamos de classes de congruência, basta acharmos uma potência conveniente e ir fazendo as contas. Na prática deve ficar mais claro.

Vamos escolher uma potência próxima, como \(2^5 = 32\). Claro, 32 deixa resto 32 na divisão por 33, mas não podemos dizer também que 32 pertence à mesma classe de congruência que -1? Veja:

32 = 33 * 0 + 32
-1 = 33 * -1 + 32

Sendo o resto idêntico, conclui-se que \(\overline{32} = \overline{-1}\). Esse "truque do complementar" é muito útil para simplificar os cálculos. Usando esse fato, e lembrando que \(2^{34} = (2^5)^6 \times 2^4\), podemos concluir:

$$ \overline{2^{34}} = (\overline{32})^6 \times (\overline{2})^4 = (\overline{-1})^6 \times \overline{16} = \overline{16} $$

Ou seja, esse troço aí deixa resto 16 na divisão por 33. Não confia em mim? Então tire a prova com a entidade suprema do conhecimento: Wolfram Alpha.

Problemas com dígitos

Outra coisa que pode ser reduzida a encontrar a classe de congruência à qual pertence um número são alguns dos tais problemas com dígitos. Vamos escolher um simples:

• Problema 2 - Determine o dígito das unidades de \(3^{34}\)

Que equivale a descobrir o resto da divisão desse número por 10. Você pode comprovar com alguns exemplos: 124 mod 10 = 4, 1000 mod 10 = 0, 567819038912 mod 10 = 2. Mas para remover qualquer sombra de dúvida, vamos analisar o caso geral, considerando um número a na base decimal. Como sabemos, ele pode ser decomposto da seguinte forma:

$$ a = 10^{n - 1} a_{n - 1} + 10^{n - 2} a_{n - 2} + ... + a_0 $$

Onde cada "a índice alguma coisa" é um de seus dígitos e a índice zero é o dígito das unidades. Vamos reescrevê-lo isolando o 10:

$$ a = 10(10^{n - 2} a_{n - 1} + 10^{n - 3} a_{n - 2} + ... + a_1) + a_0 $$

Opa, isso é interessante. Quer dizer que se dividirmos esse número por 10, fica claro que só sobra o a índice zero, que não está multiplicado por uma potência de 10. Ok, agora vamos fazer as continhas, tomando 3² = 9 como ponto inicial. Pelo "truque do complementar" e os artifícios anteriores:

$$ \overline{3^{34}} = (\overline{3^2})^{17} = (\overline{-1})^{17} = \overline{-1} = \overline{9} $$

Portanto, 9 é nossa resposta. Raciocínios semelhantes podem ser utilizados se quisermos descobrir os últimos dígitos ou apenas o antepenúltimo, sei lá, as possibilidades são infinitas. Vá brincar com seus novos super-poderes agora.

Divisibilidade

• Problema 3 - Considere o inteiro n = x³ + 2x² + 3x + 4. Mostre que n é sempre par.

Ou seja, para todo x, n|2, o que significa que n pertence à classe de congruência \(\overline{0}\) módulo 2. O método mais comum é substituir x por um número da forma 2a — par — e 2a + 1 — ímpar — e verificar "na mão" que é verídico. Embora haja uma maneira de fazê-lo sem precisar explicitamente elevar o negócio ao quadrado, depois ao cubo, então multiplicar e somar com sei lá o quê (tente!), as congruências estão aí para tornar nosso trabalho bem mais fácil:

$$ \begin{alignat}{4}
\overline{x^3 + 2x^2 + 3x + 4} & = \\
& = (\overline{x})^3 + \overline{2} (\overline{x})^2 + \overline{3} \overline{x} + \overline{4} = \\
& = (\overline{x})^3 + \overline{0} (\overline{x})^2 + \overline{1} \overline{x} + \overline{0} = \\
& = (\overline{x})^3 + \overline{x} \\
\end{alignat} $$

Mas há um número finito de possibilidades para \(\overline{x}\), considerando o módulo 2. Afinal, um número deixa apenas resto 0 ou 1 na divisão por 2, então só precisamos substituir esses valores:

Para x = 0: $$ (\overline{0})^3 + \overline{0} = \overline{0} $$

Para x = 1: $$ (\overline{1})^3 + \overline{1} = \overline{2} = \overline{0} $$

Portanto, n é par independente do valor de x.

A função de Euler e o teorema de Euler-Fermat

A esta altura você já deve ter percebido que, em cálculos envolvendo classes de congruência, o mais prático é encontrar um valor congruente a 1 ou -1. Mas até chegar lá, não tem jeito, é questão de tentativa e erro... Ou será que tem? Pode apostar que sim! Antes de tudo, precisamos definir a função de Euler:

• Definição 4 - A função de Euler, φ(n), determina o número de inteiros menores que n e relativamente primos/coprimos com ele. Assim, como 5 é relativamente primo com 1, 2, 3 e 4, φ(5) = 4. Similarmente, φ(2) = 1, φ(10) = 4 etc.

Opa, isso é legal, mas... há um modo de calcular esse valor?

• Teorema 1 - Para todo inteiro n, tal que sua decomposição em fatores primos seja \( n = p_1^{e_1} p_2^{e_2} ... p_n^{e_n} \), \( \phi (n) = n(\frac{1}{p_1})(\frac{1}{p_2})...(\frac{1}{p_n}) \), onde cada p representa um fator primo de n.

Não vou demonstrá-lo aqui, mas você pode conferir nas fontes abaixo — o que aliás recomendo. Também não vou detalhar por que a "fórmula mágica abaixo" funciona:

• Teorema 2 - Dados dois inteiros a e m, se (a, m) = 1, ou seja, se a e m forem primos entre si, então \( a^{\phi (m)} \equiv 1 \pmod{m} \)

Viva, agora boa parte de nossas dores de cabeça estão resolvidas! Claro, é importante lembrar que a e m devem ser primos entre si.

Mais problemas

• Problema 1 - Sejam x e y inteiros tal que 2x + 3y é um múltiplo de 17. Mostre que 9x + 5y deve também ser um múltiplo de 17.

• Problema 2 - Mostre que, para todo n natural, \( n^5 - n\) é um múltiplo de 10.

• Problema 3 - Mostre que, para todos k, m, n naturais, \( 5^{5k + 1} + 4^{5m + 2} + 3^{5n} \) é um múltiplo de 11.

• Problema 4 - Encontre o dígito das unidades de \( 4^{4^{4^4}} \).

• Problema 5 - Encontre os últimos 3 dígitos de \(9^{105}\).

• Problema 6 - Encontre o menor inteiro positivo tal que, quando o primeiro dígito é removido, o inteiro resultante é \(\frac{1}{29}\) do valor original.

• Problema 7 - A sequência de Fibonacci é tal que, a partir dos dois primeiros termos 0 e 1, F(n) = F(n - 1) + F(n - 2). Ou seja: para todo n > 1, o n-ésimo termo é a soma dos dois termos anteriores. Assim, uma amostra da sequência seria {0, 1, (0 + 1) 1, (1 + 1) 2, (2 + 1) 3, (3 + 2) 5}. Mostre que um dos primeiros \( 10^8 + 1 \) termos da sequência termina em 4 zeros (dica: utilize módulo \(10^4\)).

• Problema 8 - Para qualquer inteiro positivo n, n! (lê-se "n fatorial") é definido como sendo o produto dos inteiros de 1 até n. Por exemplo, 4! = 4 * 3 * 2 * 1 = 24. Mostre que 20! termina em 4 zeros. 

Fontes

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