# Teoria de números/Imprimir

* Esta é a versão para impressão de Teoria de números
* Se você for imprimir esta página, escolha "Visualizar impressão" no seu navegador, ou clique em Versão para impressão, você irá ver esta página sem esse aviso, sem os elementos de navegação a esquerda ou acima, e sem as TOC's de cada página.
* Atualize esta página para ter certeza de que está imprimindo a versão mais atual.
* Para maiores informações sobre a versão para impressão, incluindo como fazer arquivos PDF realmente adequados para a impressão, veja Wikilivros:Versões para impressão.

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

# 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
### 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
### 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
### Observações

* Utilize {{Demonstração}} nesses casos.
* Por padrão, se não for inserido qualquer texto para a demonstração, o resultado é:

# 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

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

* Anel
* Axiomas de Peano
* Adição
* Associatividade

## B

* Bloco básico

## D

* Divisibilidade

## E

* Elemento oposto
* Estrutura
    aditiva
    multiplicativa

## L

* Lei do cancelamento
* Linearidade

## M

* Multiplicação
* Multiplicatividade

## N

* Número
    inteiro
    natural

## R

* Reflexividade

## T

* Transitividade

## Z
# 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 $\mathbb {Z}$, sendo que:
    $\mathbb {Z} =\{\ldots ,-3,-2,-1,0,1,2,3,\ldots \}$
O conjunto $\mathbb {Z}$ pode ser definido formalmente a partir do conjunto dos números naturais $\mathbb {N} =\{0,1,2,3,\ldots \}$ 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 | $\ldots$ |
| $-1-1$ | $\mathbf {-1}$ | $1-1$ | $\mathbf {1}$ | $1+1$ | $(1+1)+1$ | $(1+1)+(1+1)$ | $\ldots$ |
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:
    $\mathbf {5} =2+2+1=(1+1)+(1+1)+1$
    $\mathbf {5} =2+1+2=(1+1)+1+(1+1)$
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 $\mathbb {Z}$ é muito mais sofisticada. Veja alguns exemplos:
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | $\ldots$ |
| bloco básico | bloco básico | $2\cdot 2$ | bloco básico | $2\cdot 3$ | bloco básico | $(2\cdot 2)\cdot 2$ | $3\cdot 3$ | $2\cdot 5$ | bloco básico | $(2\cdot 2)\cdot 3$ | $\ldots$ |
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: $6=2\cdot 3$, $10=2\cdot 5$ 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
### Definição

Dados os inteiros $a$ e $b$, diz-se que "$a$ divide $b$" e escreve-se $a|b$, se existe um inteiro $c$ tal que $b=a\cdot c$. Alternativamente, $a|b$ pode ser lido como "$a$ é divisor de $b$", "$a$ é um fator de $b$" ou "$b$ é múltiplo de $a$". Quando não se tem $a|b$, escreve-se $a\not |b$.
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 $\mathbb {Z}$ é qualquer subconjunto $R$ do conjunto das partes de $\mathbb {Z}$, $P(\mathbb {Z} )$. No caso da divisibilidade, tem-se:
    $R=\{(a,b)|a{\mbox{ divide }}b\}$
Nesses termos, quando $(a,b)\in R$ costuma-se dizer que $a$ está relacionado com $b$ escrevendo-se $aRb$.

## Propriedades da divisibilidade

A relação de divisibilidade possui as seguintes propriedades, para quaisquer (salvo indicação em contrário) inteiros $a,b,c,d,r,s$:
    1. $a|a$(reflexividade) 2. $a|b$ e $b|c$ implica $a|c$(transitividade) 3. $a|b$ e $b|a$ implica $a=b$ ou $a=-b$ 4. $c|a$ e $c|b$ implica $c|ra+sb$(linearidade) 5. $a|b$ e $c|d$ implica $ac|bd$ 6. $a|b$ implica $ac|bc$(multiplicatividade) 7. $ac|bc$ e $c\not =0$ implica $a|b$(lei do cancelamento) 8. $1|a$($1$ divide todo número inteiro) 9. $a|0$(todo número inteiro divide zero) 10. $0|a$ implica $a=0$(zero só divide zero) 11. $a|1$ implica $a=\pm 1$(os divisores de 1 são 1 e -1) 12. $a|b$ e $b\not =0$ implica $|a|\leq |b|$(compatibilidade com a ordem "$\leq$") 13. $a|b$ e $a\not =0$ implica $(b/a)|b$
1. Como $a=1.a$ segue da definição que $a|a$.
2. Se $a|b$ e $b|c$, então existem $q_{1},q_{2}\in \mathbb {Z}$ tais que $b=aq_{1}$ e $c=bq_{2}$, logo $c=aq_{1}q_{2}$ e portanto $a|c$.
3. $a|b$ implica que $a\geq b$. E se $b|a$, então $b\geq a$. Logo como $a$ não pode ser menor que $b$ e $b$ não pode ser menor que $a$ ao mesmo tempo, temos que $a=b$. $a=-b$ e $-b=a$ também são possíveis, já que a diferença entre $b/a$ e $b/-a$ é somente o sinal do quociente. O mesmo vale para $b/a$ e $-b/a$.
4. Como $c|a$ e $c|b$ temos que $a=q_{1}c$ e $b=q_{2}c$ com $q_{1}$ e $q_{2}$ $\in \mathbb {Z} .$. Multiplicando a primeira igualdade por $r$ e a segunda por $s$, temos $ra=rq_{1}c$ e $sb=sq_{2}c$. Somando membro a membro e colocando $c$ em evidência: $ra+sb=(rq_{1}+sq_{2})c$ daí como $rq_{1}+sq_{2}$ é inteiro segue por definição que $c|ra+sb$.
5. Tendo $a|b$ e $c|d$, podemos transformar $a|b$ e $c|d$ em equações: $b/a=x$ e $d/c=y$, sendo $x$ e $y$ os quocientes das divisões. Multiplicando ambas as equações temos: $bd/ac=xy$. Assim, já que $xy$ é o quociente da divisão $bd/ac$ (cujo resto $=0$), temos que $ac|bd$.
6. Adicionando fatores comuns no dividendo e divisor da equação $b/a=x$ (divisão exata), que implica em $a|b$; não altera o resultado da divisão, pois: $bc/ac=(b/a)(c/c)$. Como $c/c=1$: $(b/a)(c/c)=1(b/a)=b/a$. Assim $b/a=bc/ac$, que implica em $ac|bc$.
7. Como $a|b$ vem de $b/a=x$ (c = quociente), $ac|bc$ vem de $bc/ac=x$, no qual podemos tirar $c$ da divisão, já que ele é um fator comum no dividendo e divisor de $bc/ac$. Assim $ac|bc=a|c$.
8. $1a=a$ implica que $a/1=a$. Assim $1|a$.
9. $0a=0$ implica que $0/a=0$. Logo $a|0$.
10. $a|0$ pode ser transformado em $a/0=x$. Como não existe divisão por 0 (já que tendo $0x=0$ e não existe número que multiplicado por 0 dê x </math>), o único número que pode estar no dividendo é 0. Logo $0|a$ implica em $a=0$.
11. $a|1$ implica que $1/a$. Como os divisores de $1=1;-1$, temos que $a=\pm 1$.
12. Como $a|b$ e $b\neq 0$ podemos escrever $b=aq$ com $q\neq 0$. Assim, $|q|\geq 1$ e $|b|=|a||q|\geq |a|$.
$a|b$
$b/a=c$
$b/a=c$
$(quociente)(divisor)=dividendo$
$b/c=a$
$b/a=c$
$b/c=a$
$c|b=(b/a)|b$

### Observações

* A terceira propriedade seria chamada de anti-simetria, se não fosse necessário considerar o caso "$a=-b$". Quando são considerados apenas os números não-negativos (os elementos de $\mathbb {Z} _{+}$) a conclusão é apenas "$a=b$", e as propriedades de 1 a 3 fazem da divisibilidade uma relação de ordem parcial sobre $\mathbb {Z} _{+}$. No entanto, essa não é uma ordem total, pois nem todo par de elementos em $\mathbb {Z} _{+}$ é comparável, ou seja, existem inteiros não negativos $a$ e $b$, para os quais não se tem $a|b$ nem $b|a$.
* Frequentemente é mais prático trabalhar apenas com o conjunto dos números naturais $\mathbb {N}$ (o subconjunto dos inteiros não-negativos $\mathbb {Z} _{+}$) ou com os números naturais não nulos $\mathbb {N} ^{*}$ (os inteiros positivos $\mathbb {Z} _{+}^{*}$).
* As propriedades 1 e 8 garantem que todo número inteiro não negativo $a$, diferente de $1$, possui ao menos dois divisores, chamados de divisores triviais: $1$ e $a$. 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

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, pois 4 é par. |
| 3 | é divisível por 3 a soma dos seus dígitos. | 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 |
| 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. |
| 6 | é 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: | vale qualquer dessas propriedades: |
| 7 | é 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 |
| 7 | é 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. |
| 7 | é 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. |
| 7 | é 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: | vale qualquer dessas propriedades: |
| 8 | 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. |
| 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. |
| 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 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: | vale qualquer dessas propriedades: |
| 11 | é 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. |
| 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. |
| 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?

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)
### Teorema

Se $a$ e $b$ são números inteiros, e $b\not =0$, então existe um único par de números inteiros $q$ e $r$, tais que:
    $a=bq+r$, com $0\leq r<|b|$
Uma formulação alternativa é a seguinte:
Dados os números inteiros $a$ e $b$, ou $a$ é múltiplo de $b$ ou está entre dois múltiplos consecutivos de $b$.
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

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,
    $726=\mathbf {7} \cdot 100+\mathbf {2} \cdot 10+\mathbf {6} \cdot 1$
Em geral, cada número inteiro não negativo possui uma única representação decimal $a_{n}\ldots a_{2}a_{1}a_{0}$. 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 $b$ (chamado de base), maior do que a unidade, cada inteiro positivo $a$ pode ser escrito de uma única maneira como
    $a=a_{n}\cdot b^{n}+a_{n-1}\cdot b^{n-1}+\ldots +a_{1}\cdot b+a_{0}$
$a_{i}$
$a_{i}\in [0,b)$
$a_{n}\not =0$
$n\geq 0$
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:
    $a=q_{0}b+a_{0}$
Fazendo o mesmo com $q_{0}$, resulta:
    $q_{0}=q_{1}b+a_{1}$
Repetindo o procedimento com cada quociente $q_{i}$, será construída uma sequência decrescente:
    $a>q_{0}>q_{1}>q_{2}>\ldots$
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 $q_{n}=1$, ou seja, que o algoritmo da divisão fornece $q_{n-1}=1\cdot b+0$. Neste ponto o processo pode ser interrompido, e nota-se que:
    $a$ $=q_{0}b+a_{0}$ $=(q_{1}b+a_{1})b+a_{0}$ $=q_{1}\cdot b^{2}+a_{1}\cdot b^{1}+a_{0}$ $=((q_{2}b+a_{2})b+a_{1})b+a_{0}$ $=q_{2}\cdot b^{3}+a_{2}\cdot b^{2}+a_{1}\cdot b^{1}+a_{0}$ $\vdots$ $=((???)b+a_{1})b+a_{0}$ $=a_{n}\cdot b^{n}+\ldots +a_{2}\cdot b^{2}+a_{1}\cdot b^{1}+a_{0}$

### Observações

* Quando a base não é 10, é comum usar a notação $(a_{n}\ldots a_{2}a_{1}a_{0})_{b}$ 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

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
#### Proposição

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

### Divisibilidade por 3
#### 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.

### Divisibilidade por 11
#### 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.

## Exercícios

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

## Notas

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

# Números primos

* Um pouco de história
* 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
### 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 $1$ é divisor de qualquer número inteiro (propriedade 8) garantem que todo número inteiro $a$ diferente de $1$ e $-1$ possui pelo menos dois divisores: $1$ e $a$. 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 $1$ 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 $p$ 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 $\mathbb {Z} ^{+}$ estão "ordenados" pela divisibilidade na figura a seguir:
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
### Teorema

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

## Exemplos

Com o auxílio de um computador, e algum software para computação algébrica, verifica-se ques são verdadeiras as seguintes igualdades:
    $12=2^{2}\cdot 3$
    $123=3\cdot 41$
    $1234=2\cdot 617$
    $12345=3\cdot 5\cdot 823$
    $123456=2^{6}\cdot 3\cdot 643\!$
    $1234567=127\cdot 9721$
    $12345678=2\cdot 3^{2}\cdot 47\cdot 14593$
    $123456789=3^{2}\cdot 3607\cdot 3803$
e ainda:
    $12345678901234567=7\cdot 1763668414462081$
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 $\mathbb {Z}$ 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 $n$, 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 $\mathbb {Z}$ 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

Considere o conjunto $2\mathbb {N} =\{2n:n\in \mathbb {N} \}=\{2,4,6,8,10,12,14,16,\ldots \}$.
Quem são os elementos que permitem "gerar" todos os demais através da multiplicação? Acompanhe:
| $n$ | 2 | 4 | 6 | 8 | 10 | 12 | 14 | 16 | 18 | ... |
| fatoração de $n$ | 2 | $2\cdot 2$ | 6 | $2\cdot 2\cdot 2$ | 10 | $2\cdot 6$ | 14 | $2\cdot 2\cdot 2\cdot 2$ | 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 $2\mathbb {Z}$. De modo geral, um elemento $n$ é 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 $n$ é um elemento redutível de $2\mathbb {Z}$, então $n=2p\cdot 2q=4\cdot pq$, ou seja, todo elemento redutível é um múltiplo de 4.
Os elementos irredutíveis de $2\mathbb {Z}$ 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 $2\mathbb {Z}$ possui uma decomposição em fatores irredutíveis.
Uma última consideração a respeito do conjunto $2\mathbb {Z}$ (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:
    $60=2\cdot 30=6\cdot 10$
E como se verifica facilmente, os números acima são todos irredutíveis em $2\mathbb {Z}$.
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 $\mathbb {Z}$, além de sua estrutura multiplicativa.

### O monóide de Hilbert

Seja $H=4\mathbb {N} +1=\{4n+1:n\in \mathbb {N} \}=\{1,5,9,13,17,21,29,\ldots \}$.
Verifica-se facilmente que a multiplicação de elementos de $H$ possui as seguintes propriedades:
* $a\cdot b\in H$, quaisquer que sejam $a,b\in H$;
* $\left(a\cdot b\right)\cdot c=a\cdot \left(b\cdot c\right)=a\cdot b\cdot c$, para quaisquer $a,b,c\in H$;
* O elemento neutro da multiplicação, o número inteiro 1, está em $H$.
Este conjunto $H$ é conhecido como o monóide de Hilbert.
A propriedade 1 decorre dos seguintes cálculos: Se $a=4n+1$ e $b=4m+1$ então
    $a\cdot b=(4n+1)\cdot (4m+1)=4(4n^{2}+m+n)+1=4p+1$
Novamente, tem-se a decomposição em fatores irredutíveis (fatores que não são produto de outros elementos em $H$). Acompanhe a fatoração de alguns elementos de $H$:
| $n$ | 1 | 5 | 9 | 13 | 17 | 21 | 25 | 29 | ... | 45 | ... | 65 | ... | 117 | ... |
| fatoração de $n$ | 1 | 5 | 9 | 13 | 17 | 21 | $5\cdot 5$ | 29 | ... | $5\cdot 9$ | ... | $5\cdot 13$ | ... | $9\cdot 13$ | ... |

### Outros monóides

É possível obter outros exemplos similares procedendo de forma análoga com os conjuntos $\{an+1:n\in \mathbb {N} \}$, e em alguns casos com $\{an+b:n,a,b\in \mathbb {N} \}$ (para quais $a,b$ ainda funciona?). Também o conjunto $\{x^{2}+y^{2}:x,y\in \mathbb {N} \}$ possui essas propriedades.

## Teorema de Euclides
### Teorema

Existe uma infinidade de números primos.

### Demonstração de Euclides
#### Exemplos

Se o conjunto $P$ que aparece na demonstração do teorema for constituído dos primeiros $r$ números primos, então as fatorações de $n=2\cdot 3\cdot \ldots \cdot p_{r}+1$ para alguns valores de $r$ são as seguintes:
| $r$ | $n=2\cdot 3\cdot \ldots \cdot p_{r}+1$ | Fatoração de $n$ | Tipo |
| $1$ | $3=2+1$ | $3$ | primo |
| $2$ | $7=2\cdot 3+1$ | $7$ | primo |
| $3$ | $31=2\cdot 3\cdot 5+1$ | $31$ | primo |
| $4$ | $211=2\cdot 3\cdot 5\cdot 7+1$ | $211$ | primo |
| $5$ | $2311=2\cdot 3\cdot 5\cdot 7\cdot 11+1$ | $2311$ | primo |
| $6$ | $30031=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13+1$ | $59\cdot 509$ | composto |
| $7$ | $510511=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17+1$ | $19\cdot 97\cdot 277$ | composto |
A demonstração acima pode ser adaptada para mostrar que o monóide de Hilbert $H$ possui infinitos elementos irredutíveis. Observe:

##### Observação

Não serve escolher $n=b_{1},\ldots ,b_{r}+1$. Por que?

### Demonstração de Hermite

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

#### Exemplos

Uma tabela como a anterior pode ser feita para os números $x(n)$. Neste caso, tem-se:
| $n$ | $x(n)=n!+1$ | Fatoração de $x(n)$ | Tipo |
| $1$ | $2=1+1$ | $2$ | primo |
| $2$ | $3=1\cdot 2+1$ | $3$ | primo |
| $3$ | $7=1\cdot 2\cdot 3+1$ | $7$ | primo |
| $4$ | $25=1\cdot 2\cdot 3\cdot 4+1$ | $5\cdot 5$ | composto |
| $5$ | $121=1\cdot 2\cdot 3\cdot 4\cdot 5+1$ | $11\cdot 11$ | composto |
| $26951$ | (bem grande!) | ... | primo |
Um fato curioso é que a última linha da tabela corresponde ao maior número primo da forma $n!+1$ para valores de $n$ até 35500.

### Demonstração de Saidak
#### Exemplos

Tomando $N_{1}=2$, obtem-se a seguinte tabela:
| $k$ | $N_{k}$ | Fatoração de $N_{k}$ |
| $1$ | $2=1+1$ | $2$ |
| $2$ | $6=2\cdot (2+1)$ | $2\cdot 3$ |
| $3$ | $42=6\cdot (6+1)$ | $2\cdot 3\cdot 7$ |
| $4$ | $1806=42\cdot (42+1)$ | $2\cdot 3\cdot 7\cdot 43$ |
| $5$ | $3263442=1806\cdot (1806+1)$ | $2\cdot 3\cdot 7\cdot 43\cdot 13\cdot 139$ |

## Teorema fundamental da aritmética
### Teorema

A decomposição de um número inteiro $n\in \mathbb {N} ^{*}$ em fatores primos é única, exceto pela ordem. Em símbolos:
Se $p_{1}\cdot \ldots \cdot p_{r}=n=q_{1}\cdot \ldots \cdot q_{s}$, e cada $p_{j}$ e todo $q_{j}$ é um número primo, então $r=s$ e para cada $j$ tem-se $p_{j}=q_{\sigma (j)}$, para alguma permutação $\sigma$.
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.

### 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 $\mathbb {Z}$ será crucial na demonstração desta propriedade e consequentemente, do teorema fundamental da aritmética.

### Demonstração do teorema fundamental da aritmética
## Corolário
### Corolário

Todo $n\in \mathbb {N} ^{*}$ pode ser escrito como $n=p_{1}^{e_{1}}\cdot \ldots \cdot p_{r}^{e_{r}}$, com $p_{1}<p_{2}<\ldots <p_{r}$ e $e_{i}\geq 1$.
Esta é chamada de forma padrão da decomposição em fatores primos.
Outra forma de escrita é
    $n=\prod _{p}p^{e_{p}}$, com $e_{i}=0$, exceto para uma quantidade finita de $p$'s.
A constatação da verdade dessas afirmações é elementar.

### Aplicação

A partir dessa notação pode-se definir uma função $v_{p}:\mathbb {N} \rightarrow \mathbb {N}$ escolhendo $v_{p}(n)=e_{p}$. Verifica-se que a função acima definida goza das seguintes propriedades:
* $v_{p}(m\cdot n)=v_{p}(m)+v_{p}(n)$
* $v_{p}(m+n)\geq min(v_{p}(m),v_{p}(n))$
Essa função oferece uma forma "elegante" de se fazer certas demonstrações. Por exemplo, a irracionalidade de ${\sqrt {2}}$ é provada assim:

### Uma equivalência

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:

## Exercícios

* Demonstre os seguintes fatos:
** Se $p=6k+r$ (com $0\leq r\leq 5$) for um número primo maior do que $3$, então $r=1$ ou $r=5$.
** O produto de dois elementos quaisquer do conjunto $\{6k+1:k\in \mathbb {Z} \}$ é ainda um elemento deste conjunto.
** O conjunto $\{6k+5:k\in \mathbb {Z} \}$ 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
### Definição

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

### Exemplos
#### Quem são os divisores comuns de a e b?

O conjunto formado pelos divisores comuns de $a$ e $b$ será denotado por $D(a,b)$.
No primeiro capítulo, mostrou-se que o número $1$ é divisor de qualquer número inteiro. Em particular, se forem escolhidos números $a$ e $b$, certamente $1$ será um divisor comum de ambos.
Logo, o conjunto $D(a,b)$ é não vazio, pois $1\in D(a,b)$.

#### O maior dos divisores comuns

Se $a\neq 0$ e $d$ for um divisor comum de $a$ e de $b$, então $|d|\leq |a|$. Logo o conjunto $D(a,b)$ é limitado superiormente e deve ter um elemento máximo, ou seja, existe um divisor comum de $a$ e $b$ maior que todos os demais. Analogamente, para $b\neq 0$, o conjunto $D(a,b)$ também tem um elemento máximo. O único caso que $D(a,b)$ não é limitado superiormente é o conjunto $D(0,0)$, já que zero é múltiplo de qualquer inteiro não-nulo.
Isso motiva a próxima definição.

### Definição de MDC
#### Definição

O máximo divisor comum (abreviadamente MDC) entre dois números inteiros $a$ e $b$, em que pelo menos um deles não é zero, é o maior elemento do conjunto $D(a,b)$, e será denotado por $mdc(a,b)$, ou simplesmente $(a,b)$.
Quando o conjunto $D(a,b)$ possui apenas um elemento positivo, ou seja, quando $(a,b)=1$, os números $a$ e $b$ são ditos primos entre si, relativamente primos ou simplesmente co-primos.

#### Exemplo

Qual é o máximo divisor comum entre $12$ e $15$?
Considerando que os divisores de $12$ são os elementos do conjunto $D(12)=\{\pm 1,\pm 2,\pm 3,\pm 4,\pm 6,\pm 12\}$ e que os divisores de $15$ formam o conjunto $D(15)=\{\pm 1,\pm 3,\pm 5,\pm 15\}$, tem-se que $D(12,15)=\{\pm 1,\pm 3\}$, cujo maior elemento é $3$. Portanto, $mdc(12,15)=3$.
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 $\{ax+by:x,y\in \mathbb {Z} \}$. 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
### Teorema

Se $d=mdc(a,b)$, então existem inteiros $x$ e $y$ tais que $d=ax+by$.
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
#### Corolário

Se $m|ab$ e $mdc(a,m)=1$ então $m|b$.
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
#### Teorema

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

### Demonstração do teorema de Bézout

Uma observação crucial para a demonstração do teorema de Bézout é que, para quaisquer números inteiros $a,b$, tem-se a igualdade $(a,b)=(a-b,b)$.
De fato, para que tal propriedade se verifique, é suficiente que os conjuntos $D(a,b)$ e $D(a-b,b)$ 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 $d\in D(a,b)$, então $d|a$ e $d|b$.
Donde, $d|a-b$.
Assim, $d\in D(a-b,b)$.
* Reciprocamente, se $d\in D(a-b,b)$, então $d|a-b$ e $d|b$. Logo, deve dividir a soma:
    $d|(a-b)+b=a$,
ou seja, $d\in D(a,b)$.
Outra propriedade do máximo divisor comum é a seguinte:
    $(b,a)=(a,b)=(-a,b)=(a,-b)$
Por causa dela, pode ser suposto que $a\geq b\geq 0$, e obter a demonstração:
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 $(a,b)$:

### Exemplos numéricos

Usando o procedimento sugerido, pode-se calcular $(30,18)$ facilmente. Acompanhe:
    $(30,18)=(12,18)=(18,12)=(6,12)=(6,6)=(0,6)=(6,0)=6$
No entanto, quando se tem $a$ bem maior que $b$, a igualdade mais utilizada será $(a,b)=(a-b,b)$.
Por exemplo, se $a=100$ e $b=3$ as etapas serão:
    $(100,3)=(97,3)=(94,3)=\ldots =(4,3)=(1,3)$ $=(3,1)=(2,1)=(1,1)=(0,1)=(1,0)=1$
Neste caso, parece razoável subtrair $3$ de $100$ tantas vezes quanto for possível, em uma única etapa:
    $(100,3)=(100-3\cdot 33,3)=(1,3)=1$
Em geral, será buscado um valor $q$ tal que $0\leq a-bq<b$, pois assim a igualdade $(a,b)=(a-bq,b)$ (que é sempre verdadeira, para qualquer valor inteiro de $q$) reduz o cálculo de $(a,b)$ a um caso bem mais simples.
A existência de um número $q$, 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

* 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 $a,b\in \mathbb {Z}$, com $a\geq b\geq 0$, verifique se $b=0$. Em caso afirmativo, o máximo divisor comum é o próprio $a$. Caso contrário, repita o processo usando $b$ e o resto da divisão de $a$ por $b$. Simbolicamente: Dados de entrada Os inteiros $a$ e $b$.
Saída $(a,b)$.
Procedimento * Se $a<b$, então $(a,b)=(b,a)$; * Se $b=0$, então $(a,b)=a$; * Senão $(a,b)=(a-bq,b)$, onde $0\leq a-bq<b$
Observe que esta é simplesmente uma generalização do algoritmo apresentado logo após a demonstração do teorema de Bézout.
É preciso verificar que o algoritmo irá parar, e ainda mais importante, que fornecerá a resposta correta.
Considere $r_{0}=a$ e $r_{1}=b$, e a seguinte sequência de igualdades (obtidas pelo algoritmo da divisão):
    $r_{0}=$$r_{1}q_{0}+r_{2}$$0\leq r_{2}<r_{1}$ $r_{1}=$$r_{2}q_{1}+r_{3}$$0\leq r_{3}<r_{2}$ $\vdots$ $r_{k-2}=$$r_{k-1}q_{k-2}+r_{k}$$0\leq r_{k}<r_{k-1}$ $r_{k-1}=$$r_{k}q_{k-1}+r_{k+1}$$0\leq r_{k+1}<r_{k}$ $\vdots$
Juntando as desigualdades anteriores, tem-se uma sequência decrescente de números não negativos:
    $r_{1}>r_{2}>r_{3}>\ldots >r_{k}>\ldots \geq 0$
No entanto, só existe uma quantidade finita de números positivos menores que $r_{1}$. Logo, depois de algum resto $r_{k}$, tem-se $r_{k+1}=0$, ou seja:
    $r_{1}>r_{2}>r_{3}>\ldots >\mathbf {r_{k}} >r_{k+1}=0$
É nesse ponto que o algoritmo para: quando o resto $r_{k+1}=0$. Segundo o enunciado, o resultado fornecido será então $r_{k}$.
Será que este é realmente o valor de $(a,b)$?
A resposta é sim, pois $(a,b)=(a-b,b)=(a-2b,b)=(a-3b,b)=\ldots =(a-bq,b)$.
Logo, obtem-se sucessivamente:
    $(a,b)=(r_{0},r_{1})=(r_{1},r_{2})=\ldots =(\mathbf {r_{k}} ,r_{k+1})=(\mathbf {r_{k}} ,0)=\mathbf {r_{k}}$
Portanto o valor fornecido pelo algoritmo corresponde a $(a,b)$, e foi obtido através de exatamente $k$ divisões.

### Exemplo numérico

Quanto é $(30,18)$?
Aplicando o processo usado na demonstração do algoritmo de Euclides para o MDC, tem-se:
    $30=18\cdot 1+12$
    $18=12\cdot 1+\mathbf {6}$
    $12=\mathbf {6} \cdot 2+0$
Logo, $(30,18)=6$.
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 112 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

Na demonstração de que o algoritmo de Euclides funciona, aparecem várias igualdades da forma:
    $r_{j-1}=r_{j}q_{j-1}+r_{j+1}$
O índice $j$ indica que esta é a $j$-é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:
    ${\begin{bmatrix}r_{j-1}\\r_{j}\end{bmatrix}}={\begin{bmatrix}q_{j-1}&1\\1&0\end{bmatrix}}\cdot {\begin{bmatrix}r_{j}\\r_{j+1}\end{bmatrix}}$, sempre que $1\leq j\leq k$
Com essa notação, os cálculos que aparecem no algoritmo de Euclides para o MDC tornam-se mais sucintos. Por exemplo:
    ${\begin{bmatrix}r_{0}\\r_{1}\end{bmatrix}}$ $={\begin{bmatrix}q_{0}&1\\1&0\end{bmatrix}}\cdot {\begin{bmatrix}r_{1}\\r_{2}\end{bmatrix}}$ $={\begin{bmatrix}q_{0}&1\\1&0\end{bmatrix}}\cdot \overbrace {{\begin{bmatrix}q_{1}&1\\1&0\end{bmatrix}}\cdot {\begin{bmatrix}r_{2}\\r_{3}\end{bmatrix}}}$ $={\begin{bmatrix}q_{0}&1\\1&0\end{bmatrix}}\cdot {\begin{bmatrix}q_{1}&1\\1&0\end{bmatrix}}\cdot \overbrace {{\begin{bmatrix}q_{2}&1\\1&0\end{bmatrix}}\cdot {\begin{bmatrix}r_{3}\\r_{4}\end{bmatrix}}}$
Para facilitar ainda mais a escrita, pode-se adotar a seguinte convenção:
    $Q_{j}={\begin{bmatrix}q_{j}&1\\1&0\end{bmatrix}}$
Se o cálculo anterior for efetuado para todas as etapas do algoritmo, o resultado final será:
    ${\begin{bmatrix}r_{0}\\r_{1}\end{bmatrix}}=Q_{0}\cdot Q_{1}\cdot \ldots \cdot Q_{k-1}\cdot {\begin{bmatrix}d\\0\end{bmatrix}}=M\cdot {\begin{bmatrix}d\\0\end{bmatrix}}$, sendo que $d=(a,b)$.
Perceba que assim não há uma confusão tão grande com os índices dos sucessivos quocientes e restos.
Como a matriz $M$ é um produto de matrizes com entradas inteiras e não-negativas, nenhuma de suas entradas deverá ser negativa. Assim, é possível escrever $M$ da seguinte forma:
    $M={\begin{bmatrix}a'&u\\b'&v\end{bmatrix}}$, com $a',b',u,v\in \mathbb {N}$
Disso se conclui que
    ${\begin{bmatrix}r_{0}\\r_{1}\end{bmatrix}}={\begin{bmatrix}a\\b\end{bmatrix}}={\begin{bmatrix}a'&u\\b'&v\end{bmatrix}}\cdot {\begin{bmatrix}d\\0\end{bmatrix}}={\begin{bmatrix}a'd\\b'd\end{bmatrix}}$
Escrevendo $\Delta =det(M)=a'v-b'u$, tem-se
    $\Delta =det(Q_{0}\cdot Q_{1}\cdot \ldots \cdot Q_{k-1})=det(Q_{0})\cdot det(Q_{1})\cdot \ldots \cdot det(Q_{k-1})=(-1)^{k}$, pois cada matriz $Q_{i}$ tem determinante igual a $-1$.
Logo, a matriz $M$ é invertível e $M^{-1}={\frac {1}{\Delta }}{\begin{bmatrix}v&-u\\-b'&a'\end{bmatrix}}=\Delta {\begin{bmatrix}v&-u\\-b'&a'\end{bmatrix}}$. Esta última igualdade se justifica pois $\Delta =\Delta ^{-1}$.
Dessas considerações, resulta que:
    ${\begin{bmatrix}d\\0\end{bmatrix}}=M^{-1}{\begin{bmatrix}a\\b\end{bmatrix}}=\Delta {\begin{bmatrix}v&-u\\-b'&a'\end{bmatrix}}\cdot {\begin{bmatrix}a\\b\end{bmatrix}}$
Fazendo o produto, e igualando cada componente, conclui-se que:
$\left\{{\begin{matrix}d&=&a(\Delta v)+b(-\Delta u)\\0&=&\Delta (-b'a+a'b)\\\end{matrix}}\right.$
A primeira destas equações corresponde ao teorema de Bézout, com $x=\Delta v$ e $y=-\Delta u$. Já a segunda, implica em $b'a=a'b$. Esse valor coincide com o conhecido mínimo múltiplo comum entre $a$ e $b$, definido a seguir:

#### Definição

O mínimo múltiplo comum dos inteiros $a$ e $b$, $mmc(a,b)$, é o menor elemento positivo do conjunto $M(a,b)=\{x\in \mathbb {Z} :a,b|x\}$
Segundo o comentário que precede esta definição, tem-se:
    $mmc(a,b)={\frac {ab}{(a,b)}}$

#### Exemplificando

Anteriormente foi visto que:
    $30=18\cdot \mathbf {1} +12$
    $18=12\cdot \mathbf {1} +6$
    $12=6\cdot \mathbf {2} +0$
Utilizando esses valores, segue que:
    ${\begin{bmatrix}30\\18\end{bmatrix}}=\overbrace {{\begin{bmatrix}\mathbf {1} &1\\1&0\end{bmatrix}}\cdot {\begin{bmatrix}\mathbf {1} &1\\1&0\end{bmatrix}}\cdot {\begin{bmatrix}\mathbf {2} &1\\1&0\end{bmatrix}}} \cdot {\begin{bmatrix}6\\0\end{bmatrix}}={\begin{bmatrix}5&2\\3&1\end{bmatrix}}\cdot {\begin{bmatrix}6\\0\end{bmatrix}}$.
Para este exemplo, a matriz inversa é
    $M^{-1}=(-1)^{3}{\begin{bmatrix}1&-2\\-3&5\end{bmatrix}}={\begin{bmatrix}-1&2\\3&-5\end{bmatrix}}$
Logo,
    ${\begin{bmatrix}6\\0\end{bmatrix}}={\begin{bmatrix}-1&2\\3&-5\end{bmatrix}}\cdot {\begin{bmatrix}30\\18\end{bmatrix}}={\begin{bmatrix}-1\cdot 30&2\cdot 18\\3\cdot 30&-5\cdot 18\end{bmatrix}}$, ou seja
* $(30,18)=6=30\cdot (-1)+18\cdot 2$
* $mmc(30,18)=3\cdot 30=-5\cdot 18=90$
Note que, quando $a,b$ são positivos, a expressão $d=a(\Delta v)+b(-\Delta u)=ax+by$ deve ter exatamente um dos valores $x,y$ menor que zero, para que a combinação linear de $a,b$ não seja maior que qualquer um deles.
Considere uma outra situação: como encontrar o mínimo múltiplo comum entre $7$ e $5$?
Primeiramente, pelo algoritmo de Euclides tem-se:
    $7=5.1+2$
    $5=2.2+1$
    $2=1.2+0$
Logo $mdc(7,5)=1.$
Daí tem-se que $\textstyle mmc(7,5)={\frac {7\times 5}{1}}=35.$

## Uma demonstração alternativa do teorema de Bézout

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.

## Exercícios

* O algoritmo da divisão estabelece que dados os inteiros $a,b$, existem inteiros $q,r$ tais que $a=bq+r$, com $0\leq r<b$. Utilize uma calculadora comum (e apenas as quatro operações elementares) para obter os valores de $q,r$ correspondentes a alguns pares de inteiros $a,b$.
* 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:
** a = 299 e b = 161
** a = 435 e b = 232
** a = 101 e b = 33
** a = 145 e b = 48

## Ver também
### Wikipedia

* Máximo divisor comum

# Bibliografia
## Livros em português

* Coutinho, Severino Coullier. Números inteiros e criptografia RSA. Rio de Janeiro: IMPA, 2005. 226 p. ISBN 8524401249
    Neste livro são tratados os tópicos de teoria de números que são essenciais para a compreensão do método de criptografia RSA. A forma de exposição do conteúdo procura evitar o padrão "Definição, Teorema, Demonstração", que é usado em muitos livros de matemática.
* Hefez, Abramo. Curso de álgebra. 3ª.ed. Rio de Janeiro: IMPA, 2002. 226 p. ISBN 852440079X
* Milies, César Polcino, Coelho, Sônia Pitta. Números: Uma introdução à Matemática. 3ª.ed. São Paulo: Editora da Universidade de São Paulo, 2003. ISBN 8531404584
* Moreira, Carlos Gustavo Tamm de Araujo, Saldanha, Nicolau C. Primos de Mersenne: e outros primos muito grandes. IMPA, 1999. 81 p. v. 1. ISBN 8524401494
* Brochero Martínez, Fabio , Moreira, Carlos Gustavo , Saldanha, Nicolau, Tengan, Eduardo. Teoria dos Números: um passeio com primos e outros números familiares pelo mundo inteiro. IMPA, 2010. 450 p. v. 1. ISBN 8524403125
* Ribenboim, Paulo. Números primos: Mistérios e records. Rio de Janeiro: IMPA, 2001. 292 p. ISBN 8524401680
* Santos, José Plínio de Oliveira. Introdução à Teoria dos Números. Rio de Janeiro: IMPA, 2007. 198 p. ISBN 9788524401428

## Livros em inglês

* Apostol, Tom M.. Introduction to Analytic Number Theory. Springer, 1976. 352 p. ISBN 0387901639
* Cassels, J. W. S.. An introduction to diophantine aproximations. Cambridge University Press, 1957.
* Cohn, Harvey. A Second Course in Number Theory. New York: John Wiley & Sons, 1962. 276 p.
* Dickson, Leonard Eugene. History of the theory of numbers: Divisibility and Primality. American Mathematical Society, 1966. 486 p. ISBN 0821819348
* Gauss, Carl Friedrich. Disquisitiones Arithmeticae. Springer, 1986. 472 p. ISBN 0387962542
* Goldman, Jay R.. The Queen of Mathematics: An Historically Motivated Guide to Number Theory. A.K. Peters, 1998. 525 p. ISBN 1568810067
* Guy, Richard K.. Unsolved Problems in Number Theory. 3ª.ed. Springer, 2004. 437 p. v. 1. ISBN 0387208607
* Hardy, G. H., Wright, Edward Maitland. An Introduction to the Theory of Numbers. 5ª.ed. Oxford University Press, 1979. 456 p. ISBN 0198531710
* Honsberger, R.. A Theorem of Gabriel Lamé: Ch. 7 in Mathematical Gems II. Washington, DC: Math. Assoc. Amer., 1976. 54-57 p. ISBN 0883853027
* Ireland, Kenneth F., Rosen, Michael. A Classical Introduction to Modern Number Theory. Springer, 1990. ISBN 038797329X
* Jones, Gareth A., Jones, Josephine Mary. Elementary Number Theory. Springer, 1998. 301 p. ISBN 3540761977
* Knuth, Donald. The Art of Computer Programming: Seminumerical Algorithms. 3ª.ed. Addison-Wesley, 1997. v. 2. ISBN 0201896842
* LeVeque, William Judson. Fundamentals of Number Theory. Dover, 1996. 288 p. ISBN 0486689069
* Matiyasevich, Yuri V.. Hilbert's Tenth Problem. MIT Press, 1993. 288 p. ISBN 0262132958
* Niven, Herbert Ivan, Zuckerman, Herbert S.. Introduction to the Theory of Numbers. John Wiley & Sons, 1968. 296 p. ISBN 0471641537
* Ribenboim, Paulo. The New Book of Prime Number Records. Springer, 1996. 572 p. ISBN 0387944575
* Saidak, Filip. A New Proof of Euclid's Theorem, Amer. Math. Monthly 113, no. 10, 937--938. 2006.
* Sierpiński, Wacław. 250 Problems in Elementary Number Theory. American Elsevier Pub. Co., 1970. 125 p. ISBN 0444000712
* Stewart, Ian. Algebraic Number Theory and Fermat's Last Theorem. A K Peters, Ltd., 2002. ISBN 1568811195
* Vinogradov, Ivan Matveevich. Elements of number theory. Courier Dover Publications, 2003. 240 p. ISBN 0486495302

## Outras referências

* The Elements of Euclid, por Isaac Todhunter - Disponível no Wikisource
* Jurkiewicz, Samuel. Divisibilidade e Números Inteiros: Introdução à Aritmética Modular. Apostila 1 do estágio para bolsistas da OBMEP.
* Neves, Vítor. Introdução à Teoria dos Números. Universidade de Aveiro. 2001.
* Weisstein, Eric W. Lamé's Theorem. From MathWorld - A Wolfram Web Resource.
* Viggo Brun. Euclidean algorithms and musical theory. Enseignement Mathématique, 10:125–137, 1964.
* Toussaint, Godfried. The Euclidean Algorithm Generates Traditional Musical Rhythms.
* Shoup, Victor. A Computational Introduction to Number Theory and Algebra (Version 1) - Um eBook disponibilizado sob a Creative Commons license (Attribution-NonCommercial-NoDerivs 2.0).

# 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

Recorde-se que o algoritmo baseia-se na construção da sequência:
    $a=r_{0}\geq b=r_{1}>r_{2}>\ldots >r_{k}>r_{k+1}=0$
cujos termos verificam as seguintes igualdades:
| 1 | $r_{0}=$ | $r_{1}q_{0}+r_{2}$ | $0\leq r_{2}<r_{1}$ |
| 2 | $r_{1}=$ | $r_{2}q_{1}+r_{3}$ | $0\leq r_{3}<r_{2}$ |
| | $\vdots$ | | |
| k-1 | $r_{k-2}=$ | $r_{k-1}q_{k-2}+r_{k}$ | $0\leq r_{k}<r_{k-1}$ |
| k | $r_{k-1}=$ | $r_{k}q_{k-1}+r_{k+1}=r_{k}q_{k-1}$ | pois $0=r_{k+1}<r_{k}$ |
O algoritmo fornece $(a,b)=r_{k}$, que é o último resto não nulo, obtido em $k$ passos (divisões).
Uma observação importante é que o resto de uma divisão é sempre menor que a metade do dividendo:
    $r_{0}=r_{1}q_{0}+r_{2}\geq r_{1}+r_{2}>2r_{2}$
Sendo a primeira desigualdade válida porque $q_{0}\geq 1$ e a segunda porque $r_{1}>r_{2}$. Deste modo, tem-se
    $r_{0}>2r_{2}$
    $r_{1}>2r_{3}$
    $r_{2}>2r_{4}$
    $r_{3}>2r_{5}$
e em geral
    $r_{k}>2r_{k+2}$, para cada $k\geq 0$.
Assim, comparando os termos cujos índices são pares, segue:
    $r_{0}<a/2$
    $r_{2}<r_{0}/2<a/4$
    $r_{4}<r_{2}/2<r_{0}/4<a/8$
    $\ldots$
Por indução, resulta para cada termo:
    $r_{2j}<a/2^{j+1}$
De modo análogo, ao comparar os termos ímpares, e usar novamente indução, segue:
    $r_{2j+1}<a/2^{j+1}$
Com isso, a sequência dos $r_{j}$ decresce geometricamente, pois $a$ está fixado. O fato de ser uma sequência decrescente já havia sido demonstrado quando se justificou o funcionamento do algoritmo de Euclides. A novidade aqui é a velocidade com que a sequência decresce. Pelos cálculos anteriores, os restos diminuem, no mínimo, tão rápido quanto os termos da progressão geométrica $(a,{\frac {a}{2}},{\frac {a}{4}},{\frac {a}{8}},{\frac {a}{16}},\ldots )$.
A questão colocada era: Quantas divisões são necessárias para que o resto $r_{k+1}$ seja zero?
Analisando a progressão geométrica dada anteriormente, conclui-se que algum de seus termos é menor do que $1$. Nesse caso, o resto correspondente será nulo, e o algoritmo para. Para ser mais exato, como
    ${\frac {a}{2^{x}}}<1\Leftrightarrow a<2^{x}\Leftrightarrow \log _{2}a<x$
o menor índice inteiro $t$ que torna ${\frac {a}{2^{t}}}$ menor que $1$ é
    $t=\lfloor \log _{2}a\rfloor +1$
Onde $\lfloor \alpha \rfloor$ denota o maior inteiro que não supera $\alpha$ (a parte inteira de $\alpha$).
Então $r_{2t}<{\frac {a}{2^{t+1}}}<{\frac {a}{2^{t}}}<1$, e consequentemente $r_{2t}=0$, pois os restos são números inteiros não-negativos.
Assim, sabendo que o algoritmo para exatamente quando $r_{k+1}=0$, conlui-se que tal índice $k+1$ não pode ser maior que $2t$, em símbolos:
    $k+1\leq 2(\lfloor \log _{2}a\rfloor +1)$
Para melhor compreender o significado dessa estimativa, considere que $a$ tem $N$ dígitos decimais. Então:
    $10^{N-1}\leq a<10^{N}$
Aplicando o logaritmo em ambos os membros da segunda desigualdade, resulta
    $\log _{2}a<N\cdot \log _{2}10$
Logo, $k+1\leq 2(\lfloor \log _{2}a\rfloor +1)<2N\cdot \log _{2}10+2$, que para valores grandes de $N$ é aproximadamente $6,6N$.
Embora esta não seja a melhor aproximação para $k$, já é bastante útil, pois mostra que o número de etapas cresce linearmente com o número de dígitos de $a$.

### O pior caso

Para obter uma estimativa mais precisa do número de etapas que o algoritmo de Euclides leva para determinar o MDC de dois números, será considerada a seguinte questão:
    Qual é o menor valor de $a$ para o qual o algoritmo leva $n$ passos?
Veja alguns exemplos utilizando a representação matricial do algoritmo:
Para $n=1$:
    ${\begin{bmatrix}a\\b\end{bmatrix}}={\begin{bmatrix}q_{0}&1\\1&0\end{bmatrix}}\cdot {\begin{bmatrix}d\\0\end{bmatrix}}$
Para $n=2$:
    ${\begin{bmatrix}a\\b\end{bmatrix}}={\begin{bmatrix}q_{0}&1\\1&0\end{bmatrix}}\cdot {\begin{bmatrix}q_{1}&1\\1&0\end{bmatrix}}\cdot {\begin{bmatrix}d\\0\end{bmatrix}}={\begin{bmatrix}q_{0}q_{1}+1&q_{0}\\q_{1}&1\end{bmatrix}}\cdot {\begin{bmatrix}d\\0\end{bmatrix}}$
Para $n=3$:
    ${\begin{bmatrix}a\\b\end{bmatrix}}={\begin{bmatrix}q_{0}q_{1}+1&q_{0}\\q_{1}&1\end{bmatrix}}\cdot {\begin{bmatrix}q_{2}&1\\1&0\end{bmatrix}}\cdot {\begin{bmatrix}d\\0\end{bmatrix}}={\begin{bmatrix}q_{0}q_{1}q_{2}+q_{0}+q_{2}&q_{0}q_{1}+1\\q_{1}&1\end{bmatrix}}{\begin{bmatrix}d\\0\end{bmatrix}}$
É fácil perceber que $a$ é mínimo quando os valores $q_{0},\ldots ,q_{k-1}$ forem todos iguais a $1$, cada entrada da matriz é um polinômio nas variáveis $q_{j}$ (que são positivas), e cujos coeficiêntes são $1$ (se puder, acrescente uma justificativa mais formal).
Se cada quociente for substituído por $1$ na fórmula de recorrência
    $r_{j-1}=r_{j}q_{j-1}+r_{j+1}$
Esta passará a ser:
    $r_{j-1}=r_{j}+r_{j+1}$
Que vale para $j$ satisfazendo $1\leq j\leq k$.
A nova relação lembra a fórmula que define a sequência de Fibonacci, embora esteja "ao contrário".
Matricialmente, as condições $q_{0}=1,\ldots ,q_{k-1}=1$ produzem as seguintes igualdades:
    ${\begin{bmatrix}a\\b\end{bmatrix}}=\overbrace {{\begin{bmatrix}\mathbf {1} &1\\1&0\end{bmatrix}}\cdot {\begin{bmatrix}\mathbf {1} &1\\1&0\end{bmatrix}}\cdot \ldots \cdot {\begin{bmatrix}\mathbf {1} &1\\1&0\end{bmatrix}}} \cdot {\begin{bmatrix}d\\0\end{bmatrix}}={\begin{bmatrix}\mathbf {1} &1\\1&0\end{bmatrix}}^{k+1}\cdot {\begin{bmatrix}d\\0\end{bmatrix}}$, sendo que $d=(a,b)$.
Com um simples uso do princípio de indução finita, consegue-se:
    ${\begin{bmatrix}\mathbf {1} &1\\1&0\end{bmatrix}}^{n}={\begin{bmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{bmatrix}}$, desde que $n\geq 1$.
Deste modo,
    ${\begin{bmatrix}a\\b\end{bmatrix}}={\begin{bmatrix}F_{k+2}&F_{k+1}\\F_{k+1}&F_{k}\end{bmatrix}}\cdot {\begin{bmatrix}d\\0\end{bmatrix}}={\begin{bmatrix}d\cdot F_{k+2}\\d\cdot F_{k+1}\end{bmatrix}}$
Como $d=(a,b)\geq 1$, segue que
* $a\geq F_{k+2}$
* $b\geq F_{k+1}$

#### Teorema

Dado $n\geq 1$, sejam $a$ e $b$ os menores números tais que o algoritmo de Euclides aplicado a $a$ e $b$ leva exatamente $n$ passos, então $a=F_{n+2}$ e $b=F_{n+1}$.

#### Exemplificando

Para determinar o valor de $(F_{7},F_{6})=(13,8)$, seria necessário efetuar cinco divisões:
    $13=8\cdot 1+5$ $8=5\cdot 1+3$ $5=3\cdot 1+2$ $3=2\cdot 1+\mathbf {1}$ $2=\mathbf {1} \cdot 2+0$
Logo, $(13,8)=1$. Aproveitando este exemplo, observe que:
    ${\begin{bmatrix}13\\8\end{bmatrix}}={\begin{bmatrix}13&8\\8&5\end{bmatrix}}\cdot {\begin{bmatrix}1\\0\end{bmatrix}}={\begin{bmatrix}F_{5+2}&F_{5+1}\\F_{5+1}&F_{5}\end{bmatrix}}\cdot {\begin{bmatrix}1\\0\end{bmatrix}}={\begin{bmatrix}1&1\\1&0\end{bmatrix}}^{5+1}\cdot {\begin{bmatrix}1\\0\end{bmatrix}}$
No entanto, se qualquer dos números for menor, o algoritmo requer menos etapas. Por exemplo, ao determinar $(13,7)$ tem-se:
    $13=7\cdot 1+6$ $7=6\cdot 1+\mathbf {1}$ $6=\mathbf {1} \cdot 6+0$
Donde, $(13,7)=1$.
Já o cálculo de $(12,8)$ é ainda mais simples:
    $12=8\cdot 1+\mathbf {4}$ $8=\mathbf {4} \cdot 2+0$
Portanto, $(12,8)=4$.

## Melhorando as estimativas

Sabendo qual é o pior caso para a aplicação do algoritmo de Euclides, pode-se deduzir uma melhor estimativa de sua eficiência. Uma análise mais elaborada que aquela apresentada no início do capítulo fornece o seguinte resultado:

### Teorema de Lamé
#### Teorema

O número de passos (de divisões) no algoritmo de Euclides com entradas $u$ e $v$ é limitado superiormente por $5$ vezes a quantidade de dígitos decimais em $min(u,v)$.
Para demonstrar o teorema de Lamé, é importante ter em mente algumas propriedades relacionadas a sequência de Fibonacci e ao número de ouro:
    $\varphi ={\frac {1+{\sqrt {5}}}{2}}\approx 1.618$
Tem-se:
* $\varphi ^{2}=\varphi +1$
* $F_{n}={\frac {\varphi ^{n}}{\sqrt {5}}}$, arredondado para o inteiro mais próximo.
* $F_{n}\geq \varphi ^{n-1}$
* $\log \varphi <{\frac {1}{5}}$
Como foi visto anteriormente, quando $(a,b)$ é exige exatamente $n$ passos, é tem-se $a\geq F_{n}+2$ e $b\geq F_{n}+1$. Logo,
    $a\geq F_{n}+2\geq \varphi ^{n+1}$
Aplicando o logaritmo em ambos os menbros, segue:
    $(n+1)\log \varphi \leq \log a$
ou seja
    $n\leq {\frac {\log a}{\log \varphi }}=\log _{\varphi }a$
Mas ${\frac {1}{\log \varphi }}<5$, então:
    $n\leq {\frac {1}{\log \varphi }}\cdot \log a<5\log _{\varphi }a<5N$, onde $N$ é o número de dígitos de $a$

## Demonstração da fórmula de Binet

Nesta seção, será deduzida a fórmula de Binet:
    $F_{n}={\frac {1}{\sqrt {5}}}\left(\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}\right)={\frac {\varphi ^{n}-{\hat {\varphi }}^{n}}{\sqrt {5}}}$
onde $\varphi ={\frac {1+{\sqrt {5}}}{2}}$ e ${\hat {\varphi }}={\frac {1-{\sqrt {5}}}{2}}$.
A principal razão para se utilizar está fórmula, em vez da definição recursiva da sequência de Fibonacci, é que ela permite a obtenção de um termo da sequência sem precisar calcular os anteriores.

## Exercícios

* Verifique, utilizando o princípio de indução, que:
    ${\begin{bmatrix}F_{n+1}\\F_{n}\end{bmatrix}}={\begin{bmatrix}1&1\\1&0\end{bmatrix}}^{n}\cdot {\begin{bmatrix}F_{1}\\F_{0}\end{bmatrix}}$
* Escreva outra demonstração para a fórmula de Binet, utilizando o princípio de indução.
Por enquanto, não há muitos exercícios sobre este capítulo. O leitor está convidado a adicionar mais ítens a essa seção, para ajudar a melhorar o texto.

# Equações diofantinas

Neste capítulo serão estudados certos problemas cuja solução envolve conceitos da teoria de números que foram tratados nos capítulos anteriores.
Considere o seguinte problema:
Matematicamente, o que se quer saber é:
Em geral, as equações que surgem no contexto da teoria de números devem ser resolvidas no conjunto dos números inteiros. Este tipo de equação é conhecido como equação diofantina.

## As equações diofantinas lineares

A equação que surgiu do exemplo apresentado no início do capítulo é apenas um caso particular da seguinte: $ax+by=n.$ Aqui, os inteiros $a$ e $b$ são fixados.
Quando é que tal equação possui solução?
O próximo teorema responde exatamente essa pergunta.

### Teorema

Dados $a,b\in \mathbb {Z} ,$ existem $x,y\in \mathbb {Z}$ tais que $ax+by=n$ se, e somente se, $d=(a,b)|n.$
Além disso, se $(x_{0},y_{0})$ é solução, então todas as soluções são da forma: $x=x_{0}-b't$ e $y=y_{0}+a't,$ onde $a=a'd$ e $b=b'd.$
Assim como acontece em problemas que envolvem equações diferenciais, para determinar o conjunto solução de uma equação diofantina, encontra-se primeiramente uma solução particular, e combina-se a mesma com a solução da equação homogênea (no caso, $ax+by=0$)
Agora é possível resolver o problema proposto no início.

### Aplicação

Será que existem números inteiros $x,y,n$ que verificam $2x+5y=n?$
Conforme o teorema indica, para que exista uma solução (e portanto infinitas) é preciso que $,mdc(2,5)|n.$
Pelo algoritmo de Euclides obtem-se $mdc(2,5)=1,$ além de $2\cdot (-2)+5\cdot 1=1.$ Multiplicando ambos os membros por $n,$ segue que:
    $2\cdot (-2n)+5\cdot n=n$
Assim, as demais soluções são da forma:
* $x=-2n+5t$
* $y=n-2t$
No contexto em que o problema foi colocado, é exigido que as soluções não sejam números negativos. Disto seguem as seguintes restrições:
* $-2n+5t\geq 0$
* $n-2t\geq 0$
que são equivalentes a
    ${\frac {2}{5}}n\leq t\leq {\frac {n}{2}}$
Para que exista algum valor inteiro $t$ nesse intervalo, é suficiente que ${\frac {n}{2}}-{\frac {2}{5}}n\geq 1,$ ou seja,
    $n=5n-4n\geq 10$
Note que a condição anterior é suficiente, mas não necessária, pois para alguns valores de $n<10$ também há soluções:
* $4=2+2$
* $5=5+0$
* $6=2+2+2$
* $7=5+2$
* $8=2+2+2+2$
* $9=5+2+2$
A conclusão final é que, utilizando apenas notas de $2$ e de $5$ é possível obter qualquer valor inteiro maior que ou igual a $4.$

### Interpretação geométrica

Sabe-se que o conjunto dos pontos $(x,y)$ (com coordenadas reais) que verificam a equação $d=ax+by$ é representado por uma reta sobre o plano cartesiano. Então as soluções da equação diofantina $d=ax+by,$ são representadas pelos pontos da reta que possuem ambas as coordenadas inteiras.

## Diferença de quadrados

Um outro problema que pode ser tratado com as ferramentas desenvolvidas até agora é a busca de soluções inteiras para a seguinte equação:
    $n=x^{2}-y^{2}$
Buscar tais soluções significa determinar se existe algum inteiro $n$ que pode ser escrito como soma de dois quadrados perfeitos. Se a resposta for afirmativa, será interessante saber exatamente quais são os números inteiros $n$ que são soma de quadrados.
Estes são alguns exemplos desse tipo de problema:
* $x^{2}-y^{2}=30$ tem soluções inteiras?
* $x^{2}-y^{2}=32$ tem soluções inteiras?
Para poder entender a estratégia para a resolução desse tipo de problema, considere que a segunda equação tenha alguma solução $x,y:$
    $32=x^{2}-y^{2}$
O que se pode afirmar sobre esses dois números inteiros?
Primeiramente, deve valer $32=x^{2}-y^{2}=(x+y)(x-y),$ ou seja, a soma e a diferença das soluções devem ser divisores de $32.$ Sabe-se, por exemplo, que $32=8\cdot 4.$ Será que existem inteiros $x,y$ tais que
* $x+y=8$
* $x-y=4$
Por inspeção, percebe-se que $x=6$ e $y=2$ servem, logo $32=6^{2}-2^{2}=36-4.$
E quanto ao outro problema?
É possível encontrar um par de divisores de $30$ (por exemplo, $d$ e ${\frac {30}{d}}$) tais que um seja a soma, e outro a diferença das soluções?
Observe:
    Divisores de $30$ $d$${\frac {30}{d}}$ $1$$30$ $2$$15$ $3$$10$ $5$$6$
Você é capaz de encontrar alguma linha dessa tabela contendo a soma e a diferença de dois números inteiros? Justifique.
Em vez de continuar tratando o problema baseando-se em exemplos particulares, considere que existem $x,y$ satisfazeno a equação em sua forma geral:
    $n=x^{2}-y^{2}$
Conforme anteriormente, conclui-se que, para alguma escolha de $u,v,$ tais que $n=u\cdot v,$ tem-se $u=x+y$ e $v=x-y,$ ou seja, para tais divisores de $n$ existe uma solução $x,y$ para o sistema:
    $\left\{{\begin{matrix}x+y&=&u\\x-y&=&v\\\end{matrix}}\right.$
Equivalentemente, tais inteiros $x,y$ são também solução do sistema:
    $\left\{{\begin{matrix}2x&=&u+v\\2y&=&u-v\\\end{matrix}}\right.$
Se você interpretar essas equações adequadamente, concluirá que $u,v$ devem ter a mesma paridade (ser ambos pares ou ambos ímpares). De fato, se um deles for par e o outro for ímpar, sua soma será um número ímpar, e consequentemente não poderá ser escrita como $2x,$ para nenhum valor inteiro $x.$
Na verdade, com pouca ou nenhuma argumentação extra, prova-se a validade do seguinte teorema

### Teorema
#### Teorema

Um número inteiro $n$ pode ser escrito como a diferença de dois quadrados perfeitos, $n=x^{2}-y^{2},$ se e somente se $n$ é ímpar ou múltiplo de $4.$
Uma forma direta de obter a representação de $n$ como diferença de quadrados é a seguinte:
* Se $n$ é múltiplo de $4.$
    Nessa situação, $n=4k=(k+1)^{2}-(k-1)^{2}.$
* Se $n$ é ímpar.
    Nesse caso, $n=2k+1=(k+1)^{2}-k^{2}.$

### Exemplo

Com esse resultado, conclúi-se que não há solução para o problema dado em um exemplo anterior:
* $x^{2}-y^{2}=30$
De fato, $30$ não é ímpar e nem múltiplo de $4.$
Por outro lado, usando a fórmula anterior, fica fácil resolver:
* $x^{2}-y^{2}=32$
Como $32=4\cdot 8,$ segue que $32=(8+1)^{2}-(8-1)^{2}=81-49$

## Ternos pitagóricos

* Um pouco de história
* Bust of Pythagoras of Samos in the Capitoline Museums, Rome
* Pitágoras foi um matemático e filósofo grego nascido por volta de 570 a.C., na ilha de Samos. Ele é creditado pela demonstração de uma importante relação entre os lados de um triangulo retângulo, hoje conhecida como o teorema de Pitágoras, cujo enunciado é geralmente resumido da seguinte forma:
* O quadrado sobre a hipotenusa é igual à soma dos quadrados sobre os outros dois lados.
Um terno pitagórico é uma tripla de números inteiros $x,y,z$ que satisfazem a equação:
    $x^{2}+y^{2}=z^{2}$
Por exemplo, $3^{2}+4^{2}=5^{2},$ então $3,4,5$ é um terno pitagórico. Obviamente, $0,0,0$ também é um terno pitagórico, mas este último caso é trivial e sem interesse, portanto não será considerado na discussão que segue. O objetivo dessa seção é determinar em que circunstâncias a equação $x^{2}+y^{2}=z^{2}$ tem solução $x,y,z$ não trivial (não todos nulos).
É possível simplificar a investigação, considerando somento o caso em que $x,y,z$ são primos entre si. De fato, se $x=dx',y=dy',z=dz'$ então:
    $(dx')^{2}+(dy')^{2}=(dz')^{2}\Leftrightarrow x'^{2}+y'^{2}=z'^{2}$
Na verdade, se $x,y,z$ for uma solução, então o máximo divisor comum destes números verifica as seguintes igualdades:
    $(x,y,z)=(x,y)=(x,z)=(y,z)$
Em particular, não pode haver $x,y$ não podem ser ambos pares.
Por outro lado, os inteiros $x,y$ também não podem ser ambos ímpares.
    De fato, se assim ocorresse, valeria:
   * $x=2a+1,$ para algum inteiro $a$
   * $y=2b+1,$ para algum inteiro $b$
    Deste modo, elevando cada um destes números ao quadrado, resultaria:
   * $x^{2}=(2a+1)^{2}=4a^{2}+4a+1$ e
   * $x^{2}=(2b+1)^{2}=4b^{2}+4b+1$
    Donde:
   * $x^{2}+y^{2}=(2b+1)^{2}=(4a^{2}+4a+1)+(4b^{2}+4b+1)=4k+2$
    Ou seja, a soma dos quadrados de $x$ e $y$ seria par, mas não pertenceria a $4\mathbb {Z} .$
    No entanto, sempre que $z^{2}$ é par, tem-se $z$ par e consequentemente $z^{2}\in 4\mathbb {Z} .$
    Logo, quando $x,y$ são ambos ímpares, a soma de seus quadrados não pode ser um quadrado perfeito.
Segue que dos inteiros $x,y,$ um é ímpar e outro é par. Sem perda de generalidade, pode-se supor que $x$ é par e $y$ é ímpar.
Uma outra forma de escrever a equação original é:
    $x^{2}=z^{2}-y^{2}=(z+y)(z-y)$
A partir daí, pode-se deduzir outras informações sobre os inteiros que a satisfazem. Por exemplo, $(z+y,z-y)=1,$ pois:
    $d|z+y,z-y\Rightarrow d|2z,2y\Rightarrow d|2$
A segunda implicação vale pois $(z,y)=1.$ Logo, $d\leq 2.$
Mas não pode ocorrer $d=2,$ senão:
    $2|z+y$
e como $y$ é par, $z$ também seria, coisa que não é possível já que $(z,y)=1.$
Assim, o quadrado perfeito $x^{2}$ é o produto de dois números primos entre si. Disso decorre que cada um deles deve ser um quadrado perfeito (veja o exercício 1), ou seja:
    $\left\{{\begin{matrix}z+y&=&u^{2}\\z-y&=&v^{2}\end{matrix}}\right.$
que equivale a:
    $\left\{{\begin{matrix}2z&=&u^{2}+v^{2}\\2y&=&u^{2}-v^{2}\end{matrix}}\right.$
Portanto, quando três números inteiros primos entre si (e não todos nulos) satizfazem a equação:
    $x^{2}+y^{2}=z^{2}$
devem existir inteiros $u,v,$ ímpares e primos entre si, tais que $u>v$ e:
    $\left\{{\begin{matrix}x&=&uv\\y&=&{\frac {u^{2}-v^{2}}{2}}\\z&=&{\frac {u^{2}+v^{2}}{2}}\end{matrix}}\right.$
Claramente, para quaisquer inteiros $u,v,$ os valores de $x,y,z$ obtidos pelas fórmulas acima são ternos pitagóricos, pois:
    $(uv)^{2}+({\frac {u^{2}-v^{2}}{2}})^{2}={\frac {2u^{2}v^{2}+(u^{2}-v^{2})^{2}}{2}}={\frac {u^{2}+v^{2}}{2}}$

### Exemplos

Pode-se obter facilmente uma dezena de ternos pitagóricos utilizando as fórmulas:
    $\left\{{\begin{matrix}x&=&uv\\y&=&{\frac {u^{2}-v^{2}}{2}}\\z&=&{\frac {u^{2}+v^{2}}{2}}\end{matrix}}\right.$
Alguns deles são listados na tabela a seguir:
    parâmetrosternos pitagóricos $u$$v$$x$$y$$z$ 31345 5151213 7172425 9194041 5315817 73212029
Note ainda que toda solução é da forma:
    $4UV+(U-V)=(U+V)^{2}$
onde:
    $\left\{{\begin{matrix}U&=&u^{2}\\V&=&v^{2}\\\end{matrix}}\right.$

### Observações

A fórmula clássica para a obtenção de ternos pitagóricos é conhecida como Fórmula de Euclides, por ter sido apresentada nos Elementos de Euclides é a seguinte:
    $\left\{{\begin{matrix}x&=&a^{2}-b^{2}\\y&=&2ab\\z&=&a^{2}+b^{2}\end{matrix}}\right.$
Tal fórmula é equivalente àquela deduzida anteriormente, como se pode verificar facilmente:

## Exercícios

* Mostre que se $a^{2}=b\cdot c,$ com $b,c$ primos entre si, então $b,c$ são quadrados perfeitos.

# Congruências

* Carl Friedrich Gauss
* Carl Friedrich Gauss foi um famoso matemático, astrônomo e físico alemão.

## Definição
### Definição

O inteiro $x$ é dito congruente ao inteiro $y$ módulo $m$, quando $m|x-y$. Neste caso, escreve-se $x\equiv y\!\!\!\!{\pmod {m}}$.
Com essa notação, tem-se para quaisquer inteiros $x,y$:
    $x^{2}+y^{2}\not \equiv 3\!\!\!\!{\pmod {4}}$
pois
    $k\equiv 0\!\!\!\!{\pmod {2}}\Rightarrow k^{2}\equiv 0\!\!\!\!{\pmod {4}}$
e
    $k\equiv 1\!\!\!\!{\pmod {2}}\Rightarrow k^{2}\equiv 1\!\!\!\!{\pmod {4}}$
Como se pode ver na próxima tabela, onde são listadas todas as combinações possíveis para $x^{2},y^{2}$ e $x^{2}+y^{2}$ módulo $2$, a soma de dois quadrados nunca é congruente a $3$ módulo $4$.
| $_{x^{2}}\!\!\diagdown \!\!^{y^{2}}$ | 0 | 1 |
| 0 | 0 | 1 |
| 1 | 1 | 2 |
Em outras palavras, o simples cálculo feito acima mostra que ao somar dois quadrados perfeitos, o sucessor do resultado nunca é múltiplo de $4$.

### Nota

    $x\equiv y\!\!\!\!{\pmod {m}}\Leftrightarrow m|x-y$ $\Leftrightarrow \exists k\in \mathbb {Z} ,x-y=mk\Leftrightarrow \exists k\in \mathbb {Z} ,x=y+mk$
Sendo assim, a notação para congruências, introduzida por Gauss evita o uso de várias constantes ($k,c,m,t,\ldots$) que não são relevantes durante grande parte dos cálculos envolvendo divisibilidade. Atente para a semelhança (visual) entre as seguintes expressões:
    $x\equiv y\!\!\!\!{\pmod {m}}$
    $x=y+mk$

### Observação

Conforme o algoritmo da divisão, dados $a\in \mathbb {Z}$ e $m\in \mathbb {Z} ^{*}$existem únicos $q,r\in \mathbb {Z}$ de modo que:
    $a=mq+r$, com $0\leq r<m$
Isso significa que qualquer inteiro $a$ é congruente ao seu resto $r$ na divisão por um inteiro não nulo $m$. Uma vez que o resto obtido é único, pode-se definir para cada inteiro $m\not =0$ fixado, uma função $\rho _{m}$ que a cada número $a\in \mathbb {Z}$ associa o resto da divisão de $a$ por $m$. A imagem de $a$ por esta função é denotada por $a\!\!\!\!{\pmod {m}}$. Mais precisamente:
    $\rho _{m}:\mathbb {Z} \rightarrow \{0,1,2,\ldots ,m-1\}$
    $\rho _{m}(a)=a\!\!\!\!{\pmod {m}}$
Quando não houver risco de confusão, o índice $m$ será omitido e será escrito apenas $\rho$ em vez de $\rho _{m}$.

## A congruência vista como uma relação de equivalência

A partir da noção de congruência módulo um certo inteiro $m$, pode-se definir uma relação sobre o conjunto dos números inteiros da seguinte forma:
    $x\sim y\Leftrightarrow x\equiv y\!\!\!\!{\pmod {m}}$
Como será mostrado logo a diante, a relação assim definida satisfaz as propriedades de reflexividade, simetria, transitividade. Sendo, por isso, considerada uma relação de equivalência:
* $\forall x,x\equiv x\!\!\!\!{\pmod {m}}$
* $x\equiv y\!\!\!\!{\pmod {m}}\Rightarrow y\equiv x\!\!\!\!{\pmod {m}}$
* $x\equiv y\!\!\!\!{\pmod {m}}\land y\equiv z\!\!\!\!{\pmod {m}}\Rightarrow x\equiv z\!\!\!\!{\pmod {m}}$
De modo geral, é sempre possível construir uma relação de equivalência sobre um conjunto $X$ a partir de uma função cujo domínio seja $X$. De fato, se for definido que:
    $x\sim y\Leftrightarrow f(x)=f(y)$
então $\sim$ será uma relação de equivalência em $X$, pois $\forall x,y\in X$:
* $f(x)=f(x)$
* $f(x)=f(y)\Rightarrow f(y)=f(x)$
* $f(x)=f(y)\land f(y)=f(z)\Rightarrow f(x)=f(z)$
E destas propriedades da igualdade seguem as propriedades correspondentes para a relação $\sim$. Em particular, tomando $X=\mathbb {Z}$, e $f(x)=x\!\!\!\!{\pmod {m}}$, conclui-se que a congruência é uma relação de equivalência.

### Compatibilidade com as operações

Um fato importante, que não pode deixar de ser mencionado é que a relação de congruência é compatível com as operações do anel dos números inteiros, a saber, a adição e a multiplicação. Uma operação $\star$é compatível com uma relação de equivalência $\sim$ quando a partir de
    $\left\{{\begin{matrix}a&\sim &a'\\b&\sim &b'\\\end{matrix}}\right.$
pode-se concluir que
    $a\star b\sim a'\star b'$
No caso da relação de congruência, vê-se que a mesma é compatível tanto com a adição quanto com a multiplicação de números inteiros, como é sintetizado no próximo resultado.

#### Teorema

Se $a,a',b,b'$ são números inteiros tais que:
    $\left\{{\begin{matrix}a\equiv a'\!\!\!\!{\pmod {m}}\\b\equiv b'\!\!\!\!{\pmod {m}}\\\end{matrix}}\right.$
então:
    $\left\{{\begin{matrix}a+b\equiv a'+b'\!\!\!\!{\pmod {m}}\\ab\equiv a'b'\!\!\!\!{\pmod {m}}\\\end{matrix}}\right.$
A verificação deste resultado é bem simples, como se pode ver a seguir.

## O anel das classes de congruência

Sempre que se tem uma relação de equivalência $\sim$ sobre um conjunto $X$ é possível definir uma partição $P$ de tal conjunto. Uma coleção $P$ de subconjuntos de $X$ é chamada de partição de $X$ se todo elemento de $X$ pertence a exatamente um elemento de $P$. Os elementos de $P$ são disjuntos dois a dois, e sua união é o próprio conjunto $X$.
Para definir uma partição de $\mathbb {Z}$, usando a congruência módulo $m$, primeiramente define-se para cada inteiro $a$ a classe de equivalência de $a$, segundo $\sim$, como:
    $[a]_{m}=\{x\in \mathbb {Z} ;x\equiv a\!\!\!\!{\pmod {m}}\}$
Quando o inteiro $m$ estiver subentendido, será utilizado apenas $[a]$ para denotar $[a]_{m}$.
Nesses termos, o quociente de $\mathbb {Z}$ pela relação $\equiv \!\!\!\!{\pmod {m}}$ é a partição dada por:
    $\mathbb {Z} /_{\equiv \!\!\!\!{\pmod {m}}}=\{[a]_{m};a\in \mathbb {Z} \}$
Por simplicidade, denota-se $\mathbb {Z} /_{\equiv \!\!\!\!{\pmod {m}}}$ simplesmente como $\mathbb {Z} _{m}$.
Uma das formas de visualizar essa partição de $\mathbb {Z}$ é imaginar que sobre um barbante foram marcados todos os números inteiros, separando os números adjacentes sempre por uma mesma distância. Depois disso, para obter uma representação de $\mathbb {Z} _{m}$, enrola-se o barbante em torno de uma circunferência (infinitas vezes!), de modo que o zero ocupe a mesma posição que os inteiros $\ldots ,-2n,-n,n,2n,3n,\ldots$. Você pode então pensar nos elementos de $\mathbb {Z} _{n}$ como sendo os n pontos sobre a circunferência que se formou. Veja uma ilustração:
Deste modo, cada ponto da circunferência representa uma das classes de equivalência módulo $n$, ou seja, o conjunto dos números inteiros que ficaram sobrepostos naquele ponto da circunferência.
Mas o que há de interessante em particionar o conjunto dos números inteiros?
A grande utilidade de separar os números inteiros em várias classes de congruência é consequência da compatibilidade da congruência com as operações de adição e multiplicação: Sabendo-se que elas são compatíveis, é possível definir em cada $\mathbb {Z} _{m}$ novas operações de adição e multiplicação. O procedimento é o seguinte:
Fixado um inteiro $m$, e dadas as classes $[a],[b]$, define-se:
    $[a]+[b]=[a+b]$
    $[a]\times [b]=[a\times b]$ (ou simplesmente $[a][b]=[ab]$)
Em outras palavras, a soma (produto) das classes de congruência dos inteiros $a,b$ é a classe de congruência de sua soma (produto).
É importante notar onde é utilizada a compatibilidade da congruência com as operações de $\mathbb {Z}$: Dadas duas classes de equivalência $A=[a]=[a']$ e $B=[b]=[b']$, tanto faz obter $[A]+[B]$ como sendo $[a+b],[a'+b],[a+b']$ ou $[a'+b']$. Todas essas classes são idênticas!
Mais do que isso, ao definir essas operações, $(\mathbb {Z} _{m},+,\times )$ torna-se um anel com unidade, ou seja, são válidas as seguintes propriedades:
Além disso, tem-se um homomorfismo de anéis entre $\mathbb {Z} =\{0,\pm 1,\pm 2,\pm 3,\ldots \}$ e $\mathbb {Z} _{m}=\{m\mathbb {Z} +0,m\mathbb {Z} +1,\ldots ,m\mathbb {Z} +(m-1)\}$:
    $\rho :\mathbb {Z} \rightarrow \mathbb {Z} _{m}$
    $\rho (x)=[x]=[x\!\!\!\!{\pmod {m}}]$
    Recordando...
    Um anel com unidade é um conjunto R equipado com duas operações binárias + : R × R ? R e · : R × R ? R (onde × denota o produto cartesiano), chamadas de adição e multiplicação, tais que:
   * (R, +) é um grupo abeliano com elemento identidade, isto é, para todo a, b, c em R, vale o seguinte:
   ** (a + b) + c = a + (b + c) (+ é associativa)
   ** 0 + a = a (0 é a identidade)
   ** a + b = b + a (+ é comutativa)
   ** para cada a em R existe −a em R tal que a + (−a) = (−a) + a = 0 (−a é o elemento inverso de a)
   * (R, ·) é um monóide com elemento identidade 1, isto é, para todo a, b, c em R, vale:
   ** (a · b) · c = a · (b · c) (· é associativa)
   ** 1 · a = a · 1 = a (1 é a identidade)
   * Multiplicação se distribui em relação a adição:
   ** a · (b + c) = (a · b) + (a · c)
   ** (a + b) · c = (a · c) + (b · c).

### Exemplos

As próximas tabelas são as tabuadas das operações de adição e multiplicação no anel $\mathbb {Z} _{6}$. Note que este é um número composto, e que (por esse motivo) existem elementos não nulos em $\mathbb {Z} _{6}$ cujo produto é zero (no caso, $2\times 3=3\times 4=0$).
    $+$012345 0 012345 1 123450 2 234501 3 345012 4 450123 5 501234
    $\times$012345 0 000000 1 012345 2 024024 3 030303 4 042042 5 054321
Outro fato curioso que pode ser identificado em alguns anéis é a presença de elementos nilpotentes, ou seja, tais que alguma de suas potências é nula. Por exemplo, em $\mathbb {Z} _{12}$, tem-se $6^{2}=0$.
Veja a tábua de multiplicação completa para o anel de inteiros módulo $12$:
    $\times$01234567891011 0 000000000000 1 01234567891011 2 02468100246810 3 036903690369 4 048048048048 5 05103816114927 6 060606060606 7 07294116183105 8 084084084084 9 096309630963 10 01086420108642 11 01110987654321
O próximo passo é tentar compreender algebricamente os conjuntos $(\mathbb {Z} _{m},+)$.
No próximo diagrama pode ser observada a estrutura aditiva de $(\mathbb {Z} _{m},+)$:
    $\rho :\mathbb {Z} \rightarrow \mathbb {Z} _{m}$
    $G\ \ \ H$
    $mZ\rightarrow 0$
$H$ é subgrupo aditivo de $\mathbb {Z} _{m}$.
$H=\rho (G)$, $G$ subgrupo aditivo de $\mathbb {Z} _{m}$
    $mZ=ker(\rho )\subset G$
    $G=d\mathbb {Z}$
    $m\mathbb {Z} \subset d\mathbb {Z} \Leftrightarrow d|m$. Logo $H=d\mathbb {Z} /m\mathbb {Z}$
    ${\overline {x}}\in \mathbb {Z} _{m}$
    $ord_{m}^{+}(x)=k$
    ${\overline {k\cdot x}}=k\cdot {\overline {x}}={\overline {0}}$
    $kx\equiv 0\!\!\!\!{\pmod {m}}$
Menor $k$ tal que $m|kx$. $kx=mmc(x,m)={\frac {x\cdot m}{(x,m)}}$
    $ord_{m}^{+}(x)={\frac {m}{(x,m)}}$
    $(x,m)=1\Rightarrow {\overline {x}}$ gera $\mathbb {Z} _{m}$, ou seja são os blocos básicos.
Observe a seguinte tabela, onde constam as ordens aditivas módulo 6.
    $+$123456 0 0 1 123450 2 240 3 30 4 420 5 543210
    $G=d\mathbb {Z}$
    $m\mathbb {Z} \subset d\mathbb {Z} \Leftrightarrow d|m$. Logo $H=d\mathbb {Z} /m\mathbb {Z}$
Corolário da p7
    Se p é primo então $\mathbb {Z} _{p}$ não tem subgrupos triviais.
    $xy\equiv 0\!\!\!\!{\pmod {p}}$
    $p|xy\Rightarrow p|x$ ou $p|y$. Isso implica que $x={\overline {0}}$ ou $y={\overline {0}}$, donde $\mathbb {Z} _{p}$ é domínio de integridade e portanto, $\mathbb {Z} _{p}$ é corpo (todo domínio finito é corpo).
Exemplo:
    $\times$01234 0 00000 1 01234 2 02413 3 03142 4 04321
Outra consequencia é que, fixado z não nulo em Z_p, a função $\mu :\mathbb {Z} _{p}\rightarrow \mathbb {Z} _{p}$, definida por $\mu (x)=zx$ é injetiva, pois se $\mu (x)=\mu (x')$, ou seja, $zx\equiv zx'\!\!\!\!{\pmod {p}}$, então $z(x-x')\equiv 0\!\!\!\!{\pmod {p}}$. Como $(z,p)=1$, pode-se concluir que $x-x'\equiv 0\!\!\!\!{\pmod {p}}$, ou seja, $x\equiv x'\!\!\!\!{\pmod {p}}$.
Em particular, da sobrejetividade de $\mu$, e de $1\in \mathbb {Z} _{p}$ (a imagem de $\mu$), segue a existência de $z'\in \mathbb {Z} _{p}$ tal que $\mu (z')=1$, ou seja, tal que $zz'\equiv 1\!\!\!\!{\pmod {p}}$.
Algebricamente, o significado da sobrejetividade de $\mu$ é a existência de um elemento inverso para cada $z\in \mathbb {Z} _{p}$ (quando p é primo). No entanto, a argumentação anterior é não construtiva, pois não indica um método para obter o inverso de um certo $z\in \mathbb {Z} _{p}$.
Pode-se obter outra justificativa para a existência de elementos inversos em $\mathbb {Z} _{p}$ usando o teorema de Bezout. De fato, ${\bar {z}}\not ={\bar {0}}$ se, e somente se, $p\not |z$, ou seja, se, e somente, $(p,z)=1$. Usando o algoritmo de Euclides, pode-se então encontrar $u,v\in \mathbb {Z}$ tais que $pu+zv=1$. Em particular, usando congruências módulo p segue $pu+zv\equiv 1\!\!\!\!{\pmod {p}}$. Donde
$0+zv\equiv 1\!\!\!\!{\pmod {p}}$, ou seja, $zv\equiv 1\!\!\!\!{\pmod {p}}$. Portanto, o $z'$ procurado é simplesmente $v\!\!\!\!{\pmod {p}}$.

## Resumindo

Os fatos mais relevantes apresentados na discussão feita até agora podem ser sintetizados da seguinte forma:
* Para qualquer $m\in \mathbb {Z}$, tem-se um anel finito $\mathbb {Z} _{m}$;
* São equivalentes:
** $\mathbb {Z} _{m}$ é corpo;
** $\mathbb {Z} _{m}$ é um domínio;
** $m$ é um número primo;
       (propriedades algébricas dos conjuntos $\mathbb {Z} _{m}$ -- anéis regulares --correspondem a propriedades aritméticas dos numeros inteiros $m$).
* São também equivalentes:
** $\mathbb {Z} _{m}$ tem divisores de zero;
** $m$ é um número composto;

## Unidades

Para um inteiro $m$ arbitrário (seja ele primo ou não), podem ser considerada a questão:
    Quais elementos de $\mathbb {Z} _{m}$ são inversíveis?
Antes de responder essa pergunta, convém introduzir uma notação específica para denotar o conjunto dos elementos $u\in \mathbb {Z} _{m}$ que possuem inverso multiplicativo:

### Definição

Um elemento de $\mathbb {Z} _{m}$ é chamado de unidade quando possui inverso multiplicativo. O conjunto das unidades de $\mathbb {Z} _{m}$ denota-se por $U_{m}$.

### Exemplos

* Se p é número primo, então $U_{m}=\mathbb {Z} _{m}/\{0\}=\{{\bar {1}},{\bar {2}},\ldots ,{\overline {p-1}}\}$
* $U_{6}=\{{\bar {1}},{\bar {5}}\}=\{\pm {\bar {1}}\}$
* $U_{7}=\{{\bar {1}},{\bar {2}},{\bar {3}},{\bar {4}},{\bar {5}},{\bar {6}},{\bar {7}}\}$

### Propriedades das unidades

Pode-se verificar que para qualquer $m$, o conjunto $U_{m}$, das unidades de $\mathbb {Z} _{m}$, é um grupo multiplicativo finito. Em particular, sempre que $u,v\in U_{m}$, tem-se $uv\in U_{m}$. Além disso, $1\in U_{m}$ e existe $v\in U_{m}$ tal que $uv=1$.
Novamente, a estrutura de $U_{m}$ reflete as propriedades aritméticas de $m$. Para melhor entender o que isso significa, é interessante saber para cada $m$ a quantidade de elementos de $U_{m}$. É razoável esperar que esse número varie com $m$, então o melhor é definir uma função que associa $m$ com a cardinalidade de $U_{m}$:

#### Definição

A função $U_{m}$ de Euler é a função que associa a cada $m$ o número de elementos de $U_{m}$:
    $\phi (m)=|U_{m}|$

#### Observações

* Convenciona-se que $\phi (1)=1$.
* O valor $\phi (m)$ é justamente a quantidade de números de $1$ a $m$ que são coprimos com $m$:

### Exemplos

* Quando $p$ é um número primo, tem-se $\phi (p)=p-1$.
* Por outro lado, para números compostos, $\phi (m)$ pode ser bem menor do que $m-1$. Em particular, $\phi (6)=|U_{6}|=|\{\pm {\bar {1}}\}|=2<5-1=4$.

### Curiosidades
#### Exemplo

No caso $m=6$ apresentado anteriormente, temos as seguintes frações próprias com tal denominador:
    ${\frac {0}{6}},\mathbf {\frac {1}{6}} ,{\frac {2}{6}},{\frac {3}{6}},{\frac {4}{6}},\mathbf {\frac {5}{6}}$
Escrevendo cada uma delas na forma irredutível obtém-se:
    ${\frac {0}{1}},\mathbf {\frac {1}{6}} ,{\frac {1}{3}},{\frac {1}{2}},{\frac {2}{3}},\mathbf {\frac {5}{6}}$
Pode-se então conferir que, como era esperado, só duas das frações já estavam em sua forma irredutível: ${\frac {1}{6}}$ e ${\frac {5}{6}}$.
Note que ao escrever cada fração em sua forma irredutível os denominadores que surgem são todos divisores de $m=6$. Além disso, tem-se:
* 1 fração com denominador 1
* 1 fração com denominador 2
* 2 fração com denominador 3
* 2 fração com denominador 6
Totalizando $1+1+2+2=6$ frações. Por outro lado, a seguinte tabela indica um fato muito interessante:
    dNúmero de frações com denominador d$\phi (d)$ 1 11 2 11 3 22 6 22
Percebe-se que as duas últimas colunas coincidem. Mas o que isso significa?
Isso quer dizer que o número $m=6$ é, na verdade, igual a soma dos valores $\phi (d)$ de cada um dos divisores $d$. Em símbolos:
    $6=1+1+2+2=\phi (1)+\phi (2)+\phi (3)+\phi (6)$
Pode-se verificar que essas duas propriedades são válidas em geral:
* $\phi (m)$ é igual à quantidade de frações próprias não negativas com denominador que estão na forma irredutível.
* $m=\sum _{d|m}{\phi (d)}$

## Equações lineares

Uma questão muito natural é investigar em que casos há alguma solução para equações lineares do tipo
    $ax\equiv y\!\!\!\!{\pmod {m}}$

### Exemplo de equação linear com apenas uma solução

Considere em $\mathbb {Z} _{8}$ a seguinte equação:
    $3x=2$
ou, em termos de congruências,
    $3x\equiv 2\!\!\!\!{\pmod {8}}$
Sabendo que $mdc(3,8)=1$, é possível determinar $r,s$ tais que
    $3r+8s=1$
Por exemplo, pode-se tomar $r=-5$ e $s=2$. Outra possibilidade é $r=3$ e $s=-1$. Neste caso, nota-se que:
    $3\cdot 3+8\cdot (-1)\equiv 1\!\!\!\!{\pmod {8}}$
ou seja,
    $3\cdot 3+0\equiv 1\!\!\!\!{\pmod {8}}$
significando que $3=3^{-1}$ em $\mathbb {Z} _{8}$, ou seja, que neste anel o inverso multiplicativo de $3$ é ele mesmo. Sabendo disso, é possível resolver
    $3x\equiv 2\!\!\!\!{\pmod {8}}$
de forma análoga à utilizada em $\mathbb {Z}$: Multiplicando-se ambos os membros pelo inverso de $3$, segue:
    $3\cdot 3x\equiv 3\cdot 2\!\!\!\!{\pmod {8}}$
ou seja,
    $1\cdot x\equiv 6\!\!\!\!{\pmod {8}}$
Conclui-se então que, nesse exemplo, há uma somente uma solução em $\mathbb {Z} _{8}$ para a equação dada. Observe ainda que o número $y=2$ não teve qualquer influência no número de soluções para o problema. Isso pode ser percebido considerando para cada $x\in \mathbb {Z} _{8}$ o resultado de sua multiplicação por $a=3$:
    01234567 $\times 3$ 03614725
Note que se tem uma permutação dos elementos de $\mathbb {Z} _{8}$ e que, portanto, o único elemento que é levado em $2$ ao ser multiplicado por $3$ é o $6$. Essa unicidade permaneceria se o $2$ fosse trocado por qualquer outro elemento.

### Exemplo de equação linear sem solução

Considere a seguinte equação em $\mathbb {Z} _{8}$:
    $4x=5$
que em termos de congruências se escreve como
    $4x\equiv 5\!\!\!\!{\pmod {8}}$
Já foi mostrado que ela é equivalente à seguinte equação em $\mathbb {Z}$:
    $4x=5+8k$
ou seja,
    $4(x-2k)=5$
É claro que tal equação não admite sequer uma solução inteira, uma vez que à esquerda tem-se um número par e a direita um ímpar, ou para ser mais exato, pois $4=\mathrm {mdc} (4,8)\nmid 5$.

### Exemplo de equação linear com duas soluções

Como um último exemplo antes de conhecer o teorema que dá uma resposta definitiva sobre o número de soluções de uma equação linear em $\mathbb {Z} _{m}$, considere em $\mathbb {Z} _{8}$ a equação:
    $2x=6$
ou seja,
    $2x\equiv 6\!\!\!\!{\pmod {8}}$
O problema de encontrar soluções para esta equação é equivalente a encontrar inteiros $x,y$ tais que:
    $2x=6+8y$
Dividindo ambos os membros por dois, obtem-se
    ${\frac {2}{2}}x={\frac {6}{2}}+{\frac {8}{2}}y$
ou seja,
    $x=3+4y$
Em termos de congruências, segue:
    $x\equiv 3\!\!\!\!{\pmod {4}}$
Os números inteiros que verificam essa congruência são os termos da progressão aritmética:
    $\{\ldots ,-5,-1,3,7,11,15,19,\ldots \}$
No entanto, como as soluções são buscadas em $\mathbb {Z} _{8}$, devemos considerar os números acima módulo $8$:
    $\{\ldots ,3,7,3,7,3,7,3,\ldots \}$
ou seja, o conjunto das soluções é:
    $S=\{3,7\}$
Em suma, verificou-se através dos exemplos anteriores que é possível encontrar em $\mathbb {Z} _{8}$ equações do tipo $ax=y$ que possuam uma ou duas soluções, e mesmo equações que não adimitem solução. Essa é uma notavel diferença entre corpos (como $\mathbb {R}$, $\mathbb {Q}$ e $\mathbb {Z} _{p}$) e anéis. Por exemplo, em $\mathbb {Q}$ ou $\mathbb {R}$ você deve estar habituado a resolver $ax=y$, simplesmente dividindo os dois membros por $a$ (e talvez descrevendo esse procedimento como "passar o $a$ para o lado direito, dividindo..."). No entanto, é tempo de notar que isso só é possível quando $a$ possui inverso. Em $\mathbb {Q}$, todo número não nulo possui inverso. Mas isso não é verdade em todo anel! Por essa razão torna-se necessário tomar algum cuidado ao resolver equações nos aneis $\mathbb {Z} _{m}$. Fique atento!

## Exercícios

* Mostre que, se $x\equiv y\!\!\!\!{\pmod {m}}$ e $f$ é um polinômio com coeficientes inteiros, então $f(x)\equiv f(y)\!\!\!\!{\pmod {m}}$.
* Que propriedade aritmética do número inteiro $m$ corresponde a existência de elementos nilpotentes em $\mathbb {Z} _{m}$? (Lembre-se, um elemento é nilpotente quando alguma de suas potências inteiras é igual a zero)

# Problemas em aberto
## Conjectura de Goldbach

Dos problemas matemáticos em aberto, a conjectura de Goldbach, embora considerada de pouca relevância por alguns, é muito importante para os estudos dos números primos. Em uma carta a Euler em 1742, Goldbach sugeriu o seguinte: todo número natural par maior que 3 pode ser escrito como soma de dois números primos.

# 10000 primos
## Lista dos primeiros 10.000 números primos

A tabela a seguir foi produzida de forma automatizada, utilizando uma macro elaborada justamente para este fim. O código fonte está disponível em uma seção posterior desta página, e foi escrito na linguagem de programação OpenOffice.org Basic.
| 2 | 3 | 5 | 7 | 11 | 13 | 17 | 19 | 23 | 29 | 31 | 37 | 41 | 43 | 47 | 53 | 59 | 61 | 67 | 71 |
| 73 | 79 | 83 | 89 | 97 | 101 | 103 | 107 | 109 | 113 | 127 | 131 | 137 | 139 | 149 | 151 | 157 | 163 | 167 | 173 |
| 179 | 181 | 191 | 193 | 197 | 199 | 211 | 223 | 227 | 229 | 233 | 239 | 241 | 251 | 257 | 263 | 269 | 271 | 277 | 281 |
| 283 | 293 | 307 | 311 | 313 | 317 | 331 | 337 | 347 | 349 | 353 | 359 | 367 | 373 | 379 | 383 | 389 | 397 | 401 | 409 |
| 419 | 421 | 431 | 433 | 439 | 443 | 449 | 457 | 461 | 463 | 467 | 479 | 487 | 491 | 499 | 503 | 509 | 521 | 523 | 541 |
| 547 | 557 | 563 | 569 | 571 | 577 | 587 | 593 | 599 | 601 | 607 | 613 | 617 | 619 | 631 | 641 | 643 | 647 | 653 | 659 |
| 661 | 673 | 677 | 683 | 691 | 701 | 709 | 719 | 727 | 733 | 739 | 743 | 751 | 757 | 761 | 769 | 773 | 787 | 797 | 809 |
| 811 | 821 | 823 | 827 | 829 | 839 | 853 | 857 | 859 | 863 | 877 | 881 | 883 | 887 | 907 | 911 | 919 | 929 | 937 | 941 |
| 947 | 953 | 967 | 971 | 977 | 983 | 991 | 997 | 1009 | 1013 | 1019 | 1021 | 1031 | 1033 | 1039 | 1049 | 1051 | 1061 | 1063 | 1069 |
| 1087 | 1091 | 1093 | 1097 | 1103 | 1109 | 1117 | 1123 | 1129 | 1151 | 1153 | 1163 | 1171 | 1181 | 1187 | 1193 | 1201 | 1213 | 1217 | 1223 |
| 1229 | 1231 | 1237 | 1249 | 1259 | 1277 | 1279 | 1283 | 1289 | 1291 | 1297 | 1301 | 1303 | 1307 | 1319 | 1321 | 1327 | 1361 | 1367 | 1373 |
| 1381 | 1399 | 1409 | 1423 | 1427 | 1429 | 1433 | 1439 | 1447 | 1451 | 1453 | 1459 | 1471 | 1481 | 1483 | 1487 | 1489 | 1493 | 1499 | 1511 |
| 1523 | 1531 | 1543 | 1549 | 1553 | 1559 | 1567 | 1571 | 1579 | 1583 | 1597 | 1601 | 1607 | 1609 | 1613 | 1619 | 1621 | 1627 | 1637 | 1657 |
| 1663 | 1667 | 1669 | 1693 | 1697 | 1699 | 1709 | 1721 | 1723 | 1733 | 1741 | 1747 | 1753 | 1759 | 1777 | 1783 | 1787 | 1789 | 1801 | 1811 |
| 1823 | 1831 | 1847 | 1861 | 1867 | 1871 | 1873 | 1877 | 1879 | 1889 | 1901 | 1907 | 1913 | 1931 | 1933 | 1949 | 1951 | 1973 | 1979 | 1987 |
| 1993 | 1997 | 1999 | 2003 | 2011 | 2017 | 2027 | 2029 | 2039 | 2053 | 2063 | 2069 | 2081 | 2083 | 2087 | 2089 | 2099 | 2111 | 2113 | 2129 |
| 2131 | 2137 | 2141 | 2143 | 2153 | 2161 | 2179 | 2203 | 2207 | 2213 | 2221 | 2237 | 2239 | 2243 | 2251 | 2267 | 2269 | 2273 | 2281 | 2287 |
| 2293 | 2297 | 2309 | 2311 | 2333 | 2339 | 2341 | 2347 | 2351 | 2357 | 2371 | 2377 | 2381 | 2383 | 2389 | 2393 | 2399 | 2411 | 2417 | 2423 |
| 2437 | 2441 | 2447 | 2459 | 2467 | 2473 | 2477 | 2503 | 2521 | 2531 | 2539 | 2543 | 2549 | 2551 | 2557 | 2579 | 2591 | 2593 | 2609 | 2617 |
| 2621 | 2633 | 2647 | 2657 | 2659 | 2663 | 2671 | 2677 | 2683 | 2687 | 2689 | 2693 | 2699 | 2707 | 2711 | 2713 | 2719 | 2729 | 2731 | 2741 |
| 2749 | 2753 | 2767 | 2777 | 2789 | 2791 | 2797 | 2801 | 2803 | 2819 | 2833 | 2837 | 2843 | 2851 | 2857 | 2861 | 2879 | 2887 | 2897 | 2903 |
| 2909 | 2917 | 2927 | 2939 | 2953 | 2957 | 2963 | 2969 | 2971 | 2999 | 3001 | 3011 | 3019 | 3023 | 3037 | 3041 | 3049 | 3061 | 3067 | 3079 |
| 3083 | 3089 | 3109 | 3119 | 3121 | 3137 | 3163 | 3167 | 3169 | 3181 | 3187 | 3191 | 3203 | 3209 | 3217 | 3221 | 3229 | 3251 | 3253 | 3257 |
| 3259 | 3271 | 3299 | 3301 | 3307 | 3313 | 3319 | 3323 | 3329 | 3331 | 3343 | 3347 | 3359 | 3361 | 3371 | 3373 | 3389 | 3391 | 3407 | 3413 |
| 3433 | 3449 | 3457 | 3461 | 3463 | 3467 | 3469 | 3491 | 3499 | 3511 | 3517 | 3527 | 3529 | 3533 | 3539 | 3541 | 3547 | 3557 | 3559 | 3571 |
| 3581 | 3583 | 3593 | 3607 | 3613 | 3617 | 3623 | 3631 | 3637 | 3643 | 3659 | 3671 | 3673 | 3677 | 3691 | 3697 | 3701 | 3709 | 3719 | 3727 |
| 3733 | 3739 | 3761 | 3767 | 3769 | 3779 | 3793 | 3797 | 3803 | 3821 | 3823 | 3833 | 3847 | 3851 | 3853 | 3863 | 3877 | 3881 | 3889 | 3907 |
| 3911 | 3917 | 3919 | 3923 | 3929 | 3931 | 3943 | 3947 | 3967 | 3989 | 4001 | 4003 | 4007 | 4013 | 4019 | 4021 | 4027 | 4049 | 4051 | 4057 |
| 4073 | 4079 | 4091 | 4093 | 4099 | 4111 | 4127 | 4129 | 4133 | 4139 | 4153 | 4157 | 4159 | 4177 | 4201 | 4211 | 4217 | 4219 | 4229 | 4231 |
| 4241 | 4243 | 4253 | 4259 | 4261 | 4271 | 4273 | 4283 | 4289 | 4297 | 4327 | 4337 | 4339 | 4349 | 4357 | 4363 | 4373 | 4391 | 4397 | 4409 |
| 4421 | 4423 | 4441 | 4447 | 4451 | 4457 | 4463 | 4481 | 4483 | 4493 | 4507 | 4513 | 4517 | 4519 | 4523 | 4547 | 4549 | 4561 | 4567 | 4583 |
| 4591 | 4597 | 4603 | 4621 | 4637 | 4639 | 4643 | 4649 | 4651 | 4657 | 4663 | 4673 | 4679 | 4691 | 4703 | 4721 | 4723 | 4729 | 4733 | 4751 |
| 4759 | 4783 | 4787 | 4789 | 4793 | 4799 | 4801 | 4813 | 4817 | 4831 | 4861 | 4871 | 4877 | 4889 | 4903 | 4909 | 4919 | 4931 | 4933 | 4937 |
| 4943 | 4951 | 4957 | 4967 | 4969 | 4973 | 4987 | 4993 | 4999 | 5003 | 5009 | 5011 | 5021 | 5023 | 5039 | 5051 | 5059 | 5077 | 5081 | 5087 |
| 5099 | 5101 | 5107 | 5113 | 5119 | 5147 | 5153 | 5167 | 5171 | 5179 | 5189 | 5197 | 5209 | 5227 | 5231 | 5233 | 5237 | 5261 | 5273 | 5279 |
| 5281 | 5297 | 5303 | 5309 | 5323 | 5333 | 5347 | 5351 | 5381 | 5387 | 5393 | 5399 | 5407 | 5413 | 5417 | 5419 | 5431 | 5437 | 5441 | 5443 |
| 5449 | 5471 | 5477 | 5479 | 5483 | 5501 | 5503 | 5507 | 5519 | 5521 | 5527 | 5531 | 5557 | 5563 | 5569 | 5573 | 5581 | 5591 | 5623 | 5639 |
| 5641 | 5647 | 5651 | 5653 | 5657 | 5659 | 5669 | 5683 | 5689 | 5693 | 5701 | 5711 | 5717 | 5737 | 5741 | 5743 | 5749 | 5779 | 5783 | 5791 |
| 5801 | 5807 | 5813 | 5821 | 5827 | 5839 | 5843 | 5849 | 5851 | 5857 | 5861 | 5867 | 5869 | 5879 | 5881 | 5897 | 5903 | 5923 | 5927 | 5939 |
| 5953 | 5981 | 5987 | 6007 | 6011 | 6029 | 6037 | 6043 | 6047 | 6053 | 6067 | 6073 | 6079 | 6089 | 6091 | 6101 | 6113 | 6121 | 6131 | 6133 |
| 6143 | 6151 | 6163 | 6173 | 6197 | 6199 | 6203 | 6211 | 6217 | 6221 | 6229 | 6247 | 6257 | 6263 | 6269 | 6271 | 6277 | 6287 | 6299 | 6301 |
| 6311 | 6317 | 6323 | 6329 | 6337 | 6343 | 6353 | 6359 | 6361 | 6367 | 6373 | 6379 | 6389 | 6397 | 6421 | 6427 | 6449 | 6451 | 6469 | 6473 |
| 6481 | 6491 | 6521 | 6529 | 6547 | 6551 | 6553 | 6563 | 6569 | 6571 | 6577 | 6581 | 6599 | 6607 | 6619 | 6637 | 6653 | 6659 | 6661 | 6673 |
| 6679 | 6689 | 6691 | 6701 | 6703 | 6709 | 6719 | 6733 | 6737 | 6761 | 6763 | 6779 | 6781 | 6791 | 6793 | 6803 | 6823 | 6827 | 6829 | 6833 |
| 6841 | 6857 | 6863 | 6869 | 6871 | 6883 | 6899 | 6907 | 6911 | 6917 | 6947 | 6949 | 6959 | 6961 | 6967 | 6971 | 6977 | 6983 | 6991 | 6997 |
| 7001 | 7013 | 7019 | 7027 | 7039 | 7043 | 7057 | 7069 | 7079 | 7103 | 7109 | 7121 | 7127 | 7129 | 7151 | 7159 | 7177 | 7187 | 7193 | 7207 |
| 7211 | 7213 | 7219 | 7229 | 7237 | 7243 | 7247 | 7253 | 7283 | 7297 | 7307 | 7309 | 7321 | 7331 | 7333 | 7349 | 7351 | 7369 | 7393 | 7411 |
| 7417 | 7433 | 7451 | 7457 | 7459 | 7477 | 7481 | 7487 | 7489 | 7499 | 7507 | 7517 | 7523 | 7529 | 7537 | 7541 | 7547 | 7549 | 7559 | 7561 |
| 7573 | 7577 | 7583 | 7589 | 7591 | 7603 | 7607 | 7621 | 7639 | 7643 | 7649 | 7669 | 7673 | 7681 | 7687 | 7691 | 7699 | 7703 | 7717 | 7723 |
| 7727 | 7741 | 7753 | 7757 | 7759 | 7789 | 7793 | 7817 | 7823 | 7829 | 7841 | 7853 | 7867 | 7873 | 7877 | 7879 | 7883 | 7901 | 7907 | 7919 |
| 7927 | 7933 | 7937 | 7949 | 7951 | 7963 | 7993 | 8009 | 8011 | 8017 | 8039 | 8053 | 8059 | 8069 | 8081 | 8087 | 8089 | 8093 | 8101 | 8111 |
| 8117 | 8123 | 8147 | 8161 | 8167 | 8171 | 8179 | 8191 | 8209 | 8219 | 8221 | 8231 | 8233 | 8237 | 8243 | 8263 | 8269 | 8273 | 8287 | 8291 |
| 8293 | 8297 | 8311 | 8317 | 8329 | 8353 | 8363 | 8369 | 8377 | 8387 | 8389 | 8419 | 8423 | 8429 | 8431 | 8443 | 8447 | 8461 | 8467 | 8501 |
| 8513 | 8521 | 8527 | 8537 | 8539 | 8543 | 8563 | 8573 | 8581 | 8597 | 8599 | 8609 | 8623 | 8627 | 8629 | 8641 | 8647 | 8663 | 8669 | 8677 |
| 8681 | 8689 | 8693 | 8699 | 8707 | 8713 | 8719 | 8731 | 8737 | 8741 | 8747 | 8753 | 8761 | 8779 | 8783 | 8803 | 8807 | 8819 | 8821 | 8831 |
| 8837 | 8839 | 8849 | 8861 | 8863 | 8867 | 8887 | 8893 | 8923 | 8929 | 8933 | 8941 | 8951 | 8963 | 8969 | 8971 | 8999 | 9001 | 9007 | 9011 |
| 9013 | 9029 | 9041 | 9043 | 9049 | 9059 | 9067 | 9091 | 9103 | 9109 | 9127 | 9133 | 9137 | 9151 | 9157 | 9161 | 9173 | 9181 | 9187 | 9199 |
| 9203 | 9209 | 9221 | 9227 | 9239 | 9241 | 9257 | 9277 | 9281 | 9283 | 9293 | 9311 | 9319 | 9323 | 9337 | 9341 | 9343 | 9349 | 9371 | 9377 |
| 9391 | 9397 | 9403 | 9413 | 9419 | 9421 | 9431 | 9433 | 9437 | 9439 | 9461 | 9463 | 9467 | 9473 | 9479 | 9491 | 9497 | 9511 | 9521 | 9533 |
| 9539 | 9547 | 9551 | 9587 | 9601 | 9613 | 9619 | 9623 | 9629 | 9631 | 9643 | 9649 | 9661 | 9677 | 9679 | 9689 | 9697 | 9719 | 9721 | 9733 |
| 9739 | 9743 | 9749 | 9767 | 9769 | 9781 | 9787 | 9791 | 9803 | 9811 | 9817 | 9829 | 9833 | 9839 | 9851 | 9857 | 9859 | 9871 | 9883 | 9887 |
| 9901 | 9907 | 9923 | 9929 | 9931 | 9941 | 9949 | 9967 | 9973 | 10007 | 10009 | 10037 | 10039 | 10061 | 10067 | 10069 | 10079 | 10091 | 10093 | 10099 |
| 10103 | 10111 | 10133 | 10139 | 10141 | 10151 | 10159 | 10163 | 10169 | 10177 | 10181 | 10193 | 10211 | 10223 | 10243 | 10247 | 10253 | 10259 | 10267 | 10271 |
| 10273 | 10289 | 10301 | 10303 | 10313 | 10321 | 10331 | 10333 | 10337 | 10343 | 10357 | 10369 | 10391 | 10399 | 10427 | 10429 | 10433 | 10453 | 10457 | 10459 |
| 10463 | 10477 | 10487 | 10499 | 10501 | 10513 | 10529 | 10531 | 10559 | 10567 | 10589 | 10597 | 10601 | 10607 | 10613 | 10627 | 10631 | 10639 | 10651 | 10657 |
| 10663 | 10667 | 10687 | 10691 | 10709 | 10711 | 10723 | 10729 | 10733 | 10739 | 10753 | 10771 | 10781 | 10789 | 10799 | 10831 | 10837 | 10847 | 10853 | 10859 |
| 10861 | 10867 | 10883 | 10889 | 10891 | 10903 | 10909 | 10937 | 10939 | 10949 | 10957 | 10973 | 10979 | 10987 | 10993 | 11003 | 11027 | 11047 | 11057 | 11059 |
| 11069 | 11071 | 11083 | 11087 | 11093 | 11113 | 11117 | 11119 | 11131 | 11149 | 11159 | 11161 | 11171 | 11173 | 11177 | 11197 | 11213 | 11239 | 11243 | 11251 |
| 11257 | 11261 | 11273 | 11279 | 11287 | 11299 | 11311 | 11317 | 11321 | 11329 | 11351 | 11353 | 11369 | 11383 | 11393 | 11399 | 11411 | 11423 | 11437 | 11443 |
| 11447 | 11467 | 11471 | 11483 | 11489 | 11491 | 11497 | 11503 | 11519 | 11527 | 11549 | 11551 | 11579 | 11587 | 11593 | 11597 | 11617 | 11621 | 11633 | 11657 |
| 11677 | 11681 | 11689 | 11699 | 11701 | 11717 | 11719 | 11731 | 11743 | 11777 | 11779 | 11783 | 11789 | 11801 | 11807 | 11813 | 11821 | 11827 | 11831 | 11833 |
| 11839 | 11863 | 11867 | 11887 | 11897 | 11903 | 11909 | 11923 | 11927 | 11933 | 11939 | 11941 | 11953 | 11959 | 11969 | 11971 | 11981 | 11987 | 12007 | 12011 |
| 12037 | 12041 | 12043 | 12049 | 12071 | 12073 | 12097 | 12101 | 12107 | 12109 | 12113 | 12119 | 12143 | 12149 | 12157 | 12161 | 12163 | 12197 | 12203 | 12211 |
| 12227 | 12239 | 12241 | 12251 | 12253 | 12263 | 12269 | 12277 | 12281 | 12289 | 12301 | 12323 | 12329 | 12343 | 12347 | 12373 | 12377 | 12379 | 12391 | 12401 |
| 12409 | 12413 | 12421 | 12433 | 12437 | 12451 | 12457 | 12473 | 12479 | 12487 | 12491 | 12497 | 12503 | 12511 | 12517 | 12527 | 12539 | 12541 | 12547 | 12553 |
| 12569 | 12577 | 12583 | 12589 | 12601 | 12611 | 12613 | 12619 | 12637 | 12641 | 12647 | 12653 | 12659 | 12671 | 12689 | 12697 | 12703 | 12713 | 12721 | 12739 |
| 12743 | 12757 | 12763 | 12781 | 12791 | 12799 | 12809 | 12821 | 12823 | 12829 | 12841 | 12853 | 12889 | 12893 | 12899 | 12907 | 12911 | 12917 | 12919 | 12923 |
| 12941 | 12953 | 12959 | 12967 | 12973 | 12979 | 12983 | 13001 | 13003 | 13007 | 13009 | 13033 | 13037 | 13043 | 13049 | 13063 | 13093 | 13099 | 13103 | 13109 |
| 13121 | 13127 | 13147 | 13151 | 13159 | 13163 | 13171 | 13177 | 13183 | 13187 | 13217 | 13219 | 13229 | 13241 | 13249 | 13259 | 13267 | 13291 | 13297 | 13309 |
| 13313 | 13327 | 13331 | 13337 | 13339 | 13367 | 13381 | 13397 | 13399 | 13411 | 13417 | 13421 | 13441 | 13451 | 13457 | 13463 | 13469 | 13477 | 13487 | 13499 |
| 13513 | 13523 | 13537 | 13553 | 13567 | 13577 | 13591 | 13597 | 13613 | 13619 | 13627 | 13633 | 13649 | 13669 | 13679 | 13681 | 13687 | 13691 | 13693 | 13697 |
| 13709 | 13711 | 13721 | 13723 | 13729 | 13751 | 13757 | 13759 | 13763 | 13781 | 13789 | 13799 | 13807 | 13829 | 13831 | 13841 | 13859 | 13873 | 13877 | 13879 |
| 13883 | 13901 | 13903 | 13907 | 13913 | 13921 | 13931 | 13933 | 13963 | 13967 | 13997 | 13999 | 14009 | 14011 | 14029 | 14033 | 14051 | 14057 | 14071 | 14081 |
| 14083 | 14087 | 14107 | 14143 | 14149 | 14153 | 14159 | 14173 | 14177 | 14197 | 14207 | 14221 | 14243 | 14249 | 14251 | 14281 | 14293 | 14303 | 14321 | 14323 |
| 14327 | 14341 | 14347 | 14369 | 14387 | 14389 | 14401 | 14407 | 14411 | 14419 | 14423 | 14431 | 14437 | 14447 | 14449 | 14461 | 14479 | 14489 | 14503 | 14519 |
| 14533 | 14537 | 14543 | 14549 | 14551 | 14557 | 14561 | 14563 | 14591 | 14593 | 14621 | 14627 | 14629 | 14633 | 14639 | 14653 | 14657 | 14669 | 14683 | 14699 |
| 14713 | 14717 | 14723 | 14731 | 14737 | 14741 | 14747 | 14753 | 14759 | 14767 | 14771 | 14779 | 14783 | 14797 | 14813 | 14821 | 14827 | 14831 | 14843 | 14851 |
| 14867 | 14869 | 14879 | 14887 | 14891 | 14897 | 14923 | 14929 | 14939 | 14947 | 14951 | 14957 | 14969 | 14983 | 15013 | 15017 | 15031 | 15053 | 15061 | 15073 |
| 15077 | 15083 | 15091 | 15101 | 15107 | 15121 | 15131 | 15137 | 15139 | 15149 | 15161 | 15173 | 15187 | 15193 | 15199 | 15217 | 15227 | 15233 | 15241 | 15259 |
| 15263 | 15269 | 15271 | 15277 | 15287 | 15289 | 15299 | 15307 | 15313 | 15319 | 15329 | 15331 | 15349 | 15359 | 15361 | 15373 | 15377 | 15383 | 15391 | 15401 |
| 15413 | 15427 | 15439 | 15443 | 15451 | 15461 | 15467 | 15473 | 15493 | 15497 | 15511 | 15527 | 15541 | 15551 | 15559 | 15569 | 15581 | 15583 | 15601 | 15607 |
| 15619 | 15629 | 15641 | 15643 | 15647 | 15649 | 15661 | 15667 | 15671 | 15679 | 15683 | 15727 | 15731 | 15733 | 15737 | 15739 | 15749 | 15761 | 15767 | 15773 |
| 15787 | 15791 | 15797 | 15803 | 15809 | 15817 | 15823 | 15859 | 15877 | 15881 | 15887 | 15889 | 15901 | 15907 | 15913 | 15919 | 15923 | 15937 | 15959 | 15971 |
| 15973 | 15991 | 16001 | 16007 | 16033 | 16057 | 16061 | 16063 | 16067 | 16069 | 16073 | 16087 | 16091 | 16097 | 16103 | 16111 | 16127 | 16139 | 16141 | 16183 |
| 16187 | 16189 | 16193 | 16217 | 16223 | 16229 | 16231 | 16249 | 16253 | 16267 | 16273 | 16301 | 16319 | 16333 | 16339 | 16349 | 16361 | 16363 | 16369 | 16381 |
| 16411 | 16417 | 16421 | 16427 | 16433 | 16447 | 16451 | 16453 | 16477 | 16481 | 16487 | 16493 | 16519 | 16529 | 16547 | 16553 | 16561 | 16567 | 16573 | 16603 |
| 16607 | 16619 | 16631 | 16633 | 16649 | 16651 | 16657 | 16661 | 16673 | 16691 | 16693 | 16699 | 16703 | 16729 | 16741 | 16747 | 16759 | 16763 | 16787 | 16811 |
| 16823 | 16829 | 16831 | 16843 | 16871 | 16879 | 16883 | 16889 | 16901 | 16903 | 16921 | 16927 | 16931 | 16937 | 16943 | 16963 | 16979 | 16981 | 16987 | 16993 |
| 17011 | 17021 | 17027 | 17029 | 17033 | 17041 | 17047 | 17053 | 17077 | 17093 | 17099 | 17107 | 17117 | 17123 | 17137 | 17159 | 17167 | 17183 | 17189 | 17191 |
| 17203 | 17207 | 17209 | 17231 | 17239 | 17257 | 17291 | 17293 | 17299 | 17317 | 17321 | 17327 | 17333 | 17341 | 17351 | 17359 | 17377 | 17383 | 17387 | 17389 |
| 17393 | 17401 | 17417 | 17419 | 17431 | 17443 | 17449 | 17467 | 17471 | 17477 | 17483 | 17489 | 17491 | 17497 | 17509 | 17519 | 17539 | 17551 | 17569 | 17573 |
| 17579 | 17581 | 17597 | 17599 | 17609 | 17623 | 17627 | 17657 | 17659 | 17669 | 17681 | 17683 | 17707 | 17713 | 17729 | 17737 | 17747 | 17749 | 17761 | 17783 |
| 17789 | 17791 | 17807 | 17827 | 17837 | 17839 | 17851 | 17863 | 17881 | 17891 | 17903 | 17909 | 17911 | 17921 | 17923 | 17929 | 17939 | 17957 | 17959 | 17971 |
| 17977 | 17981 | 17987 | 17989 | 18013 | 18041 | 18043 | 18047 | 18049 | 18059 | 18061 | 18077 | 18089 | 18097 | 18119 | 18121 | 18127 | 18131 | 18133 | 18143 |
| 18149 | 18169 | 18181 | 18191 | 18199 | 18211 | 18217 | 18223 | 18229 | 18233 | 18251 | 18253 | 18257 | 18269 | 18287 | 18289 | 18301 | 18307 | 18311 | 18313 |
| 18329 | 18341 | 18353 | 18367 | 18371 | 18379 | 18397 | 18401 | 18413 | 18427 | 18433 | 18439 | 18443 | 18451 | 18457 | 18461 | 18481 | 18493 | 18503 | 18517 |
| 18521 | 18523 | 18539 | 18541 | 18553 | 18583 | 18587 | 18593 | 18617 | 18637 | 18661 | 18671 | 18679 | 18691 | 18701 | 18713 | 18719 | 18731 | 18743 | 18749 |
| 18757 | 18773 | 18787 | 18793 | 18797 | 18803 | 18839 | 18859 | 18869 | 18899 | 18911 | 18913 | 18917 | 18919 | 18947 | 18959 | 18973 | 18979 | 19001 | 19009 |
| 19013 | 19031 | 19037 | 19051 | 19069 | 19073 | 19079 | 19081 | 19087 | 19121 | 19139 | 19141 | 19157 | 19163 | 19181 | 19183 | 19207 | 19211 | 19213 | 19219 |
| 19231 | 19237 | 19249 | 19259 | 19267 | 19273 | 19289 | 19301 | 19309 | 19319 | 19333 | 19373 | 19379 | 19381 | 19387 | 19391 | 19403 | 19417 | 19421 | 19423 |
| 19427 | 19429 | 19433 | 19441 | 19447 | 19457 | 19463 | 19469 | 19471 | 19477 | 19483 | 19489 | 19501 | 19507 | 19531 | 19541 | 19543 | 19553 | 19559 | 19571 |
| 19577 | 19583 | 19597 | 19603 | 19609 | 19661 | 19681 | 19687 | 19697 | 19699 | 19709 | 19717 | 19727 | 19739 | 19751 | 19753 | 19759 | 19763 | 19777 | 19793 |
| 19801 | 19813 | 19819 | 19841 | 19843 | 19853 | 19861 | 19867 | 19889 | 19891 | 19913 | 19919 | 19927 | 19937 | 19949 | 19961 | 19963 | 19973 | 19979 | 19991 |
| 19993 | 19997 | 20011 | 20021 | 20023 | 20029 | 20047 | 20051 | 20063 | 20071 | 20089 | 20101 | 20107 | 20113 | 20117 | 20123 | 20129 | 20143 | 20147 | 20149 |
| 20161 | 20173 | 20177 | 20183 | 20201 | 20219 | 20231 | 20233 | 20249 | 20261 | 20269 | 20287 | 20297 | 20323 | 20327 | 20333 | 20341 | 20347 | 20353 | 20357 |
| 20359 | 20369 | 20389 | 20393 | 20399 | 20407 | 20411 | 20431 | 20441 | 20443 | 20477 | 20479 | 20483 | 20507 | 20509 | 20521 | 20533 | 20543 | 20549 | 20551 |
| 20563 | 20593 | 20599 | 20611 | 20627 | 20639 | 20641 | 20663 | 20681 | 20693 | 20707 | 20717 | 20719 | 20731 | 20743 | 20747 | 20749 | 20753 | 20759 | 20771 |
| 20773 | 20789 | 20807 | 20809 | 20849 | 20857 | 20873 | 20879 | 20887 | 20897 | 20899 | 20903 | 20921 | 20929 | 20939 | 20947 | 20959 | 20963 | 20981 | 20983 |
| 21001 | 21011 | 21013 | 21017 | 21019 | 21023 | 21031 | 21059 | 21061 | 21067 | 21089 | 21101 | 21107 | 21121 | 21139 | 21143 | 21149 | 21157 | 21163 | 21169 |
| 21179 | 21187 | 21191 | 21193 | 21211 | 21221 | 21227 | 21247 | 21269 | 21277 | 21283 | 21313 | 21317 | 21319 | 21323 | 21341 | 21347 | 21377 | 21379 | 21383 |
| 21391 | 21397 | 21401 | 21407 | 21419 | 21433 | 21467 | 21481 | 21487 | 21491 | 21493 | 21499 | 21503 | 21517 | 21521 | 21523 | 21529 | 21557 | 21559 | 21563 |
| 21569 | 21577 | 21587 | 21589 | 21599 | 21601 | 21611 | 21613 | 21617 | 21647 | 21649 | 21661 | 21673 | 21683 | 21701 | 21713 | 21727 | 21737 | 21739 | 21751 |
| 21757 | 21767 | 21773 | 21787 | 21799 | 21803 | 21817 | 21821 | 21839 | 21841 | 21851 | 21859 | 21863 | 21871 | 21881 | 21893 | 21911 | 21929 | 21937 | 21943 |
| 21961 | 21977 | 21991 | 21997 | 22003 | 22013 | 22027 | 22031 | 22037 | 22039 | 22051 | 22063 | 22067 | 22073 | 22079 | 22091 | 22093 | 22109 | 22111 | 22123 |
| 22129 | 22133 | 22147 | 22153 | 22157 | 22159 | 22171 | 22189 | 22193 | 22229 | 22247 | 22259 | 22271 | 22273 | 22277 | 22279 | 22283 | 22291 | 22303 | 22307 |
| 22343 | 22349 | 22367 | 22369 | 22381 | 22391 | 22397 | 22409 | 22433 | 22441 | 22447 | 22453 | 22469 | 22481 | 22483 | 22501 | 22511 | 22531 | 22541 | 22543 |
| 22549 | 22567 | 22571 | 22573 | 22613 | 22619 | 22621 | 22637 | 22639 | 22643 | 22651 | 22669 | 22679 | 22691 | 22697 | 22699 | 22709 | 22717 | 22721 | 22727 |
| 22739 | 22741 | 22751 | 22769 | 22777 | 22783 | 22787 | 22807 | 22811 | 22817 | 22853 | 22859 | 22861 | 22871 | 22877 | 22901 | 22907 | 22921 | 22937 | 22943 |
| 22961 | 22963 | 22973 | 22993 | 23003 | 23011 | 23017 | 23021 | 23027 | 23029 | 23039 | 23041 | 23053 | 23057 | 23059 | 23063 | 23071 | 23081 | 23087 | 23099 |
| 23117 | 23131 | 23143 | 23159 | 23167 | 23173 | 23189 | 23197 | 23201 | 23203 | 23209 | 23227 | 23251 | 23269 | 23279 | 23291 | 23293 | 23297 | 23311 | 23321 |
| 23327 | 23333 | 23339 | 23357 | 23369 | 23371 | 23399 | 23417 | 23431 | 23447 | 23459 | 23473 | 23497 | 23509 | 23531 | 23537 | 23539 | 23549 | 23557 | 23561 |
| 23563 | 23567 | 23581 | 23593 | 23599 | 23603 | 23609 | 23623 | 23627 | 23629 | 23633 | 23663 | 23669 | 23671 | 23677 | 23687 | 23689 | 23719 | 23741 | 23743 |
| 23747 | 23753 | 23761 | 23767 | 23773 | 23789 | 23801 | 23813 | 23819 | 23827 | 23831 | 23833 | 23857 | 23869 | 23873 | 23879 | 23887 | 23893 | 23899 | 23909 |
| 23911 | 23917 | 23929 | 23957 | 23971 | 23977 | 23981 | 23993 | 24001 | 24007 | 24019 | 24023 | 24029 | 24043 | 24049 | 24061 | 24071 | 24077 | 24083 | 24091 |
| 24097 | 24103 | 24107 | 24109 | 24113 | 24121 | 24133 | 24137 | 24151 | 24169 | 24179 | 24181 | 24197 | 24203 | 24223 | 24229 | 24239 | 24247 | 24251 | 24281 |
| 24317 | 24329 | 24337 | 24359 | 24371 | 24373 | 24379 | 24391 | 24407 | 24413 | 24419 | 24421 | 24439 | 24443 | 24469 | 24473 | 24481 | 24499 | 24509 | 24517 |
| 24527 | 24533 | 24547 | 24551 | 24571 | 24593 | 24611 | 24623 | 24631 | 24659 | 24671 | 24677 | 24683 | 24691 | 24697 | 24709 | 24733 | 24749 | 24763 | 24767 |
| 24781 | 24793 | 24799 | 24809 | 24821 | 24841 | 24847 | 24851 | 24859 | 24877 | 24889 | 24907 | 24917 | 24919 | 24923 | 24943 | 24953 | 24967 | 24971 | 24977 |
| 24979 | 24989 | 25013 | 25031 | 25033 | 25037 | 25057 | 25073 | 25087 | 25097 | 25111 | 25117 | 25121 | 25127 | 25147 | 25153 | 25163 | 25169 | 25171 | 25183 |
| 25189 | 25219 | 25229 | 25237 | 25243 | 25247 | 25253 | 25261 | 25301 | 25303 | 25307 | 25309 | 25321 | 25339 | 25343 | 25349 | 25357 | 25367 | 25373 | 25391 |
| 25409 | 25411 | 25423 | 25439 | 25447 | 25453 | 25457 | 25463 | 25469 | 25471 | 25523 | 25537 | 25541 | 25561 | 25577 | 25579 | 25583 | 25589 | 25601 | 25603 |
| 25609 | 25621 | 25633 | 25639 | 25643 | 25657 | 25667 | 25673 | 25679 | 25693 | 25703 | 25717 | 25733 | 25741 | 25747 | 25759 | 25763 | 25771 | 25793 | 25799 |
| 25801 | 25819 | 25841 | 25847 | 25849 | 25867 | 25873 | 25889 | 25903 | 25913 | 25919 | 25931 | 25933 | 25939 | 25943 | 25951 | 25969 | 25981 | 25997 | 25999 |
| 26003 | 26017 | 26021 | 26029 | 26041 | 26053 | 26083 | 26099 | 26107 | 26111 | 26113 | 26119 | 26141 | 26153 | 26161 | 26171 | 26177 | 26183 | 26189 | 26203 |
| 26209 | 26227 | 26237 | 26249 | 26251 | 26261 | 26263 | 26267 | 26293 | 26297 | 26309 | 26317 | 26321 | 26339 | 26347 | 26357 | 26371 | 26387 | 26393 | 26399 |
| 26407 | 26417 | 26423 | 26431 | 26437 | 26449 | 26459 | 26479 | 26489 | 26497 | 26501 | 26513 | 26539 | 26557 | 26561 | 26573 | 26591 | 26597 | 26627 | 26633 |
| 26641 | 26647 | 26669 | 26681 | 26683 | 26687 | 26693 | 26699 | 26701 | 26711 | 26713 | 26717 | 26723 | 26729 | 26731 | 26737 | 26759 | 26777 | 26783 | 26801 |
| 26813 | 26821 | 26833 | 26839 | 26849 | 26861 | 26863 | 26879 | 26881 | 26891 | 26893 | 26903 | 26921 | 26927 | 26947 | 26951 | 26953 | 26959 | 26981 | 26987 |
| 26993 | 27011 | 27017 | 27031 | 27043 | 27059 | 27061 | 27067 | 27073 | 27077 | 27091 | 27103 | 27107 | 27109 | 27127 | 27143 | 27179 | 27191 | 27197 | 27211 |
| 27239 | 27241 | 27253 | 27259 | 27271 | 27277 | 27281 | 27283 | 27299 | 27329 | 27337 | 27361 | 27367 | 27397 | 27407 | 27409 | 27427 | 27431 | 27437 | 27449 |
| 27457 | 27479 | 27481 | 27487 | 27509 | 27527 | 27529 | 27539 | 27541 | 27551 | 27581 | 27583 | 27611 | 27617 | 27631 | 27647 | 27653 | 27673 | 27689 | 27691 |
| 27697 | 27701 | 27733 | 27737 | 27739 | 27743 | 27749 | 27751 | 27763 | 27767 | 27773 | 27779 | 27791 | 27793 | 27799 | 27803 | 27809 | 27817 | 27823 | 27827 |
| 27847 | 27851 | 27883 | 27893 | 27901 | 27917 | 27919 | 27941 | 27943 | 27947 | 27953 | 27961 | 27967 | 27983 | 27997 | 28001 | 28019 | 28027 | 28031 | 28051 |
| 28057 | 28069 | 28081 | 28087 | 28097 | 28099 | 28109 | 28111 | 28123 | 28151 | 28163 | 28181 | 28183 | 28201 | 28211 | 28219 | 28229 | 28277 | 28279 | 28283 |
| 28289 | 28297 | 28307 | 28309 | 28319 | 28349 | 28351 | 28387 | 28393 | 28403 | 28409 | 28411 | 28429 | 28433 | 28439 | 28447 | 28463 | 28477 | 28493 | 28499 |
| 28513 | 28517 | 28537 | 28541 | 28547 | 28549 | 28559 | 28571 | 28573 | 28579 | 28591 | 28597 | 28603 | 28607 | 28619 | 28621 | 28627 | 28631 | 28643 | 28649 |
| 28657 | 28661 | 28663 | 28669 | 28687 | 28697 | 28703 | 28711 | 28723 | 28729 | 28751 | 28753 | 28759 | 28771 | 28789 | 28793 | 28807 | 28813 | 28817 | 28837 |
| 28843 | 28859 | 28867 | 28871 | 28879 | 28901 | 28909 | 28921 | 28927 | 28933 | 28949 | 28961 | 28979 | 29009 | 29017 | 29021 | 29023 | 29027 | 29033 | 29059 |
| 29063 | 29077 | 29101 | 29123 | 29129 | 29131 | 29137 | 29147 | 29153 | 29167 | 29173 | 29179 | 29191 | 29201 | 29207 | 29209 | 29221 | 29231 | 29243 | 29251 |
| 29269 | 29287 | 29297 | 29303 | 29311 | 29327 | 29333 | 29339 | 29347 | 29363 | 29383 | 29387 | 29389 | 29399 | 29401 | 29411 | 29423 | 29429 | 29437 | 29443 |
| 29453 | 29473 | 29483 | 29501 | 29527 | 29531 | 29537 | 29567 | 29569 | 29573 | 29581 | 29587 | 29599 | 29611 | 29629 | 29633 | 29641 | 29663 | 29669 | 29671 |
| 29683 | 29717 | 29723 | 29741 | 29753 | 29759 | 29761 | 29789 | 29803 | 29819 | 29833 | 29837 | 29851 | 29863 | 29867 | 29873 | 29879 | 29881 | 29917 | 29921 |
| 29927 | 29947 | 29959 | 29983 | 29989 | 30011 | 30013 | 30029 | 30047 | 30059 | 30071 | 30089 | 30091 | 30097 | 30103 | 30109 | 30113 | 30119 | 30133 | 30137 |
| 30139 | 30161 | 30169 | 30181 | 30187 | 30197 | 30203 | 30211 | 30223 | 30241 | 30253 | 30259 | 30269 | 30271 | 30293 | 30307 | 30313 | 30319 | 30323 | 30341 |
| 30347 | 30367 | 30389 | 30391 | 30403 | 30427 | 30431 | 30449 | 30467 | 30469 | 30491 | 30493 | 30497 | 30509 | 30517 | 30529 | 30539 | 30553 | 30557 | 30559 |
| 30577 | 30593 | 30631 | 30637 | 30643 | 30649 | 30661 | 30671 | 30677 | 30689 | 30697 | 30703 | 30707 | 30713 | 30727 | 30757 | 30763 | 30773 | 30781 | 30803 |
| 30809 | 30817 | 30829 | 30839 | 30841 | 30851 | 30853 | 30859 | 30869 | 30871 | 30881 | 30893 | 30911 | 30931 | 30937 | 30941 | 30949 | 30971 | 30977 | 30983 |
| 31013 | 31019 | 31033 | 31039 | 31051 | 31063 | 31069 | 31079 | 31081 | 31091 | 31121 | 31123 | 31139 | 31147 | 31151 | 31153 | 31159 | 31177 | 31181 | 31183 |
| 31189 | 31193 | 31219 | 31223 | 31231 | 31237 | 31247 | 31249 | 31253 | 31259 | 31267 | 31271 | 31277 | 31307 | 31319 | 31321 | 31327 | 31333 | 31337 | 31357 |
| 31379 | 31387 | 31391 | 31393 | 31397 | 31469 | 31477 | 31481 | 31489 | 31511 | 31513 | 31517 | 31531 | 31541 | 31543 | 31547 | 31567 | 31573 | 31583 | 31601 |
| 31607 | 31627 | 31643 | 31649 | 31657 | 31663 | 31667 | 31687 | 31699 | 31721 | 31723 | 31727 | 31729 | 31741 | 31751 | 31769 | 31771 | 31793 | 31799 | 31817 |
| 31847 | 31849 | 31859 | 31873 | 31883 | 31891 | 31907 | 31957 | 31963 | 31973 | 31981 | 31991 | 32003 | 32009 | 32027 | 32029 | 32051 | 32057 | 32059 | 32063 |
| 32069 | 32077 | 32083 | 32089 | 32099 | 32117 | 32119 | 32141 | 32143 | 32159 | 32173 | 32183 | 32189 | 32191 | 32203 | 32213 | 32233 | 32237 | 32251 | 32257 |
| 32261 | 32297 | 32299 | 32303 | 32309 | 32321 | 32323 | 32327 | 32341 | 32353 | 32359 | 32363 | 32369 | 32371 | 32377 | 32381 | 32401 | 32411 | 32413 | 32423 |
| 32429 | 32441 | 32443 | 32467 | 32479 | 32491 | 32497 | 32503 | 32507 | 32531 | 32533 | 32537 | 32561 | 32563 | 32569 | 32573 | 32579 | 32587 | 32603 | 32609 |
| 32611 | 32621 | 32633 | 32647 | 32653 | 32687 | 32693 | 32707 | 32713 | 32717 | 32719 | 32749 | 32771 | 32779 | 32783 | 32789 | 32797 | 32801 | 32803 | 32831 |
| 32833 | 32839 | 32843 | 32869 | 32887 | 32909 | 32911 | 32917 | 32933 | 32939 | 32941 | 32957 | 32969 | 32971 | 32983 | 32987 | 32993 | 32999 | 33013 | 33023 |
| 33029 | 33037 | 33049 | 33053 | 33071 | 33073 | 33083 | 33091 | 33107 | 33113 | 33119 | 33149 | 33151 | 33161 | 33179 | 33181 | 33191 | 33199 | 33203 | 33211 |
| 33223 | 33247 | 33287 | 33289 | 33301 | 33311 | 33317 | 33329 | 33331 | 33343 | 33347 | 33349 | 33353 | 33359 | 33377 | 33391 | 33403 | 33409 | 33413 | 33427 |
| 33457 | 33461 | 33469 | 33479 | 33487 | 33493 | 33503 | 33521 | 33529 | 33533 | 33547 | 33563 | 33569 | 33577 | 33581 | 33587 | 33589 | 33599 | 33601 | 33613 |
| 33617 | 33619 | 33623 | 33629 | 33637 | 33641 | 33647 | 33679 | 33703 | 33713 | 33721 | 33739 | 33749 | 33751 | 33757 | 33767 | 33769 | 33773 | 33791 | 33797 |
| 33809 | 33811 | 33827 | 33829 | 33851 | 33857 | 33863 | 33871 | 33889 | 33893 | 33911 | 33923 | 33931 | 33937 | 33941 | 33961 | 33967 | 33997 | 34019 | 34031 |
| 34033 | 34039 | 34057 | 34061 | 34123 | 34127 | 34129 | 34141 | 34147 | 34157 | 34159 | 34171 | 34183 | 34211 | 34213 | 34217 | 34231 | 34253 | 34259 | 34261 |
| 34267 | 34273 | 34283 | 34297 | 34301 | 34303 | 34313 | 34319 | 34327 | 34337 | 34351 | 34361 | 34367 | 34369 | 34381 | 34403 | 34421 | 34429 | 34439 | 34457 |
| 34469 | 34471 | 34483 | 34487 | 34499 | 34501 | 34511 | 34513 | 34519 | 34537 | 34543 | 34549 | 34583 | 34589 | 34591 | 34603 | 34607 | 34613 | 34631 | 34649 |
| 34651 | 34667 | 34673 | 34679 | 34687 | 34693 | 34703 | 34721 | 34729 | 34739 | 34747 | 34757 | 34759 | 34763 | 34781 | 34807 | 34819 | 34841 | 34843 | 34847 |
| 34849 | 34871 | 34877 | 34883 | 34897 | 34913 | 34919 | 34939 | 34949 | 34961 | 34963 | 34981 | 35023 | 35027 | 35051 | 35053 | 35059 | 35069 | 35081 | 35083 |
| 35089 | 35099 | 35107 | 35111 | 35117 | 35129 | 35141 | 35149 | 35153 | 35159 | 35171 | 35201 | 35221 | 35227 | 35251 | 35257 | 35267 | 35279 | 35281 | 35291 |
| 35311 | 35317 | 35323 | 35327 | 35339 | 35353 | 35363 | 35381 | 35393 | 35401 | 35407 | 35419 | 35423 | 35437 | 35447 | 35449 | 35461 | 35491 | 35507 | 35509 |
| 35521 | 35527 | 35531 | 35533 | 35537 | 35543 | 35569 | 35573 | 35591 | 35593 | 35597 | 35603 | 35617 | 35671 | 35677 | 35729 | 35731 | 35747 | 35753 | 35759 |
| 35771 | 35797 | 35801 | 35803 | 35809 | 35831 | 35837 | 35839 | 35851 | 35863 | 35869 | 35879 | 35897 | 35899 | 35911 | 35923 | 35933 | 35951 | 35963 | 35969 |
| 35977 | 35983 | 35993 | 35999 | 36007 | 36011 | 36013 | 36017 | 36037 | 36061 | 36067 | 36073 | 36083 | 36097 | 36107 | 36109 | 36131 | 36137 | 36151 | 36161 |
| 36187 | 36191 | 36209 | 36217 | 36229 | 36241 | 36251 | 36263 | 36269 | 36277 | 36293 | 36299 | 36307 | 36313 | 36319 | 36341 | 36343 | 36353 | 36373 | 36383 |
| 36389 | 36433 | 36451 | 36457 | 36467 | 36469 | 36473 | 36479 | 36493 | 36497 | 36523 | 36527 | 36529 | 36541 | 36551 | 36559 | 36563 | 36571 | 36583 | 36587 |
| 36599 | 36607 | 36629 | 36637 | 36643 | 36653 | 36671 | 36677 | 36683 | 36691 | 36697 | 36709 | 36713 | 36721 | 36739 | 36749 | 36761 | 36767 | 36779 | 36781 |
| 36787 | 36791 | 36793 | 36809 | 36821 | 36833 | 36847 | 36857 | 36871 | 36877 | 36887 | 36899 | 36901 | 36913 | 36919 | 36923 | 36929 | 36931 | 36943 | 36947 |
| 36973 | 36979 | 36997 | 37003 | 37013 | 37019 | 37021 | 37039 | 37049 | 37057 | 37061 | 37087 | 37097 | 37117 | 37123 | 37139 | 37159 | 37171 | 37181 | 37189 |
| 37199 | 37201 | 37217 | 37223 | 37243 | 37253 | 37273 | 37277 | 37307 | 37309 | 37313 | 37321 | 37337 | 37339 | 37357 | 37361 | 37363 | 37369 | 37379 | 37397 |
| 37409 | 37423 | 37441 | 37447 | 37463 | 37483 | 37489 | 37493 | 37501 | 37507 | 37511 | 37517 | 37529 | 37537 | 37547 | 37549 | 37561 | 37567 | 37571 | 37573 |
| 37579 | 37589 | 37591 | 37607 | 37619 | 37633 | 37643 | 37649 | 37657 | 37663 | 37691 | 37693 | 37699 | 37717 | 37747 | 37781 | 37783 | 37799 | 37811 | 37813 |
| 37831 | 37847 | 37853 | 37861 | 37871 | 37879 | 37889 | 37897 | 37907 | 37951 | 37957 | 37963 | 37967 | 37987 | 37991 | 37993 | 37997 | 38011 | 38039 | 38047 |
| 38053 | 38069 | 38083 | 38113 | 38119 | 38149 | 38153 | 38167 | 38177 | 38183 | 38189 | 38197 | 38201 | 38219 | 38231 | 38237 | 38239 | 38261 | 38273 | 38281 |
| 38287 | 38299 | 38303 | 38317 | 38321 | 38327 | 38329 | 38333 | 38351 | 38371 | 38377 | 38393 | 38431 | 38447 | 38449 | 38453 | 38459 | 38461 | 38501 | 38543 |
| 38557 | 38561 | 38567 | 38569 | 38593 | 38603 | 38609 | 38611 | 38629 | 38639 | 38651 | 38653 | 38669 | 38671 | 38677 | 38693 | 38699 | 38707 | 38711 | 38713 |
| 38723 | 38729 | 38737 | 38747 | 38749 | 38767 | 38783 | 38791 | 38803 | 38821 | 38833 | 38839 | 38851 | 38861 | 38867 | 38873 | 38891 | 38903 | 38917 | 38921 |
| 38923 | 38933 | 38953 | 38959 | 38971 | 38977 | 38993 | 39019 | 39023 | 39041 | 39043 | 39047 | 39079 | 39089 | 39097 | 39103 | 39107 | 39113 | 39119 | 39133 |
| 39139 | 39157 | 39161 | 39163 | 39181 | 39191 | 39199 | 39209 | 39217 | 39227 | 39229 | 39233 | 39239 | 39241 | 39251 | 39293 | 39301 | 39313 | 39317 | 39323 |
| 39341 | 39343 | 39359 | 39367 | 39371 | 39373 | 39383 | 39397 | 39409 | 39419 | 39439 | 39443 | 39451 | 39461 | 39499 | 39503 | 39509 | 39511 | 39521 | 39541 |
| 39551 | 39563 | 39569 | 39581 | 39607 | 39619 | 39623 | 39631 | 39659 | 39667 | 39671 | 39679 | 39703 | 39709 | 39719 | 39727 | 39733 | 39749 | 39761 | 39769 |
| 39779 | 39791 | 39799 | 39821 | 39827 | 39829 | 39839 | 39841 | 39847 | 39857 | 39863 | 39869 | 39877 | 39883 | 39887 | 39901 | 39929 | 39937 | 39953 | 39971 |
| 39979 | 39983 | 39989 | 40009 | 40013 | 40031 | 40037 | 40039 | 40063 | 40087 | 40093 | 40099 | 40111 | 40123 | 40127 | 40129 | 40151 | 40153 | 40163 | 40169 |
| 40177 | 40189 | 40193 | 40213 | 40231 | 40237 | 40241 | 40253 | 40277 | 40283 | 40289 | 40343 | 40351 | 40357 | 40361 | 40387 | 40423 | 40427 | 40429 | 40433 |
| 40459 | 40471 | 40483 | 40487 | 40493 | 40499 | 40507 | 40519 | 40529 | 40531 | 40543 | 40559 | 40577 | 40583 | 40591 | 40597 | 40609 | 40627 | 40637 | 40639 |
| 40693 | 40697 | 40699 | 40709 | 40739 | 40751 | 40759 | 40763 | 40771 | 40787 | 40801 | 40813 | 40819 | 40823 | 40829 | 40841 | 40847 | 40849 | 40853 | 40867 |
| 40879 | 40883 | 40897 | 40903 | 40927 | 40933 | 40939 | 40949 | 40961 | 40973 | 40993 | 41011 | 41017 | 41023 | 41039 | 41047 | 41051 | 41057 | 41077 | 41081 |
| 41113 | 41117 | 41131 | 41141 | 41143 | 41149 | 41161 | 41177 | 41179 | 41183 | 41189 | 41201 | 41203 | 41213 | 41221 | 41227 | 41231 | 41233 | 41243 | 41257 |
| 41263 | 41269 | 41281 | 41299 | 41333 | 41341 | 41351 | 41357 | 41381 | 41387 | 41389 | 41399 | 41411 | 41413 | 41443 | 41453 | 41467 | 41479 | 41491 | 41507 |
| 41513 | 41519 | 41521 | 41539 | 41543 | 41549 | 41579 | 41593 | 41597 | 41603 | 41609 | 41611 | 41617 | 41621 | 41627 | 41641 | 41647 | 41651 | 41659 | 41669 |
| 41681 | 41687 | 41719 | 41729 | 41737 | 41759 | 41761 | 41771 | 41777 | 41801 | 41809 | 41813 | 41843 | 41849 | 41851 | 41863 | 41879 | 41887 | 41893 | 41897 |
| 41903 | 41911 | 41927 | 41941 | 41947 | 41953 | 41957 | 41959 | 41969 | 41981 | 41983 | 41999 | 42013 | 42017 | 42019 | 42023 | 42043 | 42061 | 42071 | 42073 |
| 42083 | 42089 | 42101 | 42131 | 42139 | 42157 | 42169 | 42179 | 42181 | 42187 | 42193 | 42197 | 42209 | 42221 | 42223 | 42227 | 42239 | 42257 | 42281 | 42283 |
| 42293 | 42299 | 42307 | 42323 | 42331 | 42337 | 42349 | 42359 | 42373 | 42379 | 42391 | 42397 | 42403 | 42407 | 42409 | 42433 | 42437 | 42443 | 42451 | 42457 |
| 42461 | 42463 | 42467 | 42473 | 42487 | 42491 | 42499 | 42509 | 42533 | 42557 | 42569 | 42571 | 42577 | 42589 | 42611 | 42641 | 42643 | 42649 | 42667 | 42677 |
| 42683 | 42689 | 42697 | 42701 | 42703 | 42709 | 42719 | 42727 | 42737 | 42743 | 42751 | 42767 | 42773 | 42787 | 42793 | 42797 | 42821 | 42829 | 42839 | 42841 |
| 42853 | 42859 | 42863 | 42899 | 42901 | 42923 | 42929 | 42937 | 42943 | 42953 | 42961 | 42967 | 42979 | 42989 | 43003 | 43013 | 43019 | 43037 | 43049 | 43051 |
| 43063 | 43067 | 43093 | 43103 | 43117 | 43133 | 43151 | 43159 | 43177 | 43189 | 43201 | 43207 | 43223 | 43237 | 43261 | 43271 | 43283 | 43291 | 43313 | 43319 |
| 43321 | 43331 | 43391 | 43397 | 43399 | 43403 | 43411 | 43427 | 43441 | 43451 | 43457 | 43481 | 43487 | 43499 | 43517 | 43541 | 43543 | 43573 | 43577 | 43579 |
| 43591 | 43597 | 43607 | 43609 | 43613 | 43627 | 43633 | 43649 | 43651 | 43661 | 43669 | 43691 | 43711 | 43717 | 43721 | 43753 | 43759 | 43777 | 43781 | 43783 |
| 43787 | 43789 | 43793 | 43801 | 43853 | 43867 | 43889 | 43891 | 43913 | 43933 | 43943 | 43951 | 43961 | 43963 | 43969 | 43973 | 43987 | 43991 | 43997 | 44017 |
| 44021 | 44027 | 44029 | 44041 | 44053 | 44059 | 44071 | 44087 | 44089 | 44101 | 44111 | 44119 | 44123 | 44129 | 44131 | 44159 | 44171 | 44179 | 44189 | 44201 |
| 44203 | 44207 | 44221 | 44249 | 44257 | 44263 | 44267 | 44269 | 44273 | 44279 | 44281 | 44293 | 44351 | 44357 | 44371 | 44381 | 44383 | 44389 | 44417 | 44449 |
| 44453 | 44483 | 44491 | 44497 | 44501 | 44507 | 44519 | 44531 | 44533 | 44537 | 44543 | 44549 | 44563 | 44579 | 44587 | 44617 | 44621 | 44623 | 44633 | 44641 |
| 44647 | 44651 | 44657 | 44683 | 44687 | 44699 | 44701 | 44711 | 44729 | 44741 | 44753 | 44771 | 44773 | 44777 | 44789 | 44797 | 44809 | 44819 | 44839 | 44843 |
| 44851 | 44867 | 44879 | 44887 | 44893 | 44909 | 44917 | 44927 | 44939 | 44953 | 44959 | 44963 | 44971 | 44983 | 44987 | 45007 | 45013 | 45053 | 45061 | 45077 |
| 45083 | 45119 | 45121 | 45127 | 45131 | 45137 | 45139 | 45161 | 45179 | 45181 | 45191 | 45197 | 45233 | 45247 | 45259 | 45263 | 45281 | 45289 | 45293 | 45307 |
| 45317 | 45319 | 45329 | 45337 | 45341 | 45343 | 45361 | 45377 | 45389 | 45403 | 45413 | 45427 | 45433 | 45439 | 45481 | 45491 | 45497 | 45503 | 45523 | 45533 |
| 45541 | 45553 | 45557 | 45569 | 45587 | 45589 | 45599 | 45613 | 45631 | 45641 | 45659 | 45667 | 45673 | 45677 | 45691 | 45697 | 45707 | 45737 | 45751 | 45757 |
| 45763 | 45767 | 45779 | 45817 | 45821 | 45823 | 45827 | 45833 | 45841 | 45853 | 45863 | 45869 | 45887 | 45893 | 45943 | 45949 | 45953 | 45959 | 45971 | 45979 |
| 45989 | 46021 | 46027 | 46049 | 46051 | 46061 | 46073 | 46091 | 46093 | 46099 | 46103 | 46133 | 46141 | 46147 | 46153 | 46171 | 46181 | 46183 | 46187 | 46199 |
| 46219 | 46229 | 46237 | 46261 | 46271 | 46273 | 46279 | 46301 | 46307 | 46309 | 46327 | 46337 | 46349 | 46351 | 46381 | 46399 | 46411 | 46439 | 46441 | 46447 |
| 46451 | 46457 | 46471 | 46477 | 46489 | 46499 | 46507 | 46511 | 46523 | 46549 | 46559 | 46567 | 46573 | 46589 | 46591 | 46601 | 46619 | 46633 | 46639 | 46643 |
| 46649 | 46663 | 46679 | 46681 | 46687 | 46691 | 46703 | 46723 | 46727 | 46747 | 46751 | 46757 | 46769 | 46771 | 46807 | 46811 | 46817 | 46819 | 46829 | 46831 |
| 46853 | 46861 | 46867 | 46877 | 46889 | 46901 | 46919 | 46933 | 46957 | 46993 | 46997 | 47017 | 47041 | 47051 | 47057 | 47059 | 47087 | 47093 | 47111 | 47119 |
| 47123 | 47129 | 47137 | 47143 | 47147 | 47149 | 47161 | 47189 | 47207 | 47221 | 47237 | 47251 | 47269 | 47279 | 47287 | 47293 | 47297 | 47303 | 47309 | 47317 |
| 47339 | 47351 | 47353 | 47363 | 47381 | 47387 | 47389 | 47407 | 47417 | 47419 | 47431 | 47441 | 47459 | 47491 | 47497 | 47501 | 47507 | 47513 | 47521 | 47527 |
| 47533 | 47543 | 47563 | 47569 | 47581 | 47591 | 47599 | 47609 | 47623 | 47629 | 47639 | 47653 | 47657 | 47659 | 47681 | 47699 | 47701 | 47711 | 47713 | 47717 |
| 47737 | 47741 | 47743 | 47777 | 47779 | 47791 | 47797 | 47807 | 47809 | 47819 | 47837 | 47843 | 47857 | 47869 | 47881 | 47903 | 47911 | 47917 | 47933 | 47939 |
| 47947 | 47951 | 47963 | 47969 | 47977 | 47981 | 48017 | 48023 | 48029 | 48049 | 48073 | 48079 | 48091 | 48109 | 48119 | 48121 | 48131 | 48157 | 48163 | 48179 |
| 48187 | 48193 | 48197 | 48221 | 48239 | 48247 | 48259 | 48271 | 48281 | 48299 | 48311 | 48313 | 48337 | 48341 | 48353 | 48371 | 48383 | 48397 | 48407 | 48409 |
| 48413 | 48437 | 48449 | 48463 | 48473 | 48479 | 48481 | 48487 | 48491 | 48497 | 48523 | 48527 | 48533 | 48539 | 48541 | 48563 | 48571 | 48589 | 48593 | 48611 |
| 48619 | 48623 | 48647 | 48649 | 48661 | 48673 | 48677 | 48679 | 48731 | 48733 | 48751 | 48757 | 48761 | 48767 | 48779 | 48781 | 48787 | 48799 | 48809 | 48817 |
| 48821 | 48823 | 48847 | 48857 | 48859 | 48869 | 48871 | 48883 | 48889 | 48907 | 48947 | 48953 | 48973 | 48989 | 48991 | 49003 | 49009 | 49019 | 49031 | 49033 |
| 49037 | 49043 | 49057 | 49069 | 49081 | 49103 | 49109 | 49117 | 49121 | 49123 | 49139 | 49157 | 49169 | 49171 | 49177 | 49193 | 49199 | 49201 | 49207 | 49211 |
| 49223 | 49253 | 49261 | 49277 | 49279 | 49297 | 49307 | 49331 | 49333 | 49339 | 49363 | 49367 | 49369 | 49391 | 49393 | 49409 | 49411 | 49417 | 49429 | 49433 |
| 49451 | 49459 | 49463 | 49477 | 49481 | 49499 | 49523 | 49529 | 49531 | 49537 | 49547 | 49549 | 49559 | 49597 | 49603 | 49613 | 49627 | 49633 | 49639 | 49663 |
| 49667 | 49669 | 49681 | 49697 | 49711 | 49727 | 49739 | 49741 | 49747 | 49757 | 49783 | 49787 | 49789 | 49801 | 49807 | 49811 | 49823 | 49831 | 49843 | 49853 |
| 49871 | 49877 | 49891 | 49919 | 49921 | 49927 | 49937 | 49939 | 49943 | 49957 | 49991 | 49993 | 49999 | 50021 | 50023 | 50033 | 50047 | 50051 | 50053 | 50069 |
| 50077 | 50087 | 50093 | 50101 | 50111 | 50119 | 50123 | 50129 | 50131 | 50147 | 50153 | 50159 | 50177 | 50207 | 50221 | 50227 | 50231 | 50261 | 50263 | 50273 |
| 50287 | 50291 | 50311 | 50321 | 50329 | 50333 | 50341 | 50359 | 50363 | 50377 | 50383 | 50387 | 50411 | 50417 | 50423 | 50441 | 50459 | 50461 | 50497 | 50503 |
| 50513 | 50527 | 50539 | 50543 | 50549 | 50551 | 50581 | 50587 | 50591 | 50593 | 50599 | 50627 | 50647 | 50651 | 50671 | 50683 | 50707 | 50723 | 50741 | 50753 |
| 50767 | 50773 | 50777 | 50789 | 50821 | 50833 | 50839 | 50849 | 50857 | 50867 | 50873 | 50891 | 50893 | 50909 | 50923 | 50929 | 50951 | 50957 | 50969 | 50971 |
| 50989 | 50993 | 51001 | 51031 | 51043 | 51047 | 51059 | 51061 | 51071 | 51109 | 51131 | 51133 | 51137 | 51151 | 51157 | 51169 | 51193 | 51197 | 51199 | 51203 |
| 51217 | 51229 | 51239 | 51241 | 51257 | 51263 | 51283 | 51287 | 51307 | 51329 | 51341 | 51343 | 51347 | 51349 | 51361 | 51383 | 51407 | 51413 | 51419 | 51421 |
| 51427 | 51431 | 51437 | 51439 | 51449 | 51461 | 51473 | 51479 | 51481 | 51487 | 51503 | 51511 | 51517 | 51521 | 51539 | 51551 | 51563 | 51577 | 51581 | 51593 |
| 51599 | 51607 | 51613 | 51631 | 51637 | 51647 | 51659 | 51673 | 51679 | 51683 | 51691 | 51713 | 51719 | 51721 | 51749 | 51767 | 51769 | 51787 | 51797 | 51803 |
| 51817 | 51827 | 51829 | 51839 | 51853 | 51859 | 51869 | 51871 | 51893 | 51899 | 51907 | 51913 | 51929 | 51941 | 51949 | 51971 | 51973 | 51977 | 51991 | 52009 |
| 52021 | 52027 | 52051 | 52057 | 52067 | 52069 | 52081 | 52103 | 52121 | 52127 | 52147 | 52153 | 52163 | 52177 | 52181 | 52183 | 52189 | 52201 | 52223 | 52237 |
| 52249 | 52253 | 52259 | 52267 | 52289 | 52291 | 52301 | 52313 | 52321 | 52361 | 52363 | 52369 | 52379 | 52387 | 52391 | 52433 | 52453 | 52457 | 52489 | 52501 |
| 52511 | 52517 | 52529 | 52541 | 52543 | 52553 | 52561 | 52567 | 52571 | 52579 | 52583 | 52609 | 52627 | 52631 | 52639 | 52667 | 52673 | 52691 | 52697 | 52709 |
| 52711 | 52721 | 52727 | 52733 | 52747 | 52757 | 52769 | 52783 | 52807 | 52813 | 52817 | 52837 | 52859 | 52861 | 52879 | 52883 | 52889 | 52901 | 52903 | 52919 |
| 52937 | 52951 | 52957 | 52963 | 52967 | 52973 | 52981 | 52999 | 53003 | 53017 | 53047 | 53051 | 53069 | 53077 | 53087 | 53089 | 53093 | 53101 | 53113 | 53117 |
| 53129 | 53147 | 53149 | 53161 | 53171 | 53173 | 53189 | 53197 | 53201 | 53231 | 53233 | 53239 | 53267 | 53269 | 53279 | 53281 | 53299 | 53309 | 53323 | 53327 |
| 53353 | 53359 | 53377 | 53381 | 53401 | 53407 | 53411 | 53419 | 53437 | 53441 | 53453 | 53479 | 53503 | 53507 | 53527 | 53549 | 53551 | 53569 | 53591 | 53593 |
| 53597 | 53609 | 53611 | 53617 | 53623 | 53629 | 53633 | 53639 | 53653 | 53657 | 53681 | 53693 | 53699 | 53717 | 53719 | 53731 | 53759 | 53773 | 53777 | 53783 |
| 53791 | 53813 | 53819 | 53831 | 53849 | 53857 | 53861 | 53881 | 53887 | 53891 | 53897 | 53899 | 53917 | 53923 | 53927 | 53939 | 53951 | 53959 | 53987 | 53993 |
| 54001 | 54011 | 54013 | 54037 | 54049 | 54059 | 54083 | 54091 | 54101 | 54121 | 54133 | 54139 | 54151 | 54163 | 54167 | 54181 | 54193 | 54217 | 54251 | 54269 |
| 54277 | 54287 | 54293 | 54311 | 54319 | 54323 | 54331 | 54347 | 54361 | 54367 | 54371 | 54377 | 54401 | 54403 | 54409 | 54413 | 54419 | 54421 | 54437 | 54443 |
| 54449 | 54469 | 54493 | 54497 | 54499 | 54503 | 54517 | 54521 | 54539 | 54541 | 54547 | 54559 | 54563 | 54577 | 54581 | 54583 | 54601 | 54617 | 54623 | 54629 |
| 54631 | 54647 | 54667 | 54673 | 54679 | 54709 | 54713 | 54721 | 54727 | 54751 | 54767 | 54773 | 54779 | 54787 | 54799 | 54829 | 54833 | 54851 | 54869 | 54877 |
| 54881 | 54907 | 54917 | 54919 | 54941 | 54949 | 54959 | 54973 | 54979 | 54983 | 55001 | 55009 | 55021 | 55049 | 55051 | 55057 | 55061 | 55073 | 55079 | 55103 |
| 55109 | 55117 | 55127 | 55147 | 55163 | 55171 | 55201 | 55207 | 55213 | 55217 | 55219 | 55229 | 55243 | 55249 | 55259 | 55291 | 55313 | 55331 | 55333 | 55337 |
| 55339 | 55343 | 55351 | 55373 | 55381 | 55399 | 55411 | 55439 | 55441 | 55457 | 55469 | 55487 | 55501 | 55511 | 55529 | 55541 | 55547 | 55579 | 55589 | 55603 |
| 55609 | 55619 | 55621 | 55631 | 55633 | 55639 | 55661 | 55663 | 55667 | 55673 | 55681 | 55691 | 55697 | 55711 | 55717 | 55721 | 55733 | 55763 | 55787 | 55793 |
| 55799 | 55807 | 55813 | 55817 | 55819 | 55823 | 55829 | 55837 | 55843 | 55849 | 55871 | 55889 | 55897 | 55901 | 55903 | 55921 | 55927 | 55931 | 55933 | 55949 |
| 55967 | 55987 | 55997 | 56003 | 56009 | 56039 | 56041 | 56053 | 56081 | 56087 | 56093 | 56099 | 56101 | 56113 | 56123 | 56131 | 56149 | 56167 | 56171 | 56179 |
| 56197 | 56207 | 56209 | 56237 | 56239 | 56249 | 56263 | 56267 | 56269 | 56299 | 56311 | 56333 | 56359 | 56369 | 56377 | 56383 | 56393 | 56401 | 56417 | 56431 |
| 56437 | 56443 | 56453 | 56467 | 56473 | 56477 | 56479 | 56489 | 56501 | 56503 | 56509 | 56519 | 56527 | 56531 | 56533 | 56543 | 56569 | 56591 | 56597 | 56599 |
| 56611 | 56629 | 56633 | 56659 | 56663 | 56671 | 56681 | 56687 | 56701 | 56711 | 56713 | 56731 | 56737 | 56747 | 56767 | 56773 | 56779 | 56783 | 56807 | 56809 |
| 56813 | 56821 | 56827 | 56843 | 56857 | 56873 | 56891 | 56893 | 56897 | 56909 | 56911 | 56921 | 56923 | 56929 | 56941 | 56951 | 56957 | 56963 | 56983 | 56989 |
| 56993 | 56999 | 57037 | 57041 | 57047 | 57059 | 57073 | 57077 | 57089 | 57097 | 57107 | 57119 | 57131 | 57139 | 57143 | 57149 | 57163 | 57173 | 57179 | 57191 |
| 57193 | 57203 | 57221 | 57223 | 57241 | 57251 | 57259 | 57269 | 57271 | 57283 | 57287 | 57301 | 57329 | 57331 | 57347 | 57349 | 57367 | 57373 | 57383 | 57389 |
| 57397 | 57413 | 57427 | 57457 | 57467 | 57487 | 57493 | 57503 | 57527 | 57529 | 57557 | 57559 | 57571 | 57587 | 57593 | 57601 | 57637 | 57641 | 57649 | 57653 |
| 57667 | 57679 | 57689 | 57697 | 57709 | 57713 | 57719 | 57727 | 57731 | 57737 | 57751 | 57773 | 57781 | 57787 | 57791 | 57793 | 57803 | 57809 | 57829 | 57839 |
| 57847 | 57853 | 57859 | 57881 | 57899 | 57901 | 57917 | 57923 | 57943 | 57947 | 57973 | 57977 | 57991 | 58013 | 58027 | 58031 | 58043 | 58049 | 58057 | 58061 |
| 58067 | 58073 | 58099 | 58109 | 58111 | 58129 | 58147 | 58151 | 58153 | 58169 | 58171 | 58189 | 58193 | 58199 | 58207 | 58211 | 58217 | 58229 | 58231 | 58237 |
| 58243 | 58271 | 58309 | 58313 | 58321 | 58337 | 58363 | 58367 | 58369 | 58379 | 58391 | 58393 | 58403 | 58411 | 58417 | 58427 | 58439 | 58441 | 58451 | 58453 |
| 58477 | 58481 | 58511 | 58537 | 58543 | 58549 | 58567 | 58573 | 58579 | 58601 | 58603 | 58613 | 58631 | 58657 | 58661 | 58679 | 58687 | 58693 | 58699 | 58711 |
| 58727 | 58733 | 58741 | 58757 | 58763 | 58771 | 58787 | 58789 | 58831 | 58889 | 58897 | 58901 | 58907 | 58909 | 58913 | 58921 | 58937 | 58943 | 58963 | 58967 |
| 58979 | 58991 | 58997 | 59009 | 59011 | 59021 | 59023 | 59029 | 59051 | 59053 | 59063 | 59069 | 59077 | 59083 | 59093 | 59107 | 59113 | 59119 | 59123 | 59141 |
| 59149 | 59159 | 59167 | 59183 | 59197 | 59207 | 59209 | 59219 | 59221 | 59233 | 59239 | 59243 | 59263 | 59273 | 59281 | 59333 | 59341 | 59351 | 59357 | 59359 |
| 59369 | 59377 | 59387 | 59393 | 59399 | 59407 | 59417 | 59419 | 59441 | 59443 | 59447 | 59453 | 59467 | 59471 | 59473 | 59497 | 59509 | 59513 | 59539 | 59557 |
| 59561 | 59567 | 59581 | 59611 | 59617 | 59621 | 59627 | 59629 | 59651 | 59659 | 59663 | 59669 | 59671 | 59693 | 59699 | 59707 | 59723 | 59729 | 59743 | 59747 |
| 59753 | 59771 | 59779 | 59791 | 59797 | 59809 | 59833 | 59863 | 59879 | 59887 | 59921 | 59929 | 59951 | 59957 | 59971 | 59981 | 59999 | 60013 | 60017 | 60029 |
| 60037 | 60041 | 60077 | 60083 | 60089 | 60091 | 60101 | 60103 | 60107 | 60127 | 60133 | 60139 | 60149 | 60161 | 60167 | 60169 | 60209 | 60217 | 60223 | 60251 |
| 60257 | 60259 | 60271 | 60289 | 60293 | 60317 | 60331 | 60337 | 60343 | 60353 | 60373 | 60383 | 60397 | 60413 | 60427 | 60443 | 60449 | 60457 | 60493 | 60497 |
| 60509 | 60521 | 60527 | 60539 | 60589 | 60601 | 60607 | 60611 | 60617 | 60623 | 60631 | 60637 | 60647 | 60649 | 60659 | 60661 | 60679 | 60689 | 60703 | 60719 |
| 60727 | 60733 | 60737 | 60757 | 60761 | 60763 | 60773 | 60779 | 60793 | 60811 | 60821 | 60859 | 60869 | 60887 | 60889 | 60899 | 60901 | 60913 | 60917 | 60919 |
| 60923 | 60937 | 60943 | 60953 | 60961 | 61001 | 61007 | 61027 | 61031 | 61043 | 61051 | 61057 | 61091 | 61099 | 61121 | 61129 | 61141 | 61151 | 61153 | 61169 |
| 61211 | 61223 | 61231 | 61253 | 61261 | 61283 | 61291 | 61297 | 61331 | 61333 | 61339 | 61343 | 61357 | 61363 | 61379 | 61381 | 61403 | 61409 | 61417 | 61441 |
| 61463 | 61469 | 61471 | 61483 | 61487 | 61493 | 61507 | 61511 | 61519 | 61543 | 61547 | 61553 | 61559 | 61561 | 61583 | 61603 | 61609 | 61613 | 61627 | 61631 |
| 61637 | 61643 | 61651 | 61657 | 61667 | 61673 | 61681 | 61687 | 61703 | 61717 | 61723 | 61729 | 61751 | 61757 | 61781 | 61813 | 61819 | 61837 | 61843 | 61861 |
| 61871 | 61879 | 61909 | 61927 | 61933 | 61949 | 61961 | 61967 | 61979 | 61981 | 61987 | 61991 | 62003 | 62011 | 62017 | 62039 | 62047 | 62053 | 62057 | 62071 |
| 62081 | 62099 | 62119 | 62129 | 62131 | 62137 | 62141 | 62143 | 62171 | 62189 | 62191 | 62201 | 62207 | 62213 | 62219 | 62233 | 62273 | 62297 | 62299 | 62303 |
| 62311 | 62323 | 62327 | 62347 | 62351 | 62383 | 62401 | 62417 | 62423 | 62459 | 62467 | 62473 | 62477 | 62483 | 62497 | 62501 | 62507 | 62533 | 62539 | 62549 |
| 62563 | 62581 | 62591 | 62597 | 62603 | 62617 | 62627 | 62633 | 62639 | 62653 | 62659 | 62683 | 62687 | 62701 | 62723 | 62731 | 62743 | 62753 | 62761 | 62773 |
| 62791 | 62801 | 62819 | 62827 | 62851 | 62861 | 62869 | 62873 | 62897 | 62903 | 62921 | 62927 | 62929 | 62939 | 62969 | 62971 | 62981 | 62983 | 62987 | 62989 |
| 63029 | 63031 | 63059 | 63067 | 63073 | 63079 | 63097 | 63103 | 63113 | 63127 | 63131 | 63149 | 63179 | 63197 | 63199 | 63211 | 63241 | 63247 | 63277 | 63281 |
| 63299 | 63311 | 63313 | 63317 | 63331 | 63337 | 63347 | 63353 | 63361 | 63367 | 63377 | 63389 | 63391 | 63397 | 63409 | 63419 | 63421 | 63439 | 63443 | 63463 |
| 63467 | 63473 | 63487 | 63493 | 63499 | 63521 | 63527 | 63533 | 63541 | 63559 | 63577 | 63587 | 63589 | 63599 | 63601 | 63607 | 63611 | 63617 | 63629 | 63647 |
| 63649 | 63659 | 63667 | 63671 | 63689 | 63691 | 63697 | 63703 | 63709 | 63719 | 63727 | 63737 | 63743 | 63761 | 63773 | 63781 | 63793 | 63799 | 63803 | 63809 |
| 63823 | 63839 | 63841 | 63853 | 63857 | 63863 | 63901 | 63907 | 63913 | 63929 | 63949 | 63977 | 63997 | 64007 | 64013 | 64019 | 64033 | 64037 | 64063 | 64067 |
| 64081 | 64091 | 64109 | 64123 | 64151 | 64153 | 64157 | 64171 | 64187 | 64189 | 64217 | 64223 | 64231 | 64237 | 64271 | 64279 | 64283 | 64301 | 64303 | 64319 |
| 64327 | 64333 | 64373 | 64381 | 64399 | 64403 | 64433 | 64439 | 64451 | 64453 | 64483 | 64489 | 64499 | 64513 | 64553 | 64567 | 64577 | 64579 | 64591 | 64601 |
| 64609 | 64613 | 64621 | 64627 | 64633 | 64661 | 64663 | 64667 | 64679 | 64693 | 64709 | 64717 | 64747 | 64763 | 64781 | 64783 | 64793 | 64811 | 64817 | 64849 |
| 64853 | 64871 | 64877 | 64879 | 64891 | 64901 | 64919 | 64921 | 64927 | 64937 | 64951 | 64969 | 64997 | 65003 | 65011 | 65027 | 65029 | 65033 | 65053 | 65063 |
| 65071 | 65089 | 65099 | 65101 | 65111 | 65119 | 65123 | 65129 | 65141 | 65147 | 65167 | 65171 | 65173 | 65179 | 65183 | 65203 | 65213 | 65239 | 65257 | 65267 |
| 65269 | 65287 | 65293 | 65309 | 65323 | 65327 | 65353 | 65357 | 65371 | 65381 | 65393 | 65407 | 65413 | 65419 | 65423 | 65437 | 65447 | 65449 | 65479 | 65497 |
| 65519 | 65521 | 65537 | 65539 | 65543 | 65551 | 65557 | 65563 | 65579 | 65581 | 65587 | 65599 | 65609 | 65617 | 65629 | 65633 | 65647 | 65651 | 65657 | 65677 |
| 65687 | 65699 | 65701 | 65707 | 65713 | 65717 | 65719 | 65729 | 65731 | 65761 | 65777 | 65789 | 65809 | 65827 | 65831 | 65837 | 65839 | 65843 | 65851 | 65867 |
| 65881 | 65899 | 65921 | 65927 | 65929 | 65951 | 65957 | 65963 | 65981 | 65983 | 65993 | 66029 | 66037 | 66041 | 66047 | 66067 | 66071 | 66083 | 66089 | 66103 |
| 66107 | 66109 | 66137 | 66161 | 66169 | 66173 | 66179 | 66191 | 66221 | 66239 | 66271 | 66293 | 66301 | 66337 | 66343 | 66347 | 66359 | 66361 | 66373 | 66377 |
| 66383 | 66403 | 66413 | 66431 | 66449 | 66457 | 66463 | 66467 | 66491 | 66499 | 66509 | 66523 | 66529 | 66533 | 66541 | 66553 | 66569 | 66571 | 66587 | 66593 |
| 66601 | 66617 | 66629 | 66643 | 66653 | 66683 | 66697 | 66701 | 66713 | 66721 | 66733 | 66739 | 66749 | 66751 | 66763 | 66791 | 66797 | 66809 | 66821 | 66841 |
| 66851 | 66853 | 66863 | 66877 | 66883 | 66889 | 66919 | 66923 | 66931 | 66943 | 66947 | 66949 | 66959 | 66973 | 66977 | 67003 | 67021 | 67033 | 67043 | 67049 |
| 67057 | 67061 | 67073 | 67079 | 67103 | 67121 | 67129 | 67139 | 67141 | 67153 | 67157 | 67169 | 67181 | 67187 | 67189 | 67211 | 67213 | 67217 | 67219 | 67231 |
| 67247 | 67261 | 67271 | 67273 | 67289 | 67307 | 67339 | 67343 | 67349 | 67369 | 67391 | 67399 | 67409 | 67411 | 67421 | 67427 | 67429 | 67433 | 67447 | 67453 |
| 67477 | 67481 | 67489 | 67493 | 67499 | 67511 | 67523 | 67531 | 67537 | 67547 | 67559 | 67567 | 67577 | 67579 | 67589 | 67601 | 67607 | 67619 | 67631 | 67651 |
| 67679 | 67699 | 67709 | 67723 | 67733 | 67741 | 67751 | 67757 | 67759 | 67763 | 67777 | 67783 | 67789 | 67801 | 67807 | 67819 | 67829 | 67843 | 67853 | 67867 |
| 67883 | 67891 | 67901 | 67927 | 67931 | 67933 | 67939 | 67943 | 67957 | 67961 | 67967 | 67979 | 67987 | 67993 | 68023 | 68041 | 68053 | 68059 | 68071 | 68087 |
| 68099 | 68111 | 68113 | 68141 | 68147 | 68161 | 68171 | 68207 | 68209 | 68213 | 68219 | 68227 | 68239 | 68261 | 68279 | 68281 | 68311 | 68329 | 68351 | 68371 |
| 68389 | 68399 | 68437 | 68443 | 68447 | 68449 | 68473 | 68477 | 68483 | 68489 | 68491 | 68501 | 68507 | 68521 | 68531 | 68539 | 68543 | 68567 | 68581 | 68597 |
| 68611 | 68633 | 68639 | 68659 | 68669 | 68683 | 68687 | 68699 | 68711 | 68713 | 68729 | 68737 | 68743 | 68749 | 68767 | 68771 | 68777 | 68791 | 68813 | 68819 |
| 68821 | 68863 | 68879 | 68881 | 68891 | 68897 | 68899 | 68903 | 68909 | 68917 | 68927 | 68947 | 68963 | 68993 | 69001 | 69011 | 69019 | 69029 | 69031 | 69061 |
| 69067 | 69073 | 69109 | 69119 | 69127 | 69143 | 69149 | 69151 | 69163 | 69191 | 69193 | 69197 | 69203 | 69221 | 69233 | 69239 | 69247 | 69257 | 69259 | 69263 |
| 69313 | 69317 | 69337 | 69341 | 69371 | 69379 | 69383 | 69389 | 69401 | 69403 | 69427 | 69431 | 69439 | 69457 | 69463 | 69467 | 69473 | 69481 | 69491 | 69493 |
| 69497 | 69499 | 69539 | 69557 | 69593 | 69623 | 69653 | 69661 | 69677 | 69691 | 69697 | 69709 | 69737 | 69739 | 69761 | 69763 | 69767 | 69779 | 69809 | 69821 |
| 69827 | 69829 | 69833 | 69847 | 69857 | 69859 | 69877 | 69899 | 69911 | 69929 | 69931 | 69941 | 69959 | 69991 | 69997 | 70001 | 70003 | 70009 | 70019 | 70039 |
| 70051 | 70061 | 70067 | 70079 | 70099 | 70111 | 70117 | 70121 | 70123 | 70139 | 70141 | 70157 | 70163 | 70177 | 70181 | 70183 | 70199 | 70201 | 70207 | 70223 |
| 70229 | 70237 | 70241 | 70249 | 70271 | 70289 | 70297 | 70309 | 70313 | 70321 | 70327 | 70351 | 70373 | 70379 | 70381 | 70393 | 70423 | 70429 | 70439 | 70451 |
| 70457 | 70459 | 70481 | 70487 | 70489 | 70501 | 70507 | 70529 | 70537 | 70549 | 70571 | 70573 | 70583 | 70589 | 70607 | 70619 | 70621 | 70627 | 70639 | 70657 |
| 70663 | 70667 | 70687 | 70709 | 70717 | 70729 | 70753 | 70769 | 70783 | 70793 | 70823 | 70841 | 70843 | 70849 | 70853 | 70867 | 70877 | 70879 | 70891 | 70901 |
| 70913 | 70919 | 70921 | 70937 | 70949 | 70951 | 70957 | 70969 | 70979 | 70981 | 70991 | 70997 | 70999 | 71011 | 71023 | 71039 | 71059 | 71069 | 71081 | 71089 |
| 71119 | 71129 | 71143 | 71147 | 71153 | 71161 | 71167 | 71171 | 71191 | 71209 | 71233 | 71237 | 71249 | 71257 | 71261 | 71263 | 71287 | 71293 | 71317 | 71327 |
| 71329 | 71333 | 71339 | 71341 | 71347 | 71353 | 71359 | 71363 | 71387 | 71389 | 71399 | 71411 | 71413 | 71419 | 71429 | 71437 | 71443 | 71453 | 71471 | 71473 |
| 71479 | 71483 | 71503 | 71527 | 71537 | 71549 | 71551 | 71563 | 71569 | 71593 | 71597 | 71633 | 71647 | 71663 | 71671 | 71693 | 71699 | 71707 | 71711 | 71713 |
| 71719 | 71741 | 71761 | 71777 | 71789 | 71807 | 71809 | 71821 | 71837 | 71843 | 71849 | 71861 | 71867 | 71879 | 71881 | 71887 | 71899 | 71909 | 71917 | 71933 |
| 71941 | 71947 | 71963 | 71971 | 71983 | 71987 | 71993 | 71999 | 72019 | 72031 | 72043 | 72047 | 72053 | 72073 | 72077 | 72089 | 72091 | 72101 | 72103 | 72109 |
| 72139 | 72161 | 72167 | 72169 | 72173 | 72211 | 72221 | 72223 | 72227 | 72229 | 72251 | 72253 | 72269 | 72271 | 72277 | 72287 | 72307 | 72313 | 72337 | 72341 |
| 72353 | 72367 | 72379 | 72383 | 72421 | 72431 | 72461 | 72467 | 72469 | 72481 | 72493 | 72497 | 72503 | 72533 | 72547 | 72551 | 72559 | 72577 | 72613 | 72617 |
| 72623 | 72643 | 72647 | 72649 | 72661 | 72671 | 72673 | 72679 | 72689 | 72701 | 72707 | 72719 | 72727 | 72733 | 72739 | 72763 | 72767 | 72797 | 72817 | 72823 |
| 72859 | 72869 | 72871 | 72883 | 72889 | 72893 | 72901 | 72907 | 72911 | 72923 | 72931 | 72937 | 72949 | 72953 | 72959 | 72973 | 72977 | 72997 | 73009 | 73013 |
| 73019 | 73037 | 73039 | 73043 | 73061 | 73063 | 73079 | 73091 | 73121 | 73127 | 73133 | 73141 | 73181 | 73189 | 73237 | 73243 | 73259 | 73277 | 73291 | 73303 |
| 73309 | 73327 | 73331 | 73351 | 73361 | 73363 | 73369 | 73379 | 73387 | 73417 | 73421 | 73433 | 73453 | 73459 | 73471 | 73477 | 73483 | 73517 | 73523 | 73529 |
| 73547 | 73553 | 73561 | 73571 | 73583 | 73589 | 73597 | 73607 | 73609 | 73613 | 73637 | 73643 | 73651 | 73673 | 73679 | 73681 | 73693 | 73699 | 73709 | 73721 |
| 73727 | 73751 | 73757 | 73771 | 73783 | 73819 | 73823 | 73847 | 73849 | 73859 | 73867 | 73877 | 73883 | 73897 | 73907 | 73939 | 73943 | 73951 | 73961 | 73973 |
| 73999 | 74017 | 74021 | 74027 | 74047 | 74051 | 74071 | 74077 | 74093 | 74099 | 74101 | 74131 | 74143 | 74149 | 74159 | 74161 | 74167 | 74177 | 74189 | 74197 |
| 74201 | 74203 | 74209 | 74219 | 74231 | 74257 | 74279 | 74287 | 74293 | 74297 | 74311 | 74317 | 74323 | 74353 | 74357 | 74363 | 74377 | 74381 | 74383 | 74411 |
| 74413 | 74419 | 74441 | 74449 | 74453 | 74471 | 74489 | 74507 | 74509 | 74521 | 74527 | 74531 | 74551 | 74561 | 74567 | 74573 | 74587 | 74597 | 74609 | 74611 |
| 74623 | 74653 | 74687 | 74699 | 74707 | 74713 | 74717 | 74719 | 74729 | 74731 | 74747 | 74759 | 74761 | 74771 | 74779 | 74797 | 74821 | 74827 | 74831 | 74843 |
| 74857 | 74861 | 74869 | 74873 | 74887 | 74891 | 74897 | 74903 | 74923 | 74929 | 74933 | 74941 | 74959 | 75011 | 75013 | 75017 | 75029 | 75037 | 75041 | 75079 |
| 75083 | 75109 | 75133 | 75149 | 75161 | 75167 | 75169 | 75181 | 75193 | 75209 | 75211 | 75217 | 75223 | 75227 | 75239 | 75253 | 75269 | 75277 | 75289 | 75307 |
| 75323 | 75329 | 75337 | 75347 | 75353 | 75367 | 75377 | 75389 | 75391 | 75401 | 75403 | 75407 | 75431 | 75437 | 75479 | 75503 | 75511 | 75521 | 75527 | 75533 |
| 75539 | 75541 | 75553 | 75557 | 75571 | 75577 | 75583 | 75611 | 75617 | 75619 | 75629 | 75641 | 75653 | 75659 | 75679 | 75683 | 75689 | 75703 | 75707 | 75709 |
| 75721 | 75731 | 75743 | 75767 | 75773 | 75781 | 75787 | 75793 | 75797 | 75821 | 75833 | 75853 | 75869 | 75883 | 75913 | 75931 | 75937 | 75941 | 75967 | 75979 |
| 75983 | 75989 | 75991 | 75997 | 76001 | 76003 | 76031 | 76039 | 76079 | 76081 | 76091 | 76099 | 76103 | 76123 | 76129 | 76147 | 76157 | 76159 | 76163 | 76207 |
| 76213 | 76231 | 76243 | 76249 | 76253 | 76259 | 76261 | 76283 | 76289 | 76303 | 76333 | 76343 | 76367 | 76369 | 76379 | 76387 | 76403 | 76421 | 76423 | 76441 |
| 76463 | 76471 | 76481 | 76487 | 76493 | 76507 | 76511 | 76519 | 76537 | 76541 | 76543 | 76561 | 76579 | 76597 | 76603 | 76607 | 76631 | 76649 | 76651 | 76667 |
| 76673 | 76679 | 76697 | 76717 | 76733 | 76753 | 76757 | 76771 | 76777 | 76781 | 76801 | 76819 | 76829 | 76831 | 76837 | 76847 | 76871 | 76873 | 76883 | 76907 |
| 76913 | 76919 | 76943 | 76949 | 76961 | 76963 | 76991 | 77003 | 77017 | 77023 | 77029 | 77041 | 77047 | 77069 | 77081 | 77093 | 77101 | 77137 | 77141 | 77153 |
| 77167 | 77171 | 77191 | 77201 | 77213 | 77237 | 77239 | 77243 | 77249 | 77261 | 77263 | 77267 | 77269 | 77279 | 77291 | 77317 | 77323 | 77339 | 77347 | 77351 |
| 77359 | 77369 | 77377 | 77383 | 77417 | 77419 | 77431 | 77447 | 77471 | 77477 | 77479 | 77489 | 77491 | 77509 | 77513 | 77521 | 77527 | 77543 | 77549 | 77551 |
| 77557 | 77563 | 77569 | 77573 | 77587 | 77591 | 77611 | 77617 | 77621 | 77641 | 77647 | 77659 | 77681 | 77687 | 77689 | 77699 | 77711 | 77713 | 77719 | 77723 |
| 77731 | 77743 | 77747 | 77761 | 77773 | 77783 | 77797 | 77801 | 77813 | 77839 | 77849 | 77863 | 77867 | 77893 | 77899 | 77929 | 77933 | 77951 | 77969 | 77977 |
| 77983 | 77999 | 78007 | 78017 | 78031 | 78041 | 78049 | 78059 | 78079 | 78101 | 78121 | 78137 | 78139 | 78157 | 78163 | 78167 | 78173 | 78179 | 78191 | 78193 |
| 78203 | 78229 | 78233 | 78241 | 78259 | 78277 | 78283 | 78301 | 78307 | 78311 | 78317 | 78341 | 78347 | 78367 | 78401 | 78427 | 78437 | 78439 | 78467 | 78479 |
| 78487 | 78497 | 78509 | 78511 | 78517 | 78539 | 78541 | 78553 | 78569 | 78571 | 78577 | 78583 | 78593 | 78607 | 78623 | 78643 | 78649 | 78653 | 78691 | 78697 |
| 78707 | 78713 | 78721 | 78737 | 78779 | 78781 | 78787 | 78791 | 78797 | 78803 | 78809 | 78823 | 78839 | 78853 | 78857 | 78877 | 78887 | 78889 | 78893 | 78901 |
| 78919 | 78929 | 78941 | 78977 | 78979 | 78989 | 79031 | 79039 | 79043 | 79063 | 79087 | 79103 | 79111 | 79133 | 79139 | 79147 | 79151 | 79153 | 79159 | 79181 |
| 79187 | 79193 | 79201 | 79229 | 79231 | 79241 | 79259 | 79273 | 79279 | 79283 | 79301 | 79309 | 79319 | 79333 | 79337 | 79349 | 79357 | 79367 | 79379 | 79393 |
| 79397 | 79399 | 79411 | 79423 | 79427 | 79433 | 79451 | 79481 | 79493 | 79531 | 79537 | 79549 | 79559 | 79561 | 79579 | 79589 | 79601 | 79609 | 79613 | 79621 |
| 79627 | 79631 | 79633 | 79657 | 79669 | 79687 | 79691 | 79693 | 79697 | 79699 | 79757 | 79769 | 79777 | 79801 | 79811 | 79813 | 79817 | 79823 | 79829 | 79841 |
| 79843 | 79847 | 79861 | 79867 | 79873 | 79889 | 79901 | 79903 | 79907 | 79939 | 79943 | 79967 | 79973 | 79979 | 79987 | 79997 | 79999 | 80021 | 80039 | 80051 |
| 80071 | 80077 | 80107 | 80111 | 80141 | 80147 | 80149 | 80153 | 80167 | 80173 | 80177 | 80191 | 80207 | 80209 | 80221 | 80231 | 80233 | 80239 | 80251 | 80263 |
| 80273 | 80279 | 80287 | 80309 | 80317 | 80329 | 80341 | 80347 | 80363 | 80369 | 80387 | 80407 | 80429 | 80447 | 80449 | 80471 | 80473 | 80489 | 80491 | 80513 |
| 80527 | 80537 | 80557 | 80567 | 80599 | 80603 | 80611 | 80621 | 80627 | 80629 | 80651 | 80657 | 80669 | 80671 | 80677 | 80681 | 80683 | 80687 | 80701 | 80713 |
| 80737 | 80747 | 80749 | 80761 | 80777 | 80779 | 80783 | 80789 | 80803 | 80809 | 80819 | 80831 | 80833 | 80849 | 80863 | 80897 | 80909 | 80911 | 80917 | 80923 |
| 80929 | 80933 | 80953 | 80963 | 80989 | 81001 | 81013 | 81017 | 81019 | 81023 | 81031 | 81041 | 81043 | 81047 | 81049 | 81071 | 81077 | 81083 | 81097 | 81101 |
| 81119 | 81131 | 81157 | 81163 | 81173 | 81181 | 81197 | 81199 | 81203 | 81223 | 81233 | 81239 | 81281 | 81283 | 81293 | 81299 | 81307 | 81331 | 81343 | 81349 |
| 81353 | 81359 | 81371 | 81373 | 81401 | 81409 | 81421 | 81439 | 81457 | 81463 | 81509 | 81517 | 81527 | 81533 | 81547 | 81551 | 81553 | 81559 | 81563 | 81569 |
| 81611 | 81619 | 81629 | 81637 | 81647 | 81649 | 81667 | 81671 | 81677 | 81689 | 81701 | 81703 | 81707 | 81727 | 81737 | 81749 | 81761 | 81769 | 81773 | 81799 |
| 81817 | 81839 | 81847 | 81853 | 81869 | 81883 | 81899 | 81901 | 81919 | 81929 | 81931 | 81937 | 81943 | 81953 | 81967 | 81971 | 81973 | 82003 | 82007 | 82009 |
| 82013 | 82021 | 82031 | 82037 | 82039 | 82051 | 82067 | 82073 | 82129 | 82139 | 82141 | 82153 | 82163 | 82171 | 82183 | 82189 | 82193 | 82207 | 82217 | 82219 |
| 82223 | 82231 | 82237 | 82241 | 82261 | 82267 | 82279 | 82301 | 82307 | 82339 | 82349 | 82351 | 82361 | 82373 | 82387 | 82393 | 82421 | 82457 | 82463 | 82469 |
| 82471 | 82483 | 82487 | 82493 | 82499 | 82507 | 82529 | 82531 | 82549 | 82559 | 82561 | 82567 | 82571 | 82591 | 82601 | 82609 | 82613 | 82619 | 82633 | 82651 |
| 82657 | 82699 | 82721 | 82723 | 82727 | 82729 | 82757 | 82759 | 82763 | 82781 | 82787 | 82793 | 82799 | 82811 | 82813 | 82837 | 82847 | 82883 | 82889 | 82891 |
| 82903 | 82913 | 82939 | 82963 | 82981 | 82997 | 83003 | 83009 | 83023 | 83047 | 83059 | 83063 | 83071 | 83077 | 83089 | 83093 | 83101 | 83117 | 83137 | 83177 |
| 83203 | 83207 | 83219 | 83221 | 83227 | 83231 | 83233 | 83243 | 83257 | 83267 | 83269 | 83273 | 83299 | 83311 | 83339 | 83341 | 83357 | 83383 | 83389 | 83399 |
| 83401 | 83407 | 83417 | 83423 | 83431 | 83437 | 83443 | 83449 | 83459 | 83471 | 83477 | 83497 | 83537 | 83557 | 83561 | 83563 | 83579 | 83591 | 83597 | 83609 |
| 83617 | 83621 | 83639 | 83641 | 83653 | 83663 | 83689 | 83701 | 83717 | 83719 | 83737 | 83761 | 83773 | 83777 | 83791 | 83813 | 83833 | 83843 | 83857 | 83869 |
| 83873 | 83891 | 83903 | 83911 | 83921 | 83933 | 83939 | 83969 | 83983 | 83987 | 84011 | 84017 | 84047 | 84053 | 84059 | 84061 | 84067 | 84089 | 84121 | 84127 |
| 84131 | 84137 | 84143 | 84163 | 84179 | 84181 | 84191 | 84199 | 84211 | 84221 | 84223 | 84229 | 84239 | 84247 | 84263 | 84299 | 84307 | 84313 | 84317 | 84319 |
| 84347 | 84349 | 84377 | 84389 | 84391 | 84401 | 84407 | 84421 | 84431 | 84437 | 84443 | 84449 | 84457 | 84463 | 84467 | 84481 | 84499 | 84503 | 84509 | 84521 |
| 84523 | 84533 | 84551 | 84559 | 84589 | 84629 | 84631 | 84649 | 84653 | 84659 | 84673 | 84691 | 84697 | 84701 | 84713 | 84719 | 84731 | 84737 | 84751 | 84761 |
| 84787 | 84793 | 84809 | 84811 | 84827 | 84857 | 84859 | 84869 | 84871 | 84913 | 84919 | 84947 | 84961 | 84967 | 84977 | 84979 | 84991 | 85009 | 85021 | 85027 |
| 85037 | 85049 | 85061 | 85081 | 85087 | 85091 | 85093 | 85103 | 85109 | 85121 | 85133 | 85147 | 85159 | 85193 | 85199 | 85201 | 85213 | 85223 | 85229 | 85237 |
| 85243 | 85247 | 85259 | 85297 | 85303 | 85313 | 85331 | 85333 | 85361 | 85363 | 85369 | 85381 | 85411 | 85427 | 85429 | 85439 | 85447 | 85451 | 85453 | 85469 |
| 85487 | 85513 | 85517 | 85523 | 85531 | 85549 | 85571 | 85577 | 85597 | 85601 | 85607 | 85619 | 85621 | 85627 | 85639 | 85643 | 85661 | 85667 | 85669 | 85691 |
| 85703 | 85711 | 85717 | 85733 | 85751 | 85781 | 85793 | 85817 | 85819 | 85829 | 85831 | 85837 | 85843 | 85847 | 85853 | 85889 | 85903 | 85909 | 85931 | 85933 |
| 85991 | 85999 | 86011 | 86017 | 86027 | 86029 | 86069 | 86077 | 86083 | 86111 | 86113 | 86117 | 86131 | 86137 | 86143 | 86161 | 86171 | 86179 | 86183 | 86197 |
| 86201 | 86209 | 86239 | 86243 | 86249 | 86257 | 86263 | 86269 | 86287 | 86291 | 86293 | 86297 | 86311 | 86323 | 86341 | 86351 | 86353 | 86357 | 86369 | 86371 |
| 86381 | 86389 | 86399 | 86413 | 86423 | 86441 | 86453 | 86461 | 86467 | 86477 | 86491 | 86501 | 86509 | 86531 | 86533 | 86539 | 86561 | 86573 | 86579 | 86587 |
| 86599 | 86627 | 86629 | 86677 | 86689 | 86693 | 86711 | 86719 | 86729 | 86743 | 86753 | 86767 | 86771 | 86783 | 86813 | 86837 | 86843 | 86851 | 86857 | 86861 |
| 86869 | 86923 | 86927 | 86929 | 86939 | 86951 | 86959 | 86969 | 86981 | 86993 | 87011 | 87013 | 87037 | 87041 | 87049 | 87071 | 87083 | 87103 | 87107 | 87119 |
| 87121 | 87133 | 87149 | 87151 | 87179 | 87181 | 87187 | 87211 | 87221 | 87223 | 87251 | 87253 | 87257 | 87277 | 87281 | 87293 | 87299 | 87313 | 87317 | 87323 |
| 87337 | 87359 | 87383 | 87403 | 87407 | 87421 | 87427 | 87433 | 87443 | 87473 | 87481 | 87491 | 87509 | 87511 | 87517 | 87523 | 87539 | 87541 | 87547 | 87553 |
| 87557 | 87559 | 87583 | 87587 | 87589 | 87613 | 87623 | 87629 | 87631 | 87641 | 87643 | 87649 | 87671 | 87679 | 87683 | 87691 | 87697 | 87701 | 87719 | 87721 |
| 87739 | 87743 | 87751 | 87767 | 87793 | 87797 | 87803 | 87811 | 87833 | 87853 | 87869 | 87877 | 87881 | 87887 | 87911 | 87917 | 87931 | 87943 | 87959 | 87961 |
| 87973 | 87977 | 87991 | 88001 | 88003 | 88007 | 88019 | 88037 | 88069 | 88079 | 88093 | 88117 | 88129 | 88169 | 88177 | 88211 | 88223 | 88237 | 88241 | 88259 |
| 88261 | 88289 | 88301 | 88321 | 88327 | 88337 | 88339 | 88379 | 88397 | 88411 | 88423 | 88427 | 88463 | 88469 | 88471 | 88493 | 88499 | 88513 | 88523 | 88547 |
| 88589 | 88591 | 88607 | 88609 | 88643 | 88651 | 88657 | 88661 | 88663 | 88667 | 88681 | 88721 | 88729 | 88741 | 88747 | 88771 | 88789 | 88793 | 88799 | 88801 |
| 88807 | 88811 | 88813 | 88817 | 88819 | 88843 | 88853 | 88861 | 88867 | 88873 | 88883 | 88897 | 88903 | 88919 | 88937 | 88951 | 88969 | 88993 | 88997 | 89003 |
| 89009 | 89017 | 89021 | 89041 | 89051 | 89057 | 89069 | 89071 | 89083 | 89087 | 89101 | 89107 | 89113 | 89119 | 89123 | 89137 | 89153 | 89189 | 89203 | 89209 |
| 89213 | 89227 | 89231 | 89237 | 89261 | 89269 | 89273 | 89293 | 89303 | 89317 | 89329 | 89363 | 89371 | 89381 | 89387 | 89393 | 89399 | 89413 | 89417 | 89431 |
| 89443 | 89449 | 89459 | 89477 | 89491 | 89501 | 89513 | 89519 | 89521 | 89527 | 89533 | 89561 | 89563 | 89567 | 89591 | 89597 | 89599 | 89603 | 89611 | 89627 |
| 89633 | 89653 | 89657 | 89659 | 89669 | 89671 | 89681 | 89689 | 89753 | 89759 | 89767 | 89779 | 89783 | 89797 | 89809 | 89819 | 89821 | 89833 | 89839 | 89849 |
| 89867 | 89891 | 89897 | 89899 | 89909 | 89917 | 89923 | 89939 | 89959 | 89963 | 89977 | 89983 | 89989 | 90001 | 90007 | 90011 | 90017 | 90019 | 90023 | 90031 |
| 90053 | 90059 | 90067 | 90071 | 90073 | 90089 | 90107 | 90121 | 90127 | 90149 | 90163 | 90173 | 90187 | 90191 | 90197 | 90199 | 90203 | 90217 | 90227 | 90239 |
| 90247 | 90263 | 90271 | 90281 | 90289 | 90313 | 90353 | 90359 | 90371 | 90373 | 90379 | 90397 | 90401 | 90403 | 90407 | 90437 | 90439 | 90469 | 90473 | 90481 |
| 90499 | 90511 | 90523 | 90527 | 90529 | 90533 | 90547 | 90583 | 90599 | 90617 | 90619 | 90631 | 90641 | 90647 | 90659 | 90677 | 90679 | 90697 | 90703 | 90709 |
| 90731 | 90749 | 90787 | 90793 | 90803 | 90821 | 90823 | 90833 | 90841 | 90847 | 90863 | 90887 | 90901 | 90907 | 90911 | 90917 | 90931 | 90947 | 90971 | 90977 |
| 90989 | 90997 | 91009 | 91019 | 91033 | 91079 | 91081 | 91097 | 91099 | 91121 | 91127 | 91129 | 91139 | 91141 | 91151 | 91153 | 91159 | 91163 | 91183 | 91193 |
| 91199 | 91229 | 91237 | 91243 | 91249 | 91253 | 91283 | 91291 | 91297 | 91303 | 91309 | 91331 | 91367 | 91369 | 91373 | 91381 | 91387 | 91393 | 91397 | 91411 |
| 91423 | 91433 | 91453 | 91457 | 91459 | 91463 | 91493 | 91499 | 91513 | 91529 | 91541 | 91571 | 91573 | 91577 | 91583 | 91591 | 91621 | 91631 | 91639 | 91673 |
| 91691 | 91703 | 91711 | 91733 | 91753 | 91757 | 91771 | 91781 | 91801 | 91807 | 91811 | 91813 | 91823 | 91837 | 91841 | 91867 | 91873 | 91909 | 91921 | 91939 |
| 91943 | 91951 | 91957 | 91961 | 91967 | 91969 | 91997 | 92003 | 92009 | 92033 | 92041 | 92051 | 92077 | 92083 | 92107 | 92111 | 92119 | 92143 | 92153 | 92173 |
| 92177 | 92179 | 92189 | 92203 | 92219 | 92221 | 92227 | 92233 | 92237 | 92243 | 92251 | 92269 | 92297 | 92311 | 92317 | 92333 | 92347 | 92353 | 92357 | 92363 |
| 92369 | 92377 | 92381 | 92383 | 92387 | 92399 | 92401 | 92413 | 92419 | 92431 | 92459 | 92461 | 92467 | 92479 | 92489 | 92503 | 92507 | 92551 | 92557 | 92567 |
| 92569 | 92581 | 92593 | 92623 | 92627 | 92639 | 92641 | 92647 | 92657 | 92669 | 92671 | 92681 | 92683 | 92693 | 92699 | 92707 | 92717 | 92723 | 92737 | 92753 |
| 92761 | 92767 | 92779 | 92789 | 92791 | 92801 | 92809 | 92821 | 92831 | 92849 | 92857 | 92861 | 92863 | 92867 | 92893 | 92899 | 92921 | 92927 | 92941 | 92951 |
| 92957 | 92959 | 92987 | 92993 | 93001 | 93047 | 93053 | 93059 | 93077 | 93083 | 93089 | 93097 | 93103 | 93113 | 93131 | 93133 | 93139 | 93151 | 93169 | 93179 |
| 93187 | 93199 | 93229 | 93239 | 93241 | 93251 | 93253 | 93257 | 93263 | 93281 | 93283 | 93287 | 93307 | 93319 | 93323 | 93329 | 93337 | 93371 | 93377 | 93383 |
| 93407 | 93419 | 93427 | 93463 | 93479 | 93481 | 93487 | 93491 | 93493 | 93497 | 93503 | 93523 | 93529 | 93553 | 93557 | 93559 | 93563 | 93581 | 93601 | 93607 |
| 93629 | 93637 | 93683 | 93701 | 93703 | 93719 | 93739 | 93761 | 93763 | 93787 | 93809 | 93811 | 93827 | 93851 | 93871 | 93887 | 93889 | 93893 | 93901 | 93911 |
| 93913 | 93923 | 93937 | 93941 | 93949 | 93967 | 93971 | 93979 | 93983 | 93997 | 94007 | 94009 | 94033 | 94049 | 94057 | 94063 | 94079 | 94099 | 94109 | 94111 |
| 94117 | 94121 | 94151 | 94153 | 94169 | 94201 | 94207 | 94219 | 94229 | 94253 | 94261 | 94273 | 94291 | 94307 | 94309 | 94321 | 94327 | 94331 | 94343 | 94349 |
| 94351 | 94379 | 94397 | 94399 | 94421 | 94427 | 94433 | 94439 | 94441 | 94447 | 94463 | 94477 | 94483 | 94513 | 94529 | 94531 | 94541 | 94543 | 94547 | 94559 |
| 94561 | 94573 | 94583 | 94597 | 94603 | 94613 | 94621 | 94649 | 94651 | 94687 | 94693 | 94709 | 94723 | 94727 | 94747 | 94771 | 94777 | 94781 | 94789 | 94793 |
| 94811 | 94819 | 94823 | 94837 | 94841 | 94847 | 94849 | 94873 | 94889 | 94903 | 94907 | 94933 | 94949 | 94951 | 94961 | 94993 | 94999 | 95003 | 95009 | 95021 |
| 95027 | 95063 | 95071 | 95083 | 95087 | 95089 | 95093 | 95101 | 95107 | 95111 | 95131 | 95143 | 95153 | 95177 | 95189 | 95191 | 95203 | 95213 | 95219 | 95231 |
| 95233 | 95239 | 95257 | 95261 | 95267 | 95273 | 95279 | 95287 | 95311 | 95317 | 95327 | 95339 | 95369 | 95383 | 95393 | 95401 | 95413 | 95419 | 95429 | 95441 |
| 95443 | 95461 | 95467 | 95471 | 95479 | 95483 | 95507 | 95527 | 95531 | 95539 | 95549 | 95561 | 95569 | 95581 | 95597 | 95603 | 95617 | 95621 | 95629 | 95633 |
| 95651 | 95701 | 95707 | 95713 | 95717 | 95723 | 95731 | 95737 | 95747 | 95773 | 95783 | 95789 | 95791 | 95801 | 95803 | 95813 | 95819 | 95857 | 95869 | 95873 |
| 95881 | 95891 | 95911 | 95917 | 95923 | 95929 | 95947 | 95957 | 95959 | 95971 | 95987 | 95989 | 96001 | 96013 | 96017 | 96043 | 96053 | 96059 | 96079 | 96097 |
| 96137 | 96149 | 96157 | 96167 | 96179 | 96181 | 96199 | 96211 | 96221 | 96223 | 96233 | 96259 | 96263 | 96269 | 96281 | 96289 | 96293 | 96323 | 96329 | 96331 |
| 96337 | 96353 | 96377 | 96401 | 96419 | 96431 | 96443 | 96451 | 96457 | 96461 | 96469 | 96479 | 96487 | 96493 | 96497 | 96517 | 96527 | 96553 | 96557 | 96581 |
| 96587 | 96589 | 96601 | 96643 | 96661 | 96667 | 96671 | 96697 | 96703 | 96731 | 96737 | 96739 | 96749 | 96757 | 96763 | 96769 | 96779 | 96787 | 96797 | 96799 |
| 96821 | 96823 | 96827 | 96847 | 96851 | 96857 | 96893 | 96907 | 96911 | 96931 | 96953 | 96959 | 96973 | 96979 | 96989 | 96997 | 97001 | 97003 | 97007 | 97021 |
| 97039 | 97073 | 97081 | 97103 | 97117 | 97127 | 97151 | 97157 | 97159 | 97169 | 97171 | 97177 | 97187 | 97213 | 97231 | 97241 | 97259 | 97283 | 97301 | 97303 |
| 97327 | 97367 | 97369 | 97373 | 97379 | 97381 | 97387 | 97397 | 97423 | 97429 | 97441 | 97453 | 97459 | 97463 | 97499 | 97501 | 97511 | 97523 | 97547 | 97549 |
| 97553 | 97561 | 97571 | 97577 | 97579 | 97583 | 97607 | 97609 | 97613 | 97649 | 97651 | 97673 | 97687 | 97711 | 97729 | 97771 | 97777 | 97787 | 97789 | 97813 |
| 97829 | 97841 | 97843 | 97847 | 97849 | 97859 | 97861 | 97871 | 97879 | 97883 | 97919 | 97927 | 97931 | 97943 | 97961 | 97967 | 97973 | 97987 | 98009 | 98011 |
| 98017 | 98041 | 98047 | 98057 | 98081 | 98101 | 98123 | 98129 | 98143 | 98179 | 98207 | 98213 | 98221 | 98227 | 98251 | 98257 | 98269 | 98297 | 98299 | 98317 |
| 98321 | 98323 | 98327 | 98347 | 98369 | 98377 | 98387 | 98389 | 98407 | 98411 | 98419 | 98429 | 98443 | 98453 | 98459 | 98467 | 98473 | 98479 | 98491 | 98507 |
| 98519 | 98533 | 98543 | 98561 | 98563 | 98573 | 98597 | 98621 | 98627 | 98639 | 98641 | 98663 | 98669 | 98689 | 98711 | 98713 | 98717 | 98729 | 98731 | 98737 |
| 98773 | 98779 | 98801 | 98807 | 98809 | 98837 | 98849 | 98867 | 98869 | 98873 | 98887 | 98893 | 98897 | 98899 | 98909 | 98911 | 98927 | 98929 | 98939 | 98947 |
| 98953 | 98963 | 98981 | 98993 | 98999 | 99013 | 99017 | 99023 | 99041 | 99053 | 99079 | 99083 | 99089 | 99103 | 99109 | 99119 | 99131 | 99133 | 99137 | 99139 |
| 99149 | 99173 | 99181 | 99191 | 99223 | 99233 | 99241 | 99251 | 99257 | 99259 | 99277 | 99289 | 99317 | 99347 | 99349 | 99367 | 99371 | 99377 | 99391 | 99397 |
| 99401 | 99409 | 99431 | 99439 | 99469 | 99487 | 99497 | 99523 | 99527 | 99529 | 99551 | 99559 | 99563 | 99571 | 99577 | 99581 | 99607 | 99611 | 99623 | 99643 |
| 99661 | 99667 | 99679 | 99689 | 99707 | 99709 | 99713 | 99719 | 99721 | 99733 | 99761 | 99767 | 99787 | 99793 | 99809 | 99817 | 99823 | 99829 | 99833 | 99839 |
| 99859 | 99871 | 99877 | 99881 | 99901 | 99907 | 99923 | 99929 | 99961 | 99971 | 99989 | 99991 | 100003 | 100019 | 100043 | 100049 | 100057 | 100069 | 100103 | 100109 |
| 100129 | 100151 | 100153 | 100169 | 100183 | 100189 | 100193 | 100207 | 100213 | 100237 | 100267 | 100271 | 100279 | 100291 | 100297 | 100313 | 100333 | 100343 | 100357 | 100361 |
| 100363 | 100379 | 100391 | 100393 | 100403 | 100411 | 100417 | 100447 | 100459 | 100469 | 100483 | 100493 | 100501 | 100511 | 100517 | 100519 | 100523 | 100537 | 100547 | 100549 |
| 100559 | 100591 | 100609 | 100613 | 100621 | 100649 | 100669 | 100673 | 100693 | 100699 | 100703 | 100733 | 100741 | 100747 | 100769 | 100787 | 100799 | 100801 | 100811 | 100823 |
| 100829 | 100847 | 100853 | 100907 | 100913 | 100927 | 100931 | 100937 | 100943 | 100957 | 100981 | 100987 | 100999 | 101009 | 101021 | 101027 | 101051 | 101063 | 101081 | 101089 |
| 101107 | 101111 | 101113 | 101117 | 101119 | 101141 | 101149 | 101159 | 101161 | 101173 | 101183 | 101197 | 101203 | 101207 | 101209 | 101221 | 101267 | 101273 | 101279 | 101281 |
| 101287 | 101293 | 101323 | 101333 | 101341 | 101347 | 101359 | 101363 | 101377 | 101383 | 101399 | 101411 | 101419 | 101429 | 101449 | 101467 | 101477 | 101483 | 101489 | 101501 |
| 101503 | 101513 | 101527 | 101531 | 101533 | 101537 | 101561 | 101573 | 101581 | 101599 | 101603 | 101611 | 101627 | 101641 | 101653 | 101663 | 101681 | 101693 | 101701 | 101719 |
| 101723 | 101737 | 101741 | 101747 | 101749 | 101771 | 101789 | 101797 | 101807 | 101833 | 101837 | 101839 | 101863 | 101869 | 101873 | 101879 | 101891 | 101917 | 101921 | 101929 |
| 101939 | 101957 | 101963 | 101977 | 101987 | 101999 | 102001 | 102013 | 102019 | 102023 | 102031 | 102043 | 102059 | 102061 | 102071 | 102077 | 102079 | 102101 | 102103 | 102107 |
| 102121 | 102139 | 102149 | 102161 | 102181 | 102191 | 102197 | 102199 | 102203 | 102217 | 102229 | 102233 | 102241 | 102251 | 102253 | 102259 | 102293 | 102299 | 102301 | 102317 |
| 102329 | 102337 | 102359 | 102367 | 102397 | 102407 | 102409 | 102433 | 102437 | 102451 | 102461 | 102481 | 102497 | 102499 | 102503 | 102523 | 102533 | 102539 | 102547 | 102551 |
| 102559 | 102563 | 102587 | 102593 | 102607 | 102611 | 102643 | 102647 | 102653 | 102667 | 102673 | 102677 | 102679 | 102701 | 102761 | 102763 | 102769 | 102793 | 102797 | 102811 |
| 102829 | 102841 | 102859 | 102871 | 102877 | 102881 | 102911 | 102913 | 102929 | 102931 | 102953 | 102967 | 102983 | 103001 | 103007 | 103043 | 103049 | 103067 | 103069 | 103079 |
| 103087 | 103091 | 103093 | 103099 | 103123 | 103141 | 103171 | 103177 | 103183 | 103217 | 103231 | 103237 | 103289 | 103291 | 103307 | 103319 | 103333 | 103349 | 103357 | 103387 |
| 103391 | 103393 | 103399 | 103409 | 103421 | 103423 | 103451 | 103457 | 103471 | 103483 | 103511 | 103529 | 103549 | 103553 | 103561 | 103567 | 103573 | 103577 | 103583 | 103591 |
| 103613 | 103619 | 103643 | 103651 | 103657 | 103669 | 103681 | 103687 | 103699 | 103703 | 103723 | 103769 | 103787 | 103801 | 103811 | 103813 | 103837 | 103841 | 103843 | 103867 |
| 103889 | 103903 | 103913 | 103919 | 103951 | 103963 | 103967 | 103969 | 103979 | 103981 | 103991 | 103993 | 103997 | 104003 | 104009 | 104021 | 104033 | 104047 | 104053 | 104059 |
| 104087 | 104089 | 104107 | 104113 | 104119 | 104123 | 104147 | 104149 | 104161 | 104173 | 104179 | 104183 | 104207 | 104231 | 104233 | 104239 | 104243 | 104281 | 104287 | 104297 |
| 104309 | 104311 | 104323 | 104327 | 104347 | 104369 | 104381 | 104383 | 104393 | 104399 | 104417 | 104459 | 104471 | 104473 | 104479 | 104491 | 104513 | 104527 | 104537 | 104543 |
| 104549 | 104551 | 104561 | 104579 | 104593 | 104597 | 104623 | 104639 | 104651 | 104659 | 104677 | 104681 | 104683 | 104693 | 104701 | 104707 | 104711 | 104717 | 104723 | 104729 |

## Código fonte da macro utilizada

Para obter uma réplica da tabela acima, basta fazer o seguinte:
* Criar um novo documento no OpenOffice.org Writer;
* Copiar o código abaixo para uma nova macro do OpenOffice.org Basic.
* Executar a macro escolhendo (quando for perguntado) 500 linhas, 20 colunas e maior número primo igual a 123456.

### Notas

* A execução pode levar alguns minutos (não mais do que 10, para 10.000 primos), pois não foi feito qualquer esforço para otimizar o código.
* No caso de querer converter a tabela resultante para a sintaxe do MediaWiki, pode ser utilizado uma ferramenta para conversão automática. Na Wikipédia inglesa há uma lista de opções disponível na página Wikipedia:Tools.

## Ver também

* List of prime numbers - diversas listas de números primos, na Wikipédia inglesa.