A primeira pessoa que provou o teorema foi Euclides. A primeira prova detalhada e correta foi na Disquisitiones Arithmeticae de Carl Friedrich Gauß.
Algumas pessoas podem pensar que o teorema é verdadeiro em todos os lugares. No entanto, o teorema não é verdadeiro em sistemas de números mais gerais, como os inteiros algébricos. Isto foi mencionado pela primeira vez por Ernst Kummer em 1843, em seu trabalho sobre o último teorema de Fermat. Para mais informações sobre isso: leia a teoria dos números algébricos.
A prova consiste em duas partes: primeiro mostramos que cada número pode ser escrito como um produto de primes; segundo mostramos que se escrevermos um número como um produto de primes pela segunda vez, então as duas listas de números primos devem ser as mesmas.
Primeira parte da prova
Mostramos que se nem todos os números maiores que 1 podem ser escritos como produto de primes, acabamos em algum tipo de impossibilidade. Portanto, depois disso, concluímos que deve ser verdade que cada número pode ser escrito como um produto de primes.
Então, agora veja o que acontece quando alguém diz que conhece um inteiro positivo, maior que 1, que não pode ser escrito como um produto de primes. Nesse caso, pedimos a ele que mencione todos os números, maiores que 1, que não podem ser escritos como produto de primes. Um destes números deve ser o menor: vamos chamá-lo de n. É claro que este número n não pode ser 1. Além disso, não pode ser um número primo, porque um número primo é um "produto" de um único primo: ele mesmo. Portanto, ele deve ser um produto de números. Assim -
n = ab
onde tanto a como b são inteiros positivos que são naturalmente menores que n. Mas: n foi o menor número que não pode ser escrito como um produto de primes. Portanto, deve ser possível escrever a e b como produtos de primes, pois ambos são menores do que n. Mas então o produto
n = ab
também pode ser escrito como um produto de primes. Isto é uma impossibilidade porque dissemos que n não pode ser escrito como um produto de primes.
Mostramos agora a impossibilidade que existe se a primeira parte do teorema não fosse verdadeira. Desta forma, provamos agora a primeira parte do teorema.
Segunda parte da prova
Agora temos que provar que só há uma maneira de escrever um número positivo maior que 1 como um produto de números primos.
Para isso, usamos o seguinte lema: se um número primo p divide um produto ab, então ele divide a ou divide b (lema de Euclid). Primeiro provamos agora este lema. Bem, assumamos agora que p não divide a. Então p e a são coprime e nós temos a identidade de Bezout que diz que deve haver inteiros x e y tais que
px + ay = 1.
Multiplicando tudo com b dá
pbx + aby = b,
Lembre-se que ab poderia ser dividido por p. Assim, agora, no lado esquerdo temos dois termos que são divisíveis por p. Assim, o termo do lado direito também é divisível por p. Provamos agora que se p não divide a, ele deve dividir b. Isso prova o lema.
Agora vamos provar que podemos escrever um número inteiro maior que 1 de uma só forma como produto de números primos. Pegue dois produtos de números primos A e B que têm o mesmo resultado. Então sabemos para o resultado dos produtos que A = B. Pegue qualquer primes p do primeiro produto A. Ele divide o A, assim também divide o B. Usando várias vezes o lema que acabamos de provar, podemos ver que p deve então dividir pelo menos um fator b de B. Mas os fatores são todos primes em si, assim também B é primes. Mas sabemos que p também é primordial, então p deve ser igual a b. Assim, agora dividimos A por p e também dividimos B por p. E obtemos um resultado como A* = B*. Novamente podemos pegar um p primo do primeiro produto A* e descobrir que é igual a algum número no produto B*. Continuando desta forma, no final vemos que os fatores primordiais dos dois produtos devem ser exatamente os mesmos. Isto prova que podemos escrever um inteiro positivo como um produto de primes de uma única maneira.
