Aldeia Numaboa UM PORTAL DIFERENTE EM PORTUGUÊS DO BRASIL

Teoria dos Números

Detalhes

Categoria: Matemática Numaboa

Atualização: Domingo, 21 Fevereiro 2010 12:57

Autor: vovó Vicki

Acessos: 142259

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, ...

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:

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:

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 p₁ seja o menor dos divisores. Neste caso, p₁ precisa ser primo. Se p₁ não for primo, então existe um inteiro 1 < k < p₁ e k divide p₁. Se k divide p₁, então k também divide n, o que contradiz a escolha de p₁.

Então

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

Repetimos este argumento com n₁ para determinar se n₁ é primo (terminando a demonstração com n = p₁n₁) ou se n₁ = p₂·n₂ onde p₂ é primo e n₁ > n₂.

Repetimos novamente o argumento com n₂, n₃, ... Este processo não pode continuar indefinidamente porque, pelo Princípio da Boa Ordenação, o conjunto dos inteiros positivos n > n₁ > n₂ > n₃... possui um último elemento, digamos p_k. 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:

A forma canônica

A forma canônica (ou padrão) da fatoração é expressa como se mostra ao lado, onde os números primos p_i satisfazem p₁ < p₂ < ... < p_k 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, 6² = 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.

É 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:

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

a | b	significa que a divide b
a 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 p^k || a para indicar que p^k divide a, porém p^k+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.

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)

A função σ(n)

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

Por exemplo:

sigma(2000) = sigma(2⁴5³) = sigma(2⁴) · sigma(5³) = (2⁵-1) / (2-1) · (5⁴-1) / (5-1) = 31 · 156 = 4836

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:

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:

ou seja

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

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ó