# Teorema fundamental da aritmética

O Teorema Fundamental da Aritmética sustenta que todos os números inteiros positivos maiores que 1 podem ser decompostos num produto de números primos, sendo esta decomposição única a menos de permutações dos fatores.
As proposições do Livro XII de Os Elementos de Euclides praticamente demonstraram este teorema que também foi exposto no Livro IX. O teorema só foi demonstrado e proposto por Carl Friedrich Gauss em 1796.

## Livro VII de Os Elementos de Euclides

O Livro VII, com 39 proposições, é totalmente aritmético e estuda as propriedades dos números naturais e suas relações. Ele apresenta três proposições que motivaram o Teorema Fundamental da Aritmética:

### Proposição VII-30:

"Caso dois números, sendo multiplicados entre si, façam algum, e algum número primo meça o produzido deles, medirá também um dos do princípio."

#### Demonstração de "Os Elementos"

"Façam, pois, dos dois números A, B, sendo multiplicados entre si, o C, e algum número primo, o D, meça o C; diga que o D mede um dos A, B. Não meça, pois, o A; e o D é primo, portanto, os A, D são primos entre si. E tantas vezes o D mede o C, quantas unidades no E, portanto o D, tendo multiplicado o E, fez o C. Mas, certamente, também o A, tendo multiplicado o B, fez o C; portanto, os dois D, E é igual aos dois A, B. Portanto, como D está para A, assim o B para o E. E os D, A são primos, e os primos são também os menores, e os menores medem os que têm as a mesma razão, o mesmo número de vezes, tanto o maior, o maior quanto o menos, o menos, isto é, tanto o antecedente, o antecedente quanto o consequente, o consequente; portanto, o D mede o B. Do mesmo modo, então, provaremos que também, caso não meça o B, medirá o A. Portanto, o D mede um dos A, B; o que era preciso prova."

### Proposição VII-31

"Todo número composto é medido por algum número primo."

#### Demonstração de "Os Elementos"

"Seja o número composto A; digo que o A é medido por algum número primo. Pois, como o A é composto, algum número o medirá. Meça, e seja o B. E se, por um lado, o B é primo, o prescrito aconteceria. Se, por outro lado, é composto, algum número o medirá. Meça, e seja o C. E como o C mede o B, e o B mede o A, portanto também o C mede o A. E se, por um lado, o C é primo, o prescrito aconteceria. Se, por outro lado é composto, outro número o medirá. Sendo então produzida uma investigação como essa, algum número primo será tomado, que medirá. Pois, se não for tomado, ilimitados números medirão o A, cada um dos quais é menor do que o outro; o que é impossível nos números. Portanto, algum número primo será tomado, que medirá o antes dele mesmo, que também medirá o A. Portanto, todo número composto é medido por algum número primo o que era preciso prova."

### Proposição VII-32

"Todo número ou é primo ou é medido por algum primo."

#### Demonstração de "Os Elementos"

"Seja o número A; digo que o A ou é primo ou é medido por algum número primo. Se, por um lado, o A é primo, o prescrito aconteceria. Se, por outro lado, é composto, algum número primo o medirá. Portanto, todo número ou é primo ou é medido por algum número primo; o que era preciso prova."

## Demonstração do Teorema Fundamental da Aritmética
### Teorema

Seja $a>1$ um inteiro positivo. Então, existem primos positivos ${p_{1}}\leq {p_{2}}\leq {...}\leq {p_{t}}$ tais que $a=p_{1}p_{2}...p_{t},$ e essa decomposição é única.
Demonstração:
Existência de uma decomposição
Será usado para esta demonstração o Princípio de indução completa.
Para $a=2$ existe uma decomposição trivial em números primos, já que 2 é, ele próprio, um número primo. Suponhamos agora que existe uma decomposição para todo inteiro ${b},\ {2}\leq {b}<a.$ Mostraremos que também vale para $a.$
Se $a$ é primo, admite a decomposição trivial. Caso contrário, $a$ admite um divisor positivo $b$ tal que $1<b<a.$ Isto é, $a=bc,$ e temos também $1<c<a.$ Pela hipótese de indução, $b$ e $c$ podem ser escritos como produtos de primos, na forma $b=p_{1}...p_{s},$ $c=q_{1}...q_{k}.$
Substituindo, temos $a=p_{1}...p_{s}q_{1}...q_{k},$ e o resultado também vale para $a.$
Unicidade da decomposição
Dado um inteiro $a,$ ele poderia admitir, em princípio, mais de uma decomposição em produto de fatores primos. Será chamado comprimento de uma decomposição ao número de fatores que nela comparecem.
A demonstração será feita por indução no comprimento de uma decomposição de $a.$
Suponhamos que $a$ admita uma decomposição do tipo $a=p_{1},$ onde $p_{1}$ é primo, e que vale
$a=p_{1}=q_{1}q_{2}...q_{s},$
em que ${q_{1}}\leq {q_{2}}\leq {...}\leq {q_{s}}$ são primos positivos. Como $q_{1}$ divide $q_{1}q_{2}...q_{s},$ $q_{1}$ também divide $p_{1},$ que é primo. Então, devemos ter $p_{1}=q_{1}.$ Cancelando, vem $1=q_{2}...q_{s}.$ Se $s>1,$ teríamos que o primo $q_{2}$ seria invertível, uma contradição. Assim, $s=1$ e, como já provamos que $p_{1}=q_{1},$ o primeiro passo de indução está verificado.
Suponhamos agora o resultado verdadeiro para todo inteiro que admita uma decomposição de comprimento ${k}\geq {1},$ e seja $a$ um inteiro com uma decomposição de comprimento $k+1.$ Se $a$ admitisse outra decomposição, temos
$a=p_{1}...p_{k+1}=q_{1}...q_{s},$
em que ${q_{1}}\leq {q_{2}}\leq {...}\leq {q_{s}}$ são primos positivos.
Como na primeira parte, $q_{1}$ divide $p_{1}...p_{k+1}$ e temos que $q_{1}$ divide $p_{i},$ para algum $i$ (Lema de Euclides). Como $p_{i}$ é primo, devemos ter novamente que $q_{1}=p_{i}.$ Em particular, ${q_{1}}\geq {p_{1}}.$
De forma análoga, pode-se obter que $p_{1}=q_{j},$ para algum j. Logo, ${p_{1}}\geq {q_{1}}.$ De ambas as desigualdades, vem que $p_{1}=q_{1}.$ Finalmente, cancelando em $a=p_{1}...p_{k+1}=q_{1}...q_{s},$ temos que
$p_{2}...p_{k+1}=q_{2}...q_{s}.$
Agora, o primeiro membro da igualdade tem uma decomposição de comprimento $k,$ logo, da hipótese de indução, admite uma única decomposição. Assim, temos $k=s-1,$ donde $k+1=s$ e $p_{i}=q_{i},$ para $i=2,...,k+1.$ Como já provamos que $p_{1}=q_{1},$ ambas as expressões de $a$ coincidem.
Agrupando os primos eventualmente repetidos na decomposição de $a,$ podemos enunciar o teorema anterior de forma levemente diferente. Também podemos estendê-lo a números negativos.

### Teorema Fundamental da Aritmética

Seja $a$ um inteiro diferente de 0, 1 e -1. Então, existem primos positivos $p_{1}<p_{2}<...<p_{r}$ e inteiros positivos $n_{1},n_{2},...,n_{r}$ tais que $a=\pm p_{1}^{n_{1}}...p_{r}^{n_{r}}.$ Além disso, essa decomposição é única.
Demonstração:
Temos que $a=\pm |a|,$ conforme $a$ seja positivo ou negativo. Como $|a|$ é positivo, do teorema anterior, temos que existem primos ${p_{1}}\leq {p_{2}}\leq {...}\leq {p_{t}}$ tais que
$a=\pm p_{1}p_{2}...p_{t}.$
Agrupando os primos eventualmente repetidos, podemos escrever
$a=\pm p_{1}^{n_{1}}...p_{r}^{n_{r}}.$
A unicidade segue diretamente do teorema anterior.
Está, portanto, demonstrado o Teorema Fundamental da Aritmética.