A Aldeia Numaboa ancestral ainda está disponível para visitação. É a versão mais antiga da Aldeia que eu não quis simplesmente descartar depois de mais de 10 milhões de pageviews. Como diz a Sirley, nossa cozinheira e filósofa de plantão: "Misericórdia, ai que dó!"

Se você tiver curiosidade, o endereço é numaboa.net.br.

Teoria dos Números

Ter

7

Nov

2006


15:20

(492 votos, média 3.59 de 5) 


Professor Euclides Embora existam diversos tipos de números (reais, complexos, etc.), o nome "Teoria dos Números" é tradicionalmente reservado para o estudo dos Números Inteiros, isto é: ..., -3, -2, -1, 0, 1, 2, 3, ...

O nome Aritmética também é usado. Esta denominação vem de arithmós que, em grego, significa número. Tanto a Aritmética quanto a Álgebra pertencem ao Cálculo. A Aritmética opera sobre os valores enquanto que a Álgebra se ocupa das funções.

Apesar de parecer coisa muito simples, preparem-se: vamos precisar de muita Aritmética para poder entender a criptologia!

Propriedades dos Números Inteiros

As propriedades mais importantes dos números inteiros (e que não têm similares nos números reais e complexos) são o Princípio da Boa Ordenação e o Princípio da Indução.

Pelo Princípio da Boa Ordenação:

     Qualquer conjunto não vazio de inteiros,
limitado inferiormente,
possui um elemento mínimo.

Segundo o Princípio da Indução:

     Se uma propriedade P(n), referente ao inteiro n, for verdadeira para n=a
e a veracidade de P(n) fizer com que P(n+1) seja verdadeira,
então P(n) é verdadeira para todo inteiro maior ou igual a a.

A partir das propriedades usuais da adição e da multiplicação de inteiros, da relação < e do Princípio da Boa Ordenação (ou do da Indução, que lhe é equivalente), é possível construir toda a Teoria dos Números. Um de seus resultados mais importantes é o Teorema Fundamental da Aritmética, segundo o qual todo inteiro (diferente de 0, 1 e –1) pode ser escrito de modo único como um produto de fatores primos.

O Princípio da Boa Ordenação

Quando tentamos desenvolver os inteiros axiomaticamente, através de uma pequena lista de suposições básicas, geralmente incluímos o Princípio da Boa Ordenação como um dos itens da lista:

Princípio da Boa Ordenação Todo conjunto S de inteiros positivos não vazio contém um elemento mínimo, isto é, existe pelo menos um elemento em S de modo que a < b para todos os elementos b de S.

Observe que os números reais positivos não têm esta propriedade. Por exemplo, não existe o menor número real positivo r porque r/2 é um número real positivo menor! Os inteiros negativos também não possuem esta propriedade porque se r for um inteiro negativo, então r-1 é um inteiro negativo menor.

Este princípio dos inteiros positivos é muito simples, porém tem muitas consequências. Veja uma delas na seguinte demonstração:

Teorema Todo inteiro n maior do que 1 pode ser expresso como um produto de primos.

Demonstração:

Ou n é primo ou possui um divisor diferente de um e ele próprio. Caso seja primo, então a demonstração está feita porque, neste caso, n é o produto de 1 e ele próprio, um número primo n.

Que p1 seja o menor dos divisores. Neste caso, p1 precisa ser primo. Se p1 não for primo, então existe um inteiro 1 < k < p1 e k divide p1. Se k divide p1, então k também divide n, o que contradiz a escolha de p1.

Então

     n = p1 x n1, onde p1 é primo e n > n1

Repetimos este argumento com n1 para determinar se n1 é primo (terminando a demonstração com n = p1n1) ou se n1 = p2·n2 onde p2 é primo e n1 > n2.

Repetimos novamente o argumento com n2, n3, ... Este processo não pode continuar indefinidamente porque, pelo Princípio da Boa Ordenação, o conjunto dos inteiros positivos n > n1 > n2 > n3... possui um último elemento, digamos pk. Neste caso,

     n = p1 · p2 · ... · pk

Considerando-se a ordem dos fatores, esta fatoração é única.

Teorema Fundamental da Aritmética

Se um número n não for primo podemos fazer sua fatoração em primos, isto é, expressá-lo como um produto de números primos. Esta fatoração sempre é possível? A fatoração de um número é única? Ao redor de 350 a.C. Euclides afirmou que sim. Nos dias atuais a resposta de Euclides à primeira pergunta é apresentada da seguinte forma:

Cada um dos números inteiros positivos maiores do que um podem ser expressos de forma única como um produto de números primos, independentemente do rearranjo dos termos.

A forma canônica

Fatoração

A forma canônica (ou padrão) da fatoração é expressa como se mostra ao lado, onde os números primos pi satisfazem p1 < p2 < ... < pk e os expoentes são inteiros positivos. Por exemplo, 60 = 22·31·51. Também se pode expressar o Teorema Fundamental da seguinte forma: a fatoração canônica de um número inteiro maior do que um é única.

Este teorema (como qualquer outro teorema chamado de "fundamental") não deve ser aplicado sem a devida precaução. Existem muitos sistemas numéricos nos quais a fatoração não é única. Por exemplo, imagine um sistema que tenha apenas inteiros pares (adição e multiplicação usual) e denomine um número de "par-primo" se ele não for o produto de dois outros números pares. Neste caso, os "par-primos" são 2, 6, 10, 14, 18, ... Observe que 36 possui duas fatorações diferentes, ou seja, 62 = 2·18.

Propriedades do Teorema Fundamental

Se, dependendo do sistema numérico, a fatoração não é única, então qual é a razão pela qual o teorema fundamental se mantém? Basicamente, devido a duas propriedades:

  • Todo número inteiro pode ser expresso como um produto de números primos (uma simples consequência do princípio da boa ordenação).
  • Se um número primo p divide ab, então p divide a ou b.

Algumas vezes a segunda propriedade é usada para definir números primos.

Divisibilidade

Um conceito chave na Teoria dos Números é o conceito de divisibilidade. Enquanto nos números reais, por exemplo, pode-se dividir qualquer número por outro (não nulo), obtendo como resultado um número real, nos inteiros é diferente. Um inteiro a só é divisível pelo inteiro b quando existir um inteiro c tal que a=bc. Neste caso, diz-se também que b é um divisor de a ou que b divide a, ou ainda que a é múltiplo de b.

Por exemplo, 8 é divisível por 2, mas não é por 3. Mesmo que a não seja divisível por b, pode-se sempre encontrar, de modo único, inteiros c (quociente) e r (resto) tais que a=bc+r, com 0 < r < b.

Existem muitos aspectos interessantes referentes à divisão de números inteiros. Antes que possam ser analisados, é necessário que conceitos básicos como divisor e divide estejam bem claros.

Inteiros

É lógico que podemos efetuar as quatro operações com números inteiros. Somar e subtrair é como correr pela linha onde os inteiros estão dispostos. Multiplicar é como se fosse correr mais depressa.

DIVIDIR já nos traz uma dor de cabeça: nem sempre podemos dar passos completos e a gente acaba tropeçando nos restos.

Divisores

Os divisores ou fatores de um número inteiro positivo são inteiros que dividem o número uniformemente. Por exemplo, os divisores de 28 são 1, 2, 4, 7, 14 e 28. Claro que 28 também é divisível pelos opostos de cada um dos divisores (-1, -2, etc) mas, geralmente, consideramos como "divisores" apenas os positivos. Veja a definição clássica de número primo: aquele cujos únicos divisores são 1 e ele próprio. Nadinha de negativos...

Muitas funções da teoria dos números estão relacionadas a divisores de n. Por exemplo, τn ou tau(n) é o número de divisores de n e σn ou sigma(n) é a soma dos divisores de n.

Existe um outro uso para a palavra divisor: quando dividimos um número inteiro a por um inteiro b diferente de zero para obter um quociente e um resto (veja o algoritmo da divisão), b é o divisor e a é o dividendo.

Divide

Dizemos que um inteiro divide outro inteiro quando ele o faz uniformemente, ou seja, quando o resto da divisão for zero. Algumas vezes dizemos "sem resto", mas isto não é tecnicamente correto. Os matemáticos escrevem isto com um pouco mais de formalidade:

Se a e b são inteiros e a for diferente de zero, dizemos que a divide b se houver um inteiro c de modo que b = ac.

Este conceito é usado com tanta frequência que tem até seus próprios símbolos:

a | b significa que a divide b
a Não divide b significa que a não divide b

Finalmente, suponha que p seja um número primo e que k seja um inteiro positivo. Uma notação que rapidamente está ganhando aceitação é escrever pk || a para indicar que pk divide a, porém pk+1 não.

Propriedades da Divisão

  • a | 0, 1 | a e a | a
  • a | 1 se, e somente se a=±1
  • Se a | b e c | d então ac | bd
  • Se a | b e b | c então a | c
  • a | b e b | a se, e somente se a=±b
  • Se a | b e b não for zero, então |a| < |b|
  • Se a | b e a | c então a | (bx+cy) para todos os inteiros x e y
O algoritmo da divisão

Na verdade, o algoritmo da divisão não é um algoritmo. É um teorema que foi "provado" uma vez através de um algoritmo que explica como se processa a divisão. Atualmente, a prova geralmente se baseia no princípio da boa ordenação.

Se a e m forem quaisquer números inteiros e m for diferente de zero, então há números inteiros únicos q e r de modo que a = qm + r e onde 0 < r < |m|.

Por exemplo, se a = 36 e m = 13, então q = 2 e r = 10 porque 36 = 2·13 + 10.

Da mesma forma, se a = -63 e m = 20, então q = -4 e r = 9 porque -63 = -4·20 + 17.

Mais uma vez: se a = 24 e m = -15 então q = -1 e r = 9 uma vez que 24 = -1·(-15) + 9.

Os números únicos q e r são denominados respectivamente de quociente e resto. O resto também é chamado de último resíduo não negativo módulo m.

Finalmente, a = qm + r implica que a = r (mod m). Em caso de dúvida, leia o texto sobre Congruências.

A função τ(n)
Inteiro n Divisores τ(n)
1 1 1
2 1, 2 2
3 1, 3 2
4 1, 2, 4 3
5 1, 5 2
6 1, 2, 3, 6 4
7 1, 7 2
8 1, 2, 4, 8 4
9 1, 3, 9 3
10 1, 2, 5, 10 4
11 1, 11 2
12 1, 2, 3, 4, 6, 12 6
13 1, 13 2

O número de divisores positivos de n é dado pela função τ(n) (que também pode ser indicada por d(n) ou tau(n)). Na tabela ao lado estão os primeiros valores desta função. Percebe-se claramente que, para os primos p, τ(p)=2. Além disso, para as potências de primos, τ(pn)=n+1. Por exemplo, 34 possui cinco (4+1) divisores positivos, ou seja, 1, 3, 32, 33 e 34.

Uma vez que τ(x) é uma função multiplicativa, isto é o suficiente para determinar a função tau para todos os inteiros n:

Se a fatorização canônica de n é Fatorização então o número de divisores é

τ(n) = (e1+1)(e2+1)(e3+1) ... (ek+1)

Por exemplo, 4200 é 23315271, de modo que ele tem (3+1)(1+1)(2+1)(1+1) = 48 divisores positivos.

A função σ(n)
Inteiro n Divisores σ(n)
1 1 1
2 1, 2 3
3 1, 3 4
4 1, 2, 4 7
5 1, 5 6
6 1, 2, 3, 6 12
7 1, 7 8
8 1, 2, 4, 8 15
9 1, 3, 9 13
10 1, 2, 5, 10 18
11 1, 11 12
12 1, 2, 3, 4, 6, 12 28
13 1, 13 14

A função sigma de um inteiro positivo n é a soma dos seus divisores positivos. Esta função é anotada como sigma(n) ou, preferencialmente, pela letra grega σ(n). Observe que, para os primos p, σ(p)=p+1. Como sigma é uma função multiplicativa, seus valores podem ser determinados através das potências dos seus valores primos:

Teorema: Se p é primo e n é um inteiro positivo qualquer, então

sigma(pn) = (pn+1-1) / (p-1)

Por exemplo:

sigma(2000) = sigma(2453) = sigma(24) · sigma(53) = (25-1) / (2-1) · (54-1) / (5-1) = 31 · 156 = 4836

|||| Compostos::

Números Primos e Compostos

Todo inteiro a é divisível por 1, -1, a e -a. Estes são os divisores triviais de a. Um inteiro é dito primo quando só possui os divisores triviais, ou seja, só é divisível por 1 e por ele próprio.

Um inteiro de valor absoluto maior do que 1 e que não seja primo (isto é, que possua divisores não triviais) é dito composto. Por exemplo: São primos 2, -2, 3, -3, 17, .... e são compostos 6=2x3, -8=(-2)x4, ...

Os números 0, 1 e –1 não são primos e nem compostos.

Quantos números primos existem? Euclides foi o primeiro a demonstrar que existem infinitos números primos.

Os números primos têm uma enorme importância na criptologia. Por este motivo, este assunto é tratado numa página própria. Os números compostos merecem mais alguns comentários.

Números Compostos

Um número composto é um inteiro positivo n que pode ser fatorado em números inteiros positivos menores (n=ab), nenhum deles com valor 1. Isto significa que os inteiros positivos podem ser desmembrados em três classes:

  • A unidade {1}
  • Os números primos {2, 3, 5, 7, 11, 13, 17, ...}
  • Os números compostos {4, 6, 8, 9, 10, 12, ...}

Como estabelecer se n é um número composto? Uma das maneiras é achar um divisor próprio. Se n for pequeno, então podemos dividí-lo pelos números primos menores que a raiz quadrada de n. Se qualquer um dos números primos menores que a raiz quadrada de n dividir n, então ele é um número composto - caso contrário, é um número primo. Por exemplo:

     n = 31                                      n = 32
V-36 = 5.57 V-36 = 5.75
31 / 2 = 15 resta 1 32 / 2 = 16 resta 0
31 / 3 = 10 resta 1
31 / 5 = 6 resta 1
Não é preciso dividir por 7 porque
este primo é maior do que a raiz
quadrada de 31.

RESULTADO: 31 é um número primo, RESULTADO: 32 é um número
não é um número composto. composto, não é um número primo.

Quando n for muito grande, é uma loucura ficar tentando centenas de divisões por números primos. Neste caso pode-se usar os testes clássicos de primalidade ou testes mais modernos, como o ECPP ou a ciclotomia.

Uma das principais razões de se testar a primalidade é que muitos métodos criptográficos (como, por exemplo, o RSA) e grande parte da segurança na Internet (por exemplo, o PGP) dependem, em parte, da dificuldade relativa de se fatorar números grandes. Para os matemáticos, porém, o mais importante é que este problema sempre foi um problema crucial na teoria dos números. Gauss o evidencia da seguinte maneira:

O problema em distinguir números primos dos números compostos e de resolver os últimos em seus fatores primos é reconhecidamente um dos mais importantes e úteis na Aritmética. Ele ocupou a diligência e a sabedoria de geômetras da antiguidade e da atualidade numa tal extensão que seria supérfluo prolongar a discussão... Além do mais, a própria dignidade da ciência parece requerer que qualquer recurso possível seja explorado para a solução de um problema tão elegante e tão célebre.
(Karl Friedrich Gauss, Disquisitiones Arithmeticae, 1801)

Máximo Divisor Comum - MDC

O máximo divisor comum de dois números inteiros a e b é o maior número inteiro que divide ambos. A notação disto geralmente é MDC(a,b) e, algumas vezes, simplesmente (a,b). Por exemplo, MDC(24,84)=12, MDC(-5,-100)=5 e MDC(46,111)=1.

Isto pode ser facilmente expandido para incluir qualquer quantidade de números inteiros: MDC(27,30,36,81)=3.

O máximo divisor comum dos inteiros não nulos a e b tem a propriedade de ser múltiplo de qualquer divisor comum de a e b e pode ser encontrado pelo algoritmo de Euclides. Quando o máximo divisor comum de a e b for 1, então seus únicos divisores comuns são 1 e –1. Nesse caso, a e b são ditos primos entre si, ou relativamente primos. Por exemplo, 9 e 14 são primos entre si.

O Algoritmo de Euclides

O Algoritmo de Euclides para calcular o máximo divisor comum de dois números inteiros diferentes de zero baseia-se no seguinte fato:

Se r é o resto quando a é dividido por b, então o máximo divisor comum de a e b é igual ao máximo divisor comum de b e r.

ou seja

MDC(a,b) = MDC(b,r)

Por exemplo, MDC(159,35) é:,/p>

     MDC(160,35) = MDC(35,20) porque
160/35 = 4 resto 20

MDC(35,20) = MDC(20,15) porque
35/20 = 1 resto 15

MDC(20,15) = MDC(15,5) porque
20/15 = 1 resto 5

MDC(15,5) = MDC(5) porque
15/5 = 3 resto 0

MDC(160,35) = MDC(35,20) = MDC(20,15) = MDC(15,5) = 5

Considerações Finais

Uma das características da Teoria dos Números é que ela inclui problemas extremamente simples de enunciar mas que, ao mesmo tempo, são incrivelmente difíceis de resolver. Um exemplo é a conjectura de Feuerbach, "todo número par é a soma de dois números primos", que ninguém até hoje conseguiu decidir se é verdadeira ou falsa. Outro exemplo é o famoso Último Teorema de Fermat: "Dado um inteiro n maior que 2, é impossível encontrar inteiros não nulos x, y, z tais que xn+yn=zn". Este teorema, enunciado no século XVII por Fermat, só foi demonstrado em 1995, por Wiles.

Gauss, o "príncipe dos matemáticos", dizia que a Matemática era a rainha das ciências e a Aritmética, a rainha das Matemáticas. Gauss desenvolveu muito a Teoria dos Números. Aos 22 anos, em 1799, publicou em latim suas "Investigações Aritméticas", onde introduziu o importante conceito de congruência para números inteiros.

O matemático inglês Hardy, grande especialista na Teoria dos Números, orgulhava-se, em 1940, de que "nenhuma descoberta sua havia feito, nem provavelmente viria a fazer, direta ou indiretamente, alguma diferença no conforto da humanidade". No entanto, 50 anos depois, um obscuro matemático americano descobriria uma falha no recém lançado processador Pentium, ao realizar cálculos "inúteis" sobre primos gêmeos (números primos que diferem em 2).

No mesmo momento em que Hardy escrevia aquela frase, durante a segunda guerra mundial, os norte-americanos Rivest, Shamir e Adlemann desenvolviam um sistema de código secreto, chamado RSA, baseado nas dificuldades insuperáveis de se descobrir os fatores primos de um número muito grande. Surgia um novo ramo da Criptografia, a ciência dos códigos, fortemente baseado na Teoria dos Números. Com o advento dos computadores e da computação algébrica, a Criptografia ganhou um novo impulso. Atualmente a proliferação de senhas bancárias e de cartões de crédito, bem como a crescente necessidade de criptografar dados confidenciais que inundam a Internet, fazem da Criptografia um dos ramos mais em moda da Matemática Aplicada - e um dos mais úteis, para desespero póstumo de Hardy smile

Recado da vovó

Este é apenas o be-a-bá da Teoria dos Números e já trouxe uma porção de supresas. Como não sou matemática (gosto apenas de dar uma espiada no que Euclides tem a nos contar), acho que esta pequena introdução ficou de bom tamanho - pelo menos dá uma idéia do que este tema fascinante pode nos oferecer. Se você tiver dúvidas (eu tenho um monte) ou sugestões, faça contato.

Se você atravessou este artigo, então, como sempre, um grande abraço e beijo da vó vovo

Informações adicionais