Mencionei em um post anterior sobre as olimpíadas que o foco das competições de matemática são justamente os assuntos menos abordados no currículo tradicional, e ao mesmo tempo mais interessantes e desafiadores aos alunos. Um deles é a teoria dos números, que trata de... bem, números, como devem ter adivinhado.
Mas por que diabos alguém se interessaria em estudar apenas representações abstratas? O que os números pura e simplesmente têm de mais? Que tipo de problemas podemos resolver com esse ramo da matemática? Essas e outras perguntas serão respondidas neste post, juntamente com uma breve introdução aos principais assuntos estudados. Quem se interessar pode ter mais informações nas fontes abaixo.
O que é teoria dos números e o que ela estuda?
A teoria dos números é a parte da matemática, mais especificamente matemática discreta, que lida com os números e as relações entre eles, bem como suas propriedades. A seguinte citação de Gauss reflete bem o que ela representa: "A Matemática é a rainha das ciências, e a Teoria dos Números é a rainha da Matemática".
Durante bastante tempo a teoria dos números ficou conhecida como a parte mais pura da matemática e limitada a ser apenas "um lindo ramo do estudo", sem utilidade real. Veremos que não é bem assim, mas de fato trata-se de um tópico muito interessante que oferece respostas a uma variedade de perguntas, mesmo que de imediato sem valor prático.
O principal diferencial é que, ao contrário de muitos outros ramos, problemas relacionado à teoria dos números dificilmente podem ser resolvidos com um procedimento geral e absoluto e/ou por fórmulas quaisquer. Em uma equação de 2º grau, por exemplo, raramente será necessário algo a mais além de aplicar o método de Bhaskara.
Para que serve?
Várias pesquisas são voltadas à aplicação na criptografia, pois esta se utiliza dos números primos devido a 2 propriedades interessantes: facilidade de encontrar números primos grandes e dificuldade de fatorar números em produto de primos. Esta página, por exemplo, lista os 10.000 primeiros números primos, obtidos por um algoritmo eficiente. Veremos em breve o que os números primos têm de tão importante.
Divisão, aritmética modular e congruência
A divisão é um processo tão rotineiro que nem percebemos como seus fundamentos nos auxiliam em uma variedade de problemas. Por exemplo, suponha que você tenha 11 maçãs para repartir entre 4 pessoas, mas não tem nenhum instrumento cortante para fracionar cada uma delas e dividir igualmente. Em outras palavras, nosso problema consiste em formar 11 a partir de 4. Assim:
11 = 4 * 2 + 3
O que fizemos foi dar duas maçãs a cada pessoa e guardar 3, o resto da divisão. Assim, generalizando, em uma divisão de um inteiro a por outro inteiro n:
a = qn + r
Onde q é o quociente da divisão e r é o resto. Para simplificar, usamos a notação q = [a/n] para representar a divisão inteira entre a e n e r = a mod n para o resto da divisão entre os dois inteiros. Perceba como transformamos o problema em uma relação entre inteiros. Isso nos permite entrar no assunto de aritmética modular e congruência.
Podemos representar os dias da semana pelos inteiros de 1 a 7: 1 é domingo, 2 segunda... até 7. Pergunta: se você está no dia 1 e passam-se 14 dias, em qual dia da semana você estará? Muito cuidado para não responder 15, pois os dias da semana só vão de 1 a 7. Instintivamente sabemos que estaremos no domingo de outra semana, devido à aritmética modular.
15 = 7 * 2 + 1
Generalizando:
a = [a/7] + a mod 7
O que fizemos foi avançar duas semanas e "parar" no dia 1, ou seja, domingo. Se 15 dias se passassem, percorreríamos duas semanas e chegaríamos ao dia 2, segunda. O que realmente nos importa é o resto da divisão do número por 7 para determinar o dia da semana. A aritmética modular é muito útil em problemas envolvendo fenômenos periódicos, como no ciclo trigonométrico. Ainda no exemplo dos dias da semana:
1 mod 7 = 1 (estamos no domingo, dia 1)
2 mod 7 = 2 (estamos na segunda, dia 2)
8 mod 7 = 1 (passou-se uma semana e estamos no domingo)
9 mod 7 = 2 (passou-se uma semana e estamos na segunda)
15 mod 7 = 1 (passaram-se duas semanas e estamos no domingo)
16 mod 7 = 2 (passaram-se duas semanas e estamos na segunda)
Normalmente utilizamos a seguinte notação para expressar relações de congruência:
1 ≡ 1 (mod 7) (lê-se 1 é congruente a 1 módulo 7)
2 ≡ 2 (mod 7)
8 ≡ 1 (mod 7)
... E por aí vai. Há muito mais a se falar sobre congruência, mas vamos parar por aqui.
Divisibilidade e MDC
Já sabemos que a = qn + r representa uma divisão entre inteiros a e n. Naturalmente, ela se verifica também quando o resto for 0, como em 4 dividido por 2: 4 = 2 * 2 + 0. Quando isso ocorre dizemos que n|a (n divide a), ou seja, existe algum inteiro i de tal forma que a = n * i. O número n é, então, um divisor de a e este é um múltiplo de n.
E aqui entram os números primos, esses peculiares inteiros que só têm 2 divisores: 1 e si próprio. E se um número não for primo nem 0, 1 ou -1, ele é composto. Composto de quê? De seus divisores, que podem ser outros números compostos, e estes são compostos de mais divisores... repita o processo indefinidamente até chegar ao "núcleo" do número. Por exemplo, vamos analisar os fatores de 240:
240 = 24 * 10
240 = (6 * 4) * (5 * 2)
240 = (3 * 2 * 2 * 2) * (5 * 2)
240 = 2^4 * 3 * 5
Como 2, 3 e 5 são números primos, terminamos o processo de decomposição. E se decompomos um número, então podemos dizer que os números primos são os blocos básicos de construção que compõem qualquer número. Este é o Teorema Fundamental da Aritmética, utilizado na criptografia para gerar números muito grandes de tal forma que seja muito difícil fatorá-los.
Voltando à divisibilidade, se d|a e d|b, então d é um divisor comum de a e b. De forma geral, d|(ax + by) para quaisquer inteiros x e y. Como o nome indica, o máximo divisor comum (MDC) é o maior valor positivo de d. Há um método muito prático para obter o MDC entre dois números e será muito útil quando explorarmos equações diofantinas: o algoritmo de Euclides, já mencionado e implementado em Python aqui.
Sistemas de numeração e critérios de divisibilidade
São tópicos aparentemente triviais, mas trazem fatos importantes e úteis. Voltemos às primeiras séries do ensino fundamental, quando sua maior preocupação provavelmente era descobrir quem seria o próximo digi-escolhido (ainda não tinha entrado em vigor o novo acordo ortográfico). Aprendemos que um número é formado por casas decimais, de modo que seu valor é determinado pelas potências de 10. Por exemplo:
2345 = 2 * 1000 + 3 * 100 + 4 * 10 + 5 * 1 = 2 * 10³ + 3 * 10² + 4 * 10¹ + 5 * 10^0
Nosso sistema de numeração é decimal e posicional, ou seja, o valor de um dígito depende de sua posição no número. O dígito 2 em 2345 está na 4ª posição, então encontra-se na casa dos milhares. Mas poderíamos dizer o mesmo de um número binário, na base 2, como 1010:
1010 = 1 * 2³ + 0 * 2² + 1 * 2¹ + 0 * 2^0 = 8 + 2 = 10
Por que tudo isso? Para podermos entender melhor como funcionam os critérios de divisibilidade introduzidos desde cedo, mas sem nenhuma explicação satisfatória. Mas além de 1, 2, 3, 5, 9 e 10, os mais populares, não existem regras para 4, 6, 7 e 8? E por que não para 11, 12 e por aí vai? E mais importante: por que dão certo? Descubra aqui.
Equações diofantinas
Equações diofantinas são equações polinomiais nas quais procuram-se apenas as soluções inteiras. Por exemplo, se temos notas de 2 e de 5 reais, quais são os valores que podemos obter com algumas combinações dessas notas? Fica claro em valores pequenos como 2, 5, 9, 10... mas será que podemos combiná-los para formar, por exemplo, 111 reais? Estamos diante do seguinte problema:
Quais os valores de n para os quais a equação 2x + 5y = n possui alguma solução inteira?
Primeiro precisamos estabelecer o teorema de Bézout. Dados inteiros a e b, existem inteiros x e y de forma que ax + by = n se e somente se mdc(a, b)|n. Mas que soluções são essas? Em equações diofantinas, primeiro resolvemos o problema para um caso particular (x0, y0) e generalizamos:
x = x0 - b't
y = y0 + a't
Onde a' = a/mdc(a, b) e b' = b/mdc(a, b). Tente provar esse teorema e responder à questão acima (resoluções nesta página). A propósito, equações do tipo ax + by = n são chamadas equações diofantinas lineares.
Fontes
Teoria de números - Wikilivros
Imersão Olímpica - Introdução à teoria dos números
Curiosidades sobre números primos
Discrete Mathematics/Number theory
Teoria dos números: uma introdução
Number theory
Postagens
0 comentários:
Postar um comentário