Teoria de números/Imprimir

Origem: Wikilivros, livros abertos por um mundo aberto.
Ir para: navegação, pesquisa


Índice

Prefácio


Este livro está sendo estruturado originalmente com base em notas de aula do curso de introdução a teoria de números oferecido pelo IMPA no verão de 2008. Seu conteúdo não precisa (nem deve) se limitar àquele que consta atualmente no índice. Sendo assim, a qualquer momento o livro pode ser revisto e ampliado.

Sinta-se a vontade para ler este e qualquer outro livro do projeto, melhorando-os conforme lhe for possível. Com isso estará ajudando a aumentar a qualidade geral do Wikilivros.

Se tiver dúvidas ou sugestões sobre páginas específicas, utilize as páginas de discussão correspondentes para deixar um comentário a respeito.

Ainda há muito por fazer, mas todos aqueles que contribuem acreditam estar fazendo o possível para oferecer o melhor a todos.


Crystal Clear app kaddressbook.png Este módulo tem a seguinte tarefa pendente: Incluir no prefácio uma descrição global de quais assuntos serão tratados neste wikilivro, comentando sobre o enfoque escolhido.

Estilo


Nesta página estarão indicadas as convenções adotadas neste wikilivro, no que diz respeito a sua formatação. Recomenda-se a leitura do mesmo, por todos que pretendem contribuir com a melhoria desde texto.

Definições[editar | editar código-fonte]

Definição

Uma definição pode ser entendida como o texto que explica de forma precisa o significado de um conceito.

Observações
  • Geralmente um termo importante aparece pela primeira vez em uma definição.
  • Devido à sua importância, é bom destacar a definição do restante do texto.
  • No momento, a forma de destacar uma definição neste wikilivro é a inclusão da mesma dentro de uma região com bordas duplas, como no exemplo acima. Par isso, utilize {{Definição}}.
  • O conceito que está sendo definido tem sido colocado em negrito, sendo que o texto da explicação tem sido alinhado a esquerda.

Propriedades, Teoremas[editar | editar código-fonte]

Teorema

Sempre que uma propriedade importante dos objetos tratados no texto precisa ser destacada, isto deve ser feito em uma caixa como essa.

Observações
  • Os principais itens a ser destacados são: teoremas, proposições, corolários e pequenos lemas.
  • Utilize {{Teorema}} quando precisar destacar essas propriedades.

Demonstrações, Justificativas[editar | editar código-fonte]

Demonstração
As demonstrações aparecem em quadros como esse.
Observações
  • Utilize {{Demonstração}} nesses casos.
  • Por padrão, se não for inserido qualquer texto para a demonstração, o resultado é:
Demonstração
Esta demonstração é deixada a cargo do leitor. Sinta-se livre para melhorar a qualidade deste texto, incluindo-a na versão online deste material.

Introdução

Antes de mais, agradecemos à Wikipedia pela oportunidade.

Sem mais demoras: 1=1+1-1(=)1+1=1+1(=)(1^2)-(1^0)+(1^+∞)=1

Desde a Pré-História que surgiu a necessidade física ao ser humano de criar a Unidade. Certo dia,no paleolítico médio, um recolector começou a contar quantas bagas havia conseguido guardar depois daquele dia exaustivo de procura por alimento. Começou por usufruir de uma das ferramentas mais importantes na altura, o seu próprio corpo e o que a evolução lhe havia dado, nada mais nada menos do que os próprios dedos da sua mão.

Índice remissivo



Nuvola apps edu mathematics-p.svg

Esta página é um esboço de matemática. Ampliando-a você ajudará a melhorar o Wikilivros.


Nuvola apps korganizer.svg

Faltam capítulos neste índice.
Ampliando-o você ajudará a melhorar o Wikilivros.


Nesta página estão listados os conceitos abordados neste livro em ordem alfabética.

O nome de cada conceito possui um link para a página onde o mesmo é definido. Outras ocorrências importantes do conceito são indicadas pelos links numerados, logo após o link principal.


A[editar | editar código-fonte]

B[editar | editar código-fonte]

C[editar | editar código-fonte]

D[editar | editar código-fonte]

E[editar | editar código-fonte]

aditiva
multiplicativa

F[editar | editar código-fonte]

G[editar | editar código-fonte]

H[editar | editar código-fonte]

I[editar | editar código-fonte]

J[editar | editar código-fonte]

K[editar | editar código-fonte]

L[editar | editar código-fonte]

M[editar | editar código-fonte]

N[editar | editar código-fonte]

inteiro
natural

O[editar | editar código-fonte]

P[editar | editar código-fonte]

Q[editar | editar código-fonte]

R[editar | editar código-fonte]

S[editar | editar código-fonte]

T[editar | editar código-fonte]

U[editar | editar código-fonte]

V[editar | editar código-fonte]

W[editar | editar código-fonte]

X[editar | editar código-fonte]

Y[editar | editar código-fonte]

Z[editar | editar código-fonte]

Divisibilidade


A teoria de números é a área da matemática em que é estudado o anel dos números inteiros. O conjunto dos números inteiros é denotado por , sendo que:

O conjunto pode ser definido formalmente a partir do conjunto dos números naturais e estes, a partir dos axiomas de Peano. Para maiores detalhes sobre o assunto pode ser consultado o "capítulo específico" do wikilivro sobre álgebra abstrata, ou o livro de Milies & Coelho (2003).

O conjunto dos números inteiros é definido juntamente com duas operações: a adição e a multiplicação.

A estrutura aditiva dos números inteiros é trivial. Acompanhe os exemplos:

-2 -1 0 1 2 3 4

Como se pode observar, qualquer número inteiro pode ser "formado aditivamente" a partir do número 1. Nesse sentido, a unidade é o "bloco básico" a partir do qual são construídos todos os números inteiros, usando-se as propriedades da operação de adição (como por exemplo a associatividade e a existência de elemento oposto).

Além disso, dado um número inteiro, sua decomposição em "blocos básicos" é essencialmente uma só. Por exemplo, se considerarmos o número 5, teremos:

No entanto, a única diferença entre duas representações do 5 é a posição dos parêntesis. Não há uma mudança significativa.

Já a estrutura multiplicativa de é muito mais sofisticada. Veja alguns exemplos:

2 3 4 5 6 7 8 9 10 11 12
bloco básico bloco básico bloco básico bloco básico bloco básico

Como deve ter percebido, quando se trata da operação de multiplicação, não existe um único bloco básico que gere todos os outros números. Por exemplo, os números 2, 3, 5, 7 e 11 não têm como ser obtidos a partir da multiplicação de dois números inteiros (além de 1 e eles próprios), mas permitem gerar outros números: , e assim por diante. Parece razoável que todos os inteiros podem ser gerados dessa maneira, bastando encontrar os blocos básicos adequados.

Mas será que mesmo sendo necessários mais "blocos básicos" para a estrutura multiplicativa que para a aditiva, um número inteiro sempre será decomposto de forma única em tais blocos?

Como foi visto, isso é o que acontece na estrutura aditiva. No entanto, para responder (de forma afirmativa) a esta pergunta, será necessário definir o conceito de divisibilidade, e conhecer de suas algumas propriedades. Este é o conteúdo da próxima seção.


Definição de divisibilidade[editar | editar código-fonte]

Definição

Dados os inteiros e , diz-se que " divide " e escreve-se , se existe um inteiro tal que . Alternativamente, pode ser lido como " é divisor de ", " é um fator de " ou " é múltiplo de ". Quando não se tem , escreve-se .

O conceito apresentado acima define uma relação binária no conjunto dos números inteiros: a divisibilidade.

Lembre-se que uma relação binária sobre é qualquer subconjunto do conjunto das partes de , . No caso da divisibilidade, tem-se:

Nesses termos, quando costuma-se dizer que está relacionado com escrevendo-se .

Propriedades da divisibilidade[editar | editar código-fonte]

A relação de divisibilidade possui as seguintes propriedades, para quaisquer (salvo indicação em contrário) inteiros :

1. (reflexividade)
2. e implica (transitividade)
3. e implica ou
4. e implica (linearidade)
5. e implica
6. implica (multiplicatividade)
7. e implica (lei do cancelamento)
8. ( divide todo número inteiro)
9. (todo número inteiro divide zero)
10. implica (zero só divide zero)
11. implica (os divisores de 1 são 1 e -1)
12. e implica (compatibilidade com a ordem "")
13. e implica

1. Como segue da definição que .

2. Se e , então existem tais que e , logo e portanto .

3.

4. Como e temos que e com e . Multiplicando a primeira igualdade por e a segunda por , temos e . Somando membro a membro e colocando em evidência: daí como é inteiro segue por definição que .

5.

6.

7.

8.

9.

10.

11.

12. Como e podemos escrever com . Assim, e .

13.
Observações
  • A terceira propriedade seria chamada de anti-simetria, se não fosse necessário considerar o caso "". Quando são considerados apenas os números não-negativos (os elementos de ) a conclusão é apenas "", e as propriedades de 1 a 3 fazem da divisibilidade uma relação de ordem parcial sobre . No entanto, essa não é uma ordem total, pois nem todo par de elementos em é comparável, ou seja, existem inteiros não negativos e , para os quais não se tem nem .
  • Frequentemente é mais prático trabalhar apenas com o conjunto dos números naturais (o subconjunto dos inteiros não-negativos ) ou com os números naturais não nulos (os inteiros positivos ).
  • As propriedades 1 e 8 garantem que todo número inteiro não negativo , diferente de , possui ao menos dois divisores, chamados de divisores triviais: e . Os números que possuem somente estes divisores são de grande interesse na teoria de números, e serão estudados no próximo capítulo.

Critérios de divisibilidade no sistema de numeração decimal[editar | editar código-fonte]

Wikipedia
A Wikipédia tem mais sobre este assunto:
Critérios de divisibilidade

Nas aulas de matemática do ensino fundamental, é possível que você tenha aprendido algumas regras (ou critérios) para saber rapidamente se um certo número é divisível por outro. Por exemplo, você identifica rapidamente que um número é par quando nota que o seu último dígito é par, assim como reconhece de imediato os múltiplos de 5, pois sabe que o seu dígito das unidades é sempre 0 ou 5.

O que talvez você não saiba é que podem ser deduzidos critérios de divisibilidade para vários outros números, senão todos, embora nem sempre tais regras sejam simples e fáceis de memorizar. Uma listagem das regras mais populares é apresentada na próxima tabela. Note que as regras descritas transformam um certo número em outro, geralmente menor, que preserva a divisibilidade pelo divisor em questão. Além disso, sempre que não fica claro se um número é múltiplo de certo divisor, a mesma regra pode ser aplicada novamente ao resultado já obtido, até que se torne evidente se determinado resultado é ou não divisível pelo divisor em questão.

Um número é
divisível por...
quando... Exemplos
1 sempre! Qualquer número inteiro é divisível por 1.
2 seu dígito das unidades é par (ou seja, 0, 2, 4, 6, ou 8). 1 294 é par[1], pois 4 é par.
3 é divisível por 3 a soma dos seus dígitos.[2] 405 é divisível por 3, pois 4 + 0 + 5 = 9, que é múltiplo de 3.
4 é divisível por 4 o dígito das unidades somado com o dobro do dígito das dezenas. 5 096 é múltiplo de 4, pois 6 + (2 × 9) = 24 que é múltiplo de 4
é divisível por 4 o número formado pelos dois últimos dígitos. 70 841 não é divisível por 4, pois 41 não é.
5 o dígito das unidades é 0 ou 5. 123 456 7890 é divisível por 5, já que seu último dígito é 0.
6 é divisível por 2 e por 3. 24 é divisível por 6, já que seu é múltiplo de 2 e de 3.
é divisível por 6 a soma do dígito das unidades com o quádruplo da soma dos demais dígitos. 12 348 é divisível por 6, pois (1 + 2 + 3 + 4) × 4 + 8 = 48
7 vale qualquer dessas propriedades:
é divisível por 7 a soma alternada dos números formados pelos blocos de três dígitos (da direita para esquerda). 1 369 851 é divisível por 7, pois 851 - 369 + 1 = 483 = 7 × 69
é divisível por 7 a soma do número formado pelos dois últimos dígitos com o dobro do número formado ao desconsiderar estes dígitos. 364 é divisível por 7, uma vez que (3 × 2) + 64 = 70.
é divisível por 7 a soma do quíntuplo do último dígito com o número formado pelos dígitos restantes. 364 é divisível por 7, já que 36 + (4 x 5) = 56.
é divisível por 7 a diferença entre o número formado ao desconsiderar o último dígito e o dobro deste dígito. 364 é divisível por 7, pois 36 − (4 x 2) = 28.
8 vale qualquer dessas propriedades:
o dígito das centenas é par e o número formado pelos dois últimos dígitos é divisível por 8. 12 345 624 é divisível por 8, pois 6 é par e 24 = 3 x 8.
o dígito das centenas é ímpar e o número formado pelos dois últimos dígitos, somado com 4 é divisível por 8. 12 352, é múltiplo de 8, já que 3 é ímpar e 52 + 4 = 56 = 7 x 8.
é divisível por 8 a soma do último dígito com o dobro do número formado pelos demais. 136 é divisível por 8, uma vez que (13 × 2) + 6 = 32.
9 é divisível por 9 a soma dos seus dígitos.[3] 3 753 é múltiplo de 9, pois 3 + 7 + 5 + 3 = 18 e 1 + 8 = 9
10 o último dígito é 0. 135790 é múltiplo de 10, pois seu último dígito é 0.
11 vale qualquer dessas propriedades:
é divisível por 11 a soma alternada dos seus dígitos. 918 082 é múltiplo de 11, pois 9 - 1 + 8 - 0 + 8 - 2 = 22 = 2 x 11.
é múltiplo de 11 a soma dos números formados pelos blocos de dois dígitos (da direita para a esquerda). 627 é múltiplo de 11, pois 6 + 27 = 33 = 3 x 11.
é múltiplo de 11 a diferença entre o número formado ao desconsiderar o último dígito e o último dígito. 627 é múltiplo de 11, já que 62 - 7 = 55 = 5 x 11..


Por que esses critérios funcionam?[editar | editar código-fonte]

Diante de tantas regras, é natural não acreditar de imediato que elas sejam todas infalíveis. Você já deve ter feito (ou ouvido alguém fazer) pelo menos uma pergunta desse tipo:

Quem disse que esses macetes funcionam sempre?
Por acaso alguém já testou algum deles para todos os números, e viu que nunca falham?
Quem é que impôs essas regras?
É possível encontrar um critério para os números que não estão na tabela?

Antes de responder a essas e outras perguntas do gênero, é interessante apresentar um resultado fundamental da teoria de números. O enunciado não deve parecer uma grande novidade, pois formaliza o tão conhecido algoritmo de divisão, aquele processo utilizado ao dividir dois números manualmente. Se estiver um pouco "enferrujado", experimente calcular o resultado da divisão de 39629376 por 321, para relembrar as suas primeiras aulas de matemática...

Algoritmo da divisão (de Euclides)[editar | editar código-fonte]

Teorema

Se e são números inteiros, e , então existe um único par de números inteiros e , tais que:

, com

Uma formulação alternativa é a seguinte:

Dados os números inteiros e , ou é múltiplo de ou está entre dois múltiplos consecutivos de .

Wikipedia
A Wikipédia tem mais sobre este assunto:
Princípio da boa ordenação
Demonstração
Considere inicialmente que .

Se , então (pois para tem-se ).

Logo, pelo princípio da boa ordenação, possui um menor elemento .

Como , segue que , para algum inteiro , e .

Suponha que . Neste caso, segue que .

De fato, se ocorresse , então seria elemento de .
Além disso, e (pois ), donde não seria o menor elemento de .

Por outro lado, se , então o algoritmo pode ser aplicado a e (que não é negativo), obtendo:

, com


Quanto à unicidade do quociente e do resto, pode-se proceder da seguinte maneira: Seja , com e . Nestas condições, tem-se:

, ou seja,

Por outro lado, como o valor de cada resto está entre e , sua diferença também está. Isto significa que:

Logo,

Mas o único elemento de com módulo menor que é o . Assim, implica .

Consequentemente, de se conclui que , que equivale a , pois .


Um último passo antes de apresentar a justificativa formal para os critérios de divisibilidade mostrados anteriormente é entender como funciona o sistema de numeração decimal.

Sistemas de numeração[editar | editar código-fonte]

Conforme é ensinado nos primeiros anos de escola, um número como 726 representa a soma de 7 centenas com 2 dezenas e 6 unidades, ou seja,

Em geral, cada número inteiro não negativo possui uma única representação decimal . Este é um resultado de extrema utilidade no cotidiano, pois é graças a tal sistema de numeração que estão a disposição algoritmos tão simples para a realização de adições, subtrações, multiplicações e divisões. Ou você é capaz de se imaginar realizando uma divisão de 646 por 38 utilizando o sistema de numeração inventado pelos romanos? (Experimente: DCXLVI dividido por XXXVIII é igual a...)

Dada a importância do sistema de numeração decimal, é justo enunciar e justificar precisamente o seu funcionamento. Isso é feito no próximo teorema, que garante a existência de representações posicionais em qualquer base, não apenas na base 10.

Teorema

Dado um numero inteiro (chamado de base), maior do que a unidade, cada inteiro positivo pode ser escrito de uma única maneira como

de modo que cada inteiro verifique , e .

Utilizando o algoritmo da divisão é possível obter cada dígito de uma tal representação, um após o outro, começando pelo dígito das unidades. De fato, ao dividir o número em questão pelo valor da base, consegue-se:

Fazendo o mesmo com , resulta:

Repetindo o procedimento com cada quociente , será construída uma sequência decrescente:

Certamente algum termo da sequência deve ser igual a unidade, pois todos são números inteiros e nenhum deles é negativo. Então considere que , ou seja, que o algoritmo da divisão fornece . Neste ponto o processo pode ser interrompido, e nota-se que:

Observações[editar | editar código-fonte]

  • Quando a base não é 10, é comum usar a notação para explicitar esse fato.
  • Os sistemas que utilizam a base 2 (binário), a base 8 (octal) e a base 16 (hexadecimal) são particularmente úteis na informática e na eletrônica digital.
  • O sistema de numeração com base 60 (sexagesimal) foi inventado pelos Sumérios, e ainda é utilizado para a contagem de minutos e segundos, tanto para indicar períodos de tempo quanto para medir ângulos.

Exemplos[editar | editar código-fonte]

De posse dessas informações, já é possível demonstrar a validade dos critérios de divisibilidade dados pela tabela anterior. Nos próximos exemplos serão demonstrados alguns desses critérios. Os demais são deixados como exercício para o leitor.

Divisibilidade por 2[editar | editar código-fonte]

Proposição

Um inteiro não negativo é par, e somente se, o dígito das unidades é par.

Demonstração
Considere um número inteiro positivo cuja representação decimal é . Para mostrar que se, e somente se, , note que:

e em geral:

Portanto:

Assim,

, com

Deste modo, se , então .

Reciprocamente, se tem-se .



Divisibilidade por 3[editar | editar código-fonte]

Proposição

Um inteiro não negativo é múltiplo de 3 se, e somente se, a soma de seus dígitos é múltiplo de 3.

Demonstração
Seja um número inteiro positivo. Como no exemplo anterior, o principal é considerar as potências de 10 e os restos de suas divisões por 3.

Primeiramente, note que:

onde é o número que possui todos os seus dígitos iguais a 3. Esta última igualdade é devida à fórmula clássica para a soma dos primeiros termos de uma progressão geométrica).

Substituindo essas potências de 10, obtem-se:

ou seja,

, onde e é a soma dos dígitos de .

Deste modo, se , então .

Analogamente, se tem-se .

Divisibilidade por 11[editar | editar código-fonte]

Proposição

Um inteiro não negativo é divisível por 11 se, e somente se, a soma alternada dos seus dígitos é divisível por 11.

Demonstração
Como antes, considere um número inteiro positivo. Pode-se proceder como antes para obter o resultado. Primeiramente, observe a relação entre as primeiras potências de 10 e o número 11:

É razoável esperar que o padrão continue, ou seja, que nas potências pares se tenha para algum inteiro , e nas potências ímpares se tenha para algum inteiro .

No entanto, como a intuição as vezes falha (o próprio Fermat foi vítima de sua intuição, se enganando ao afirmar que todo número da forma é primo), é necessário provar que o padrão se repete, qualquer que seja o expoente. Em símbolos, é preciso mostrar que:

, para algum inteiro .

Para tal usaremos o binómio de Newton:

ou seja, onde

Uma vez que o padrão está justificado, o raciocínio é o mesmo do caso anterior:

ou seja,

, onde e é a soma alternada dos dígitos de .

Deste modo, se , então .

Analogamente, se tem-se .


Exercícios[editar | editar código-fonte]

  1. Justifique a validade de cada uma das propriedades da divisibilidade apresentadas no texto.

Notas[editar | editar código-fonte]

  1. Veja a fatoração de 1294 e outras informações sobre este número no Wolfram Alpha (em inglês).
  2. Conforme diversos livros
  3. Conforme diversos livros

Números primos

Um pouco de história
P. Oxy. I 29.jpg

Os números primos são conhecidos pela humanidade há muito tempo. No papiro Rhindi, por exemplo, há indícios de que o antigo povo egípcio já possuía algum conhecimento sobre esse tipo de números. No entanto, os registros mais antigos de um estudo explícito sobre números primos é devido aos gregos.

Os Elementos de Euclides (cerca de 300 aC), contém teoremas importantes sobre números primos, incluindo a demonstração de sua infinitude o teorema fundamental da aritmética. Euclides também mostrou como construir um número perfeito a partir de um primo de Mersenne.

Ao grego Eratóstenes, atribui-se um método simples para o cálculo de números primos, conhecido atualmente como crivo de Eratóstenes. Por outro lado, nos tempos atuais, os grandes números primos são encontrados por computadores, através de testes de primalidade mais sofisticados, como por exemplo o teste de primalidade AKS.

Neste capítulo será definido o que são esses números primos, e serão apresentados os principais resultados acerca destes números.

Definição de número primo[editar | editar código-fonte]

Definição

Um número primo é um número natural que tem exatamente dois divisores positivos (distintos). Um número que não é primo é chamado de composto.

Como já foi observado no capítulo anterior, o fato da divisibilidade ser reflexiva (propriedade 1) e que é divisor de qualquer número inteiro (propriedade 8) garantem que todo número inteiro diferente de e possui pelo menos dois divisores: e . Com isso em mente, alguém poderia se perguntar:

  • O que os números primos têm de tão especial, já que todos os números inteiros têm ao menos dois divisores?

É essencial notar que a definição acima exige que um número possua exatamente dois divisores positivos, antes de poder ser chamado de número primo. Assim, a definição exclui automaticamente o número da lista de números primos, pois ele possui um único divisor positivo: o próprio 1. Além disso, seria redundante dizer na própria definição que um número é primo somente se os seus únicos divisores são ele mesmo e a unidade, pois isso decorre da exigência de que tenha apenas dois divisores positivos.

Agora é possível explicar melhor a "decomposição em blocos básicos" apresentada no início desse texto.

Primeiramente, observe como os elementos de estão "ordenados" pela divisibilidade na figura a seguir:

Diagrama ilustrando a ordenação dos números inteiros pela divisibilidade

No que diz respeito a multiplicação, será mostrado que todo número inteiro pode ser decomposto em um produto de números primos. Ou seja, os números primos são realmente "blocos básicos" que permitem a construção de todos os outros números inteiros, a partir de multiplicações.

Este resultado, de grande importância é sintetizado no próximo teorema.

Teorema da existência de fatoração[editar | editar código-fonte]

Teorema

Todo número inteiro positivo maior do que um tem decomposição em fatores primos.

Demonstração
Dado um número inteiro , vamos mostrar por indução que , com cada sendo um número primo.

De fato, para , o teorema é válido, pois basta tomar .

Se , e for primo, a afirmação é obviamente verdadeira, pois é suficiente escolher .

Considere então que é composto, e que a hipótese de indução é que todo número menor que admite decomposição em fatores primos.

Logo, existem inteiros e tais que . Além disso, e são menores que .

Pela hipótese de indução, tem-se

e
,

com cada e cada sendo um número primo, donde segue que:

Assim, basta renomear os primos e como , e tem-se o teorema.

Exemplos[editar | editar código-fonte]

Com o auxílio de um computador, e algum software para computação algébrica, verifica-se ques são verdadeiras as seguintes igualdades:

e ainda:

Na página Factorization using the Elliptic Curve Method está disponível um pequeno aplicativo que determina a fatoração de um número ou expressão numérica. O aplicativo foi escrito em Java, e não precisa ser baixado para poder ser executado.

Nos próximos exemplos, são apresentados alguns sub-conjuntos de onde a operação de multiplicação continua (bem) definida. Esses conjuntos, assim como o conjunto dos números inteiros, possuem "blocos básicos" que permitem gerar todos os seus elementos a partir da multiplicação. No entanto, os exemplos servirão como motivação para o Teorema fundamental da artimética que será demosntrado posteriormente. Esse teorema garante que um número inteiro só possui uma decomposição em fatores primos, ou seja, se Carlos e Joana encontrarem duas fatorações em primos para um certo número inteiro , então ambos encontraram os mesmos números primos, cada um aparecendo a mesma quantidade de vezes nas duas fatorações.

Ao contrário do que se possa esperar, essa propriedade não é uma consequência imediata das definições de divisibilidade e de números primos. Na verdade, a unicidade só é válida porque possui além de uma estrutura multiplicativa, uma estrutura aditiva com "boas propriedades". É a partir das propriedades de ambas as estruturas, que o teorema poderá ser demonstrado.

Os próximos exemplos servirão, portanto, para mostrar que em conjuntos onde se tem apenas uma estrutura multiplicativa, a decomposição em fatores "primos" (será dado um novo significado ao termo) pode não ser única.

O conjunto dos números pares positivos[editar | editar código-fonte]

Considere o conjunto .

Quem são os elementos que permitem "gerar" todos os demais através da multiplicação? Acompanhe:

2 4 6 8 10 12 14 16 18 ...
fatoração de 2 6 10 14 18 ...

Observe que 6 não pode ser escrito como o produto de outros dois números pares, pois estes teriam que ser necessariamente menores que 6. Assim, é rápido verificar (fazendo alguns poucos testes) que tal fatoração não é possível.

Nesse sentido, o número 6 (assim como o 2, o 10, o 14 e o 18) é um elemento irredutível de . De modo geral, um elemento é irredutível se não puder ser decomposto em um produto. Os elementos que não são irredutíveis, são naturalmente chamados de redutíveis.

Observe que se é um elemento redutível de , então , ou seja, todo elemento redutível é um múltiplo de 4.

Os elementos irredutíveis de serão os "blocos básicos" a partir dos quais poderão ser gerados todos os outros números pares.

Da mesma forma como foi demonstrado que todo número inteiro possui uma decomposição em fatores primos, pode-se provar que todo elemento de possui uma decomposição em fatores irredutíveis.

Prova
Esta prova é deixada a cargo do leitor. Sinta-se livre para melhorar a qualidade deste texto, incluindo-a na versão online deste material.

Uma última consideração a respeito do conjunto (e que justifica a escolha do mesmo para este exemplo), é que embora todos os seus elementos admitam uma fatoração em irredutíveis, pode haver mais de uma decomposição para um mesmo número. Veja:

E como se verifica facilmente, os números acima são todos irredutíveis em .

Essa característica sugere que se os números inteiros possuem uma única fatoração em primos, isso se deve a alguma outra propriedade de , além de sua estrutura multiplicativa.

O monóide de Hilbert[editar | editar código-fonte]

Seja .

Verifica-se facilmente que a multiplicação de elementos de possui as seguintes propriedades:

  1. , quaisquer que sejam ;
  2. , para quaisquer ;
  3. O elemento neutro da multiplicação, o número inteiro 1, está em .

Este conjunto é conhecido como o monóide de Hilbert.

A propriedade 1 decorre dos seguintes cálculos: Se e então

Novamente, tem-se a decomposição em fatores irredutíveis (fatores que não são produto de outros elementos em ). Acompanhe a fatoração de alguns elementos de :

1 5 9 13 17 21 25 29 ... 45 ... 65 ... 117 ...
fatoração de 1 5 9 13 17 21 29 ... ... ... ...

Outros monóides[editar | editar código-fonte]

É possível obter outros exemplos similares procedendo de forma análoga com os conjuntos , e em alguns casos com (para quais ainda funciona?). Também o conjunto possui essas propriedades.

Teorema de Euclides[editar | editar código-fonte]

Teorema

Existe uma infinidade de números primos.

Demonstração de Euclides[editar | editar código-fonte]

Demonstração
Considere um conjunto finito de números primos, contendo uma quantidade arbitrária de elementos. Denote tal conjunto por .

Seja . Como , então tem algum fator primo , ou seja, .

Se , seria verdade que , devido a linearidade da divisibilidade. Mas nenhum primo divide 1, então .

Assim, mostrou-se que não importa quantos elementos tenha um certo conjunto de números primos, sempre existirá um outro número primo que não está em , ou seja, existe uma infinidade de números primos!

Exemplos[editar | editar código-fonte]

Se o conjunto que aparece na demonstração do teorema for constituído dos primeiros números primos, então as fatorações de para alguns valores de são as seguintes:

Fatoração de Tipo
primo
primo
primo
primo
primo
composto
composto

A demonstração acima pode ser adaptada para mostrar que o monóide de Hilbert possui infinitos elementos irredutíveis. Observe:

Demonstração
Se são elementos irredutíveis de , então é também um elemento de (por quê?), e portanto possui decomposição em fatores irredutíveis em .

Seja um dos fatores que aparecem na decomposição de .

Então , para , caso contrário (pelo mesmo motivo de antes).

Logo existem infinitos números irredutíveis em .

Observação

Não serve escolher . Por que?

Demonstração de Hermite[editar | editar código-fonte]

Esta demonstração, assim como algumas outras, é uma variante daquela dada por Euclides. Acompanhe:

Demonstração
Para cada número natural , defina-se .

Como qualquer outro número natural, possui algum fator primo . No entanto, este fator não pode ser divisor de qualquer número menor ou igual a , pois neste caso, dividiria também , e consequentemente seria divisor de .

Portanto, tem que ser maior do que .

Resumindo, dado qualquer inteiro positivo , existe um número primo que é maior do que , ou seja, o conjunto dos números primos é infinito.

Exemplos[editar | editar código-fonte]

Uma tabela como a anterior pode ser feita para os números . Neste caso, tem-se:

Fatoração de Tipo
primo
primo
primo
composto
composto
... ... ... ...
(bem grande!) ... primo

Um fato curioso é que a última linha da tabela corresponde ao maior número primo da forma para valores de até 35500.

Demonstração de Saidak[editar | editar código-fonte]

Demonstração
Esta demonstração foi publicada recentemente pelo pesquisador Filip Saidak, em seu artigo A new proof of Euclid’s theorem de 2006. A prova consiste no seguinte:

Forma-se uma sequência crescente de números , de tal modo que cada termo tenha pelo menos fatores primos. Dessa forma, inevitavelmente, conclúi-se que existem infinitos números primos.

A sequência inicia com .

Como e não têm divisores em comum, o produto possui ao menos 2 divisores primos.

Do mesmo modo, e não têm fatores em comum, logo possui ao menos 3 fatores primos.

O processo pode continuar indefinidamente, definindo-se sempre , e cada terá no mínimo k fatores primos (verifique isto por indução!).

Exemplos[editar | editar código-fonte]

Tomando , obtem-se a seguinte tabela:

Fatoração de

Teorema fundamental da aritmética[editar | editar código-fonte]

Teorema

A decomposição de um número inteiro em fatores primos é única, exceto pela ordem. Em símbolos: Se , e cada e todo é um número primo, então e para cada tem-se , para alguma permutação .

Na demonstração deste resultado será assumido que é válido um outro teorema, cuja justificativa só será apresentada no próximo capítulo. Trata-se de uma propriedade bastante elementar, que já era conhecida por Euclides (alguns anos A.C):

Teorema

Se um número primo divide o produto de dois números inteiros, então ele é divisor de um dos dois.

(I)
Observação
  • Em Álgebra a propriedade mencionada é usada para definir "primo" e em geral, a "irredutibilidade" (definida nos exemplos do primeiro capítulo) não coincide com a noção de "primalidade".
  • A estrutura aditiva de será crucial na demonstração desta propriedade e consequentemente, do teorema fundamental da aritmética.

Demonstração do teorema fundamental da aritmética[editar | editar código-fonte]

Demonstração
A prova será feita por indução.

Se , o resultado é imediato, então considere que o mesmo vale para todo número inteiro menor que .

Supondo que existem duas decomposições para o inteiro , ou seja, , segue que algum é múltiplo de . Como a ordem dos fatores não é importante, pode-se supor que .

Neste caso, seque que , pois e os únicos divisores de são e ele próprio.

Logo,

implica que

Certamente , então pela hipótese de indução, possui uma fatoração única, donde e , para cada índice.

Assim, a fatoração de é única.

Corolário[editar | editar código-fonte]

Corolário

Todo pode ser escrito como , com e .

Esta é chamada de forma padrão da decomposição em fatores primos.

Outra forma de escrita é

, com , exceto para uma quantidade finita de 's.

A constatação da verdade dessas afirmações é elementar.

Aplicação[editar | editar código-fonte]

A partir dessa notação pode-se definir uma função escolhendo . Verifica-se que a função acima definida goza das seguintes propriedades:

Essa função oferece uma forma "elegante" de se fazer certas demonstrações. Por exemplo, a irracionalidade de é provada assim:

Demonstração
Se fosse racional, poderia ser escrito como , sendo que , e .

Neste caso, seria verdade que , ou seja, . Aplicando a função em ambos os membros, segue que

No entanto, essa igualdade não é possível, pois o primeiro membro é um número par, e o último é ímpar.

Logo, só pode ser irracional.

Uma equivalência[editar | editar código-fonte]

Como foi mostrado, se a propriedade (I) for válida, tem-se a validade do teorema fundamental da aritmética. Na verdade, as duas proposições são equivalentes.

Lembre-se que para garantir uma equivalência lógica (para mais informações, consulte algumas seções do wikilivro sobre lógica), é preciso verificar duas implicações, uma das quais já foi demonstrada neste capítulo. Resta ainda verificar o seguinte: ao supor a validade do teorema fundamental da aritmética, pode ser provada a propriedade (I)?

A resposta é afirmativa, e o motivo você encontrará nesta seção. Veja:

Demonstração
Suponha que . Então, pela definição de divisibilidade, existe algum número inteiro tal que .

Mas e possuem decomposição em fatores primos, então:

e

Logo, , ou seja, precisa ser um dos 's ou um dos 's.

No primeiro caso, conclui-se que , e no segundo .

Exercícios[editar | editar código-fonte]

  1. Demonstre os seguintes fatos:
    1. Se (com ) for um número primo maior do que , então ou .
    2. O produto de dois elementos quaisquer do conjunto é ainda um elemento deste conjunto.
    3. O conjunto possui uma infinidade de números primos.

Por enquanto, há poucos exercícios sobre este capítulo. O leitor está convidado a adicionar mais exercícios nesta seção, para ajudar a melhorar o texto.

Máximo divisor comum


No capítulo anterior, foi demonstrado o teorema fundamental da aritmética. No entanto, a prova apresentada, utilizou-se de um resultado cuja prova apresentaremos neste capítulo. Para tanto, será preciso definir o conceito de máximo divisor comum entre dois números inteiros.

Este é o conteúdo da próxima seção.

Divisores comuns[editar | editar código-fonte]

Definição

Um divisor comum de e é um número inteiro que é divisor tanto de quanto de .

Exemplos[editar | editar código-fonte]

Quem são os divisores comuns de a e b?[editar | editar código-fonte]

O conjunto formado pelos divisores comuns de e será denotado por .

No primeiro capítulo, mostrou-se que o número é divisor de qualquer número inteiro. Em particular, se forem escolhidos números e , certamente será um divisor comum de ambos.

Logo, o conjunto é não vazio, pois .

O maior dos divisores comuns[editar | editar código-fonte]

Se e for um divisor comum de e de , então . Logo o conjunto é limitado superiormente e deve ter um elemento máximo, ou seja, existe um divisor comum de e maior que todos os demais. Analogamente, para , o conjunto também tem um elemento máximo. O único caso que não é limitado superiormente é o conjunto , já que zero é múltiplo de qualquer inteiro não-nulo.

Isso motiva a próxima definição.

Definição de MDC[editar | editar código-fonte]

Definição

O máximo divisor comum (abreviadamente MDC) entre dois números inteiros e , em que pelo menos um deles não é zero, é o maior elemento do conjunto , e será denotado por , ou simplesmente .

Wikipedia
A Wikipédia tem mais sobre este assunto:
Números primos entre si

Quando o conjunto possui apenas um elemento positivo, ou seja, quando , os números e são ditos primos entre si, relativamente primos ou simplesmente co-primos.


Crystal Clear app kaddressbook.png Este módulo tem a seguinte tarefa pendente: Unificar a notação utilizada ao longo do livro para denotar o MDC. Pode ser mais adequado utilizar sempre mdc(a,b), em vez de (a,b), para evitar confusões. Em caso de dúvida, pode-se discutir o assunto.

Exemplo[editar | editar código-fonte]

Qual é o máximo divisor comum entre e ?

Considerando que os divisores de são os elementos do conjunto e que os divisores de formam o conjunto , tem-se que , cujo maior elemento é . Portanto, .

Embora ainda não tenha sido explicado como encontrar o máximo divisor comum de dois números inteiros (isso será feito mais adiante), mostra-se que ele é um dos elementos do conjunto . Este resultado é um teorema surpreendente, pois relaciona a estrutura multiplicativa do conjunto dos números inteiros que foi estudada até agora, com sua estrutura aditiva:

Teorema de Bézout[editar | editar código-fonte]

Teorema

Se , então existem inteiros e tais que .

Wikipedia
A Wikipédia tem mais sobre este assunto:
Identidade de Bézout

O resultado também é conhecido como identidade de Bézout.

Antes de apresentar qualquer justificativa (construtiva ou puramente algébrica) dessa identidade, serão mostradas suas consequências imediatas mais importantes.

Corolário[editar | editar código-fonte]

Corolário

Se e então .

Demonstração
Pelo teorema anterior, o máximo divisor comum entre e pode ser escrito como:
, com e inteiros.

Multiplicando cada membro da equação anterior por , obtem-se .

Claramente, divide cada parcela desta soma. Consequentemente deve dividir .

Wikipedia
A Wikipédia tem mais sobre este assunto:
Euclides

Com essa propriedade, devida a Euclides de Alexandria, já é possível demonstrar o teorema que ficou pendente no capítulo anterior:

Propriedade fundamental dos primos[editar | editar código-fonte]

Teorema

Se um número primo divide o produto de dois números inteiros, então ele é divisor de um dos dois.

Demonstração
Sejam e um número primo que divide o produto .

Será provado que se não divide , então deve necessariamente dividir .

De fato, como é primo, o conjunto de seus divisores é . Além disso, , logo não pode ser um divisor comum de e .

Segue que .

De acordo com o corolário acima, isso implica que divide .

Demonstração do teorema de Bézout[editar | editar código-fonte]

Uma observação crucial para a demonstração do teorema de Bézout é que, para quaisquer números inteiros , tem-se a igualdade .

De fato, para que tal propriedade se verifique, é suficiente que os conjuntos e sejam iguais. Isso é verdade, pois:

  • Se um deles está definido, então o outro também está. De fato, para b diferente de zero ambos conjuntos são definidos; para b igual a zero temos que a deve ser diferente de zero, e os dois conjuntos são iguais.
  • Se , então e .

Donde, .

Assim, .

  • Reciprocamente, se , então e . Logo, deve dividir a soma:
,

ou seja, .

Outra propriedade do máximo divisor comum é a seguinte:

Por causa dela, pode ser suposto que , e obter a demonstração:

Demonstração
A prova será feita por indução em .

Obviamente, se , tem-se , e a propriedade é válida pois sempre que tem-se:

Logo, pode ser suposto que (e portanto, ).

Será tomada como hipótese de indução que: os pares de números inteiros , cuja soma seja menor que , têm .

Como , e somado com é menor que , a hipótese de indução garante que . Então:

Wikipedia
A Wikipédia tem mais sobre este assunto:
Algoritmo

Como toda prova por indução, a demonstração anterior fornece um algoritmo. No caso, trata-se de um procedimento para o cálculo de :

Dados de entrada
  Os inteiros  e .

Saída
  .

Procedimento
* Se , então ;
* Se , então ;
* Senão 

Exemplos numéricos[editar | editar código-fonte]

Usando o procedimento sugerido, pode-se calcular facilmente. Acompanhe:

No entanto, quando se tem bem maior que , a igualdade mais utilizada será .

Por exemplo, se e as etapas serão:

Neste caso, parece razoável subtrair de tantas vezes quanto for possível, em uma única etapa:

Em geral, será buscado um valor tal que , pois assim a igualdade (que é sempre verdadeira, para qualquer valor inteiro de ) reduz o cálculo de a um caso bem mais simples.

A existência de um número , satisfazendo ambas as desigualdades é garantida pelo algoritmo da divisão apresentado em um capítulo anterior. Se precisar relembrar os detalhes, consulte a seção "Algoritmo da divisão (de Euclides)".

De posse deste algoritmo, pode-se fazer uma melhoria no algoritmo sugerido anteriormente para o cálculo do MDC.

Algoritmo de Euclides para o MDC[editar | editar código-fonte]

Crystal Clear app kaddressbook.png Este módulo tem a seguinte tarefa pendente: Adicionar informações históricas sobre o algoritmo e também uma referência às aplicações atuais em música, descrita nos artigos do Brun, e do Toussaint.

Consulte a Bibliografia

Teorema

Dados , com , verifique se . Em caso afirmativo, o máximo divisor comum é o próprio . Caso contrário, repita o processo usando e o resto da divisão de por . Simbolicamente: Dados de entrada Os inteiros e . Saída . Procedimento * Se , então ; * Se , então ; * Senão , onde

Observe que esta é simplesmente uma generalização do algoritmo apresentado logo após a demonstração do teorema de Bézout.

Wikipedia
A Wikipédia tem mais sobre este assunto:
Algoritmo de Euclides

É preciso verificar que o algoritmo irá parar, e ainda mais importante, que fornecerá a resposta correta.

Considere e , e a seguinte sequência de igualdades (obtidas pelo algoritmo da divisão):

Juntando as desigualdades anteriores, tem-se uma sequência decrescente de números não negativos:

No entanto, só existe uma quantidade finita de números positivos menores que . Logo, depois de algum resto , tem-se , ou seja:

É nesse ponto que o algoritmo para: quando o resto . Segundo o enunciado, o resultado fornecido será então .

Será que este é realmente o valor de ?

A resposta é sim, pois .

Logo, obtem-se sucessivamente:

Portanto o valor fornecido pelo algoritmo corresponde a , e foi obtido através de exatamente divisões.

Exemplo numérico[editar | editar código-fonte]

Quanto é ?

Aplicando o processo usado na demonstração do algoritmo de Euclides para o MDC, tem-se:

Logo, .

Para que não seja preciso explicitar cada uma das igualdades, pode-se dispor as informações de cada etapa em uma tabela como a seguinte:

quociente 1 1 2
30 18 12 6
Resto 12 6 0

É importante notar que, embora os quocientes apareçam indicados, o interesse está no valor dos restos.

Para obter automaticamente todas as etapas da aplicação do algoritmo de Euclides a outros pares de números inteiros, pode-se utilizar este recurso on-line, desenvolvido em javascript.

Interpretação matricial[editar | editar código-fonte]

Na demonstração de que o algoritmo de Euclides funciona, aparecem várias igualdades da forma:

O índice indica que esta é a -ésima divisão efetuada no algoritmo.

Cada uma dessas equações é uma equação de diferenças de segunda ordem, em que cada termo é descrito em função de dois anteriores. No caso, cada resto depende dos próximos dois restos, e reciprocamente, cada resto depende dos dois anteriores.

Tal relação de recorrência pode também ser expressa como:

, sempre que

Com essa notação, os cálculos que aparecem no algoritmo de Euclides para o MDC tornam-se mais sucintos. Por exemplo:

Para facilitar ainda mais a escrita, pode-se adotar a seguinte convenção:

Se o cálculo anterior for efetuado para todas as etapas do algoritmo, o resultado final será:

, sendo que .

Perceba que assim não há uma confusão tão grande com os índices dos sucessivos quocientes e restos.

Como a matriz é um produto de matrizes com entradas inteiras e não-negativas, nenhuma de suas entradas deverá ser negativa. Assim, é possível escrever da seguinte forma:

, com

Disso se conclui que

Escrevendo , tem-se

, pois cada matriz tem determinante igual a .

Logo, a matriz é invertível e . Esta última igualdade se justifica pois .

Dessas considerações, resulta que:

Fazendo o produto, e igualando cada componente, conclui-se que:

A primeira destas equações corresponde ao teorema de Bézout, com e . Já a segunda, implica em . Esse valor coincide com o conhecido mínimo múltiplo comum entre e , definido a seguir:

Definição

O mínimo múltiplo comum dos inteiros e , , é o menor elemento positivo do conjunto

Segundo o comentário que precede esta definição, tem-se:

Justificativa
Fica a cargo do leitor justificar este fato. Sinta-se livre para melhorar a qualidade deste texto, incluindo a justificativa na versão online deste material.

Exemplificando[editar | editar código-fonte]

Anteriormente foi visto que:

Utilizando esses valores, segue que:

.

Para este exemplo, a matriz inversa é

Logo,

, ou seja

Note que, quando são positivos, a expressão deve ter exatamente um dos valores menor que zero, para que a combinação linear de não seja maior que qualquer um deles.

Considere uma outra situação: como encontrar o mínimo múltiplo comum entre e ?

Primeiramente, pelo algoritmo de Euclides tem-se:

Logo

Daí tem-se que

Uma demonstração alternativa do teorema de Bézout[editar | editar código-fonte]

Agora será apresentada uma prova não construtiva do teorema de Bézout. Isso significa que, embora a mesma assegure a validade do teorema, ela não fornece um método para a obtenção do MDC (ao contrário do que foi feito anteriormente).

Além disso, são utilizados alguns conceitos que certamente são conhecidos por aqueles que possuem conhecimentos básicos de álgebra. Se este não for o seu caso, você poderá pular esta seção, e não haverá prejuizo na leitura do restante deste livro.

Demonstração
Sendo números inteiros, considere .

Então, é um subgrupo aditivo de (um ideal), ou seja, possui as seguintes propriedades:

  1. ;
  2. Dados , tem-se .

De fato, se então:

com . Então:

Mas todo subgrupo (aditivo?) de é escrito como , com , pois:

Se é subgrupo de , então possui elementos não-negativos. Em particular, possui um menor elemento não-negativo .
Se então pelo algoritmo de divisão, , com .
Donde .
Como , segue que , ou seja, .

Para provar que se tem , escreva (isso é possível, já que ).

Observe que:

Então, tem-se , ou seja, é divisor de .

Mas é o maior divisor porque, dado qualquer outro divisor , tem-se

Logo, , ou seja, .

Exercícios[editar | editar código-fonte]

  1. O algoritmo da divisão estabelece que dados os inteiros , existem inteiros tais que , com . Utilize uma calculadora comum (e apenas as quatro operações elementares) para obter os valores de correspondentes a alguns pares de inteiros .
  2. Dados a e b, determine o valor de mdc(a,b) e números inteiros x, y tais que d = xa + yb, para os seguintes valores de a e b:
    1. a = 299 e b = 161
    2. a = 435 e b = 232
    3. a = 101 e b = 33
    4. a = 145 e b = 48

Ver também[editar | editar código-fonte]

Wikipedia[editar | editar código-fonte]

Bibliografia

Livros em português[editar | editar código-fonte]

Livros em inglês[editar | editar código-fonte]

Outras referências[editar | editar código-fonte]

Eficiência do algoritmo de Euclides

Neste capítulo, será discutido quão eficiente é o algoritmo de Euclides para o cálculo do MDC. De forma mais precisa, se forem dados dois números inteiros:

Quantas etapas (divisões) do algoritmo são necessárias para que um resto seja zero?

Fazendo estimativas[editar | editar código-fonte]

Recorde-se que o algoritmo baseia-se na construção da sequência:

cujos termos verificam as seguintes igualdades:

1