O produto dos números primos mais 1 é sempre primo?

Não, 5*3 é 15, e 15+1 é 16, o que não é primo. Mas a idéia é que o produto de TODOS os números primos de 2 a N, quando você então adiciona 1, produz um prime. Mas mesmo isso não é exatamente a prova de Euclides. (Feche, entretanto.) Assuma que P é o produto de TODOS os primes.

Como já foi apontado, a prova de Euclid não é que P + 1 é necessariamente prime (é), mas que o número de primes não pode ser finito. Vamos analisar tudo isto. Considere, para P produto de todos os primes:

M = P + 1

M não pode ser dividido por nenhum número N, N > 2, no qual N também se divide em P. Porque isso significaria:

m * N = p * N + 1

(m * N) - (p * N) = 1

(m - p) * N = 1

m - p = 1/N

Chegamos a uma contradição, porque m e p são ambos números inteiros, produzindo um resultado inteiro. Mas para N > 1, a expressão 1/N não produz um número inteiro mas sim uma fração.

Portanto, se P pode ser dividido uniformemente por um N > 1, então P + 1 não pode ser dividido uniformemente por N. Isso é chave.

E a consequência é que se P pode ser dividido por todos os fatores principais 2, 3, ... n, então P+1 não pode ser dividido por nenhum desses mesmos fatores. Portanto, deve haver outro número primo que ainda não contabilizamos... ou o próprio P+1 ou algum outro número. O que prova por contradição que o número de primes não pode ser finito.

O passo final é normalmente lustrado. Porque o passo final é perguntar se P+1 é prime.

Se for, então encontramos um novo prime.

Se não for, então P + 1 deve ser divisível por algum prime. Mas não pode ser nenhum dos primes que se dividem em P (por suposição no nosso argumento). Portanto, nós encontramos um novo prime.

De qualquer forma, uma contradição é produzida a partir da suposição original de que havia um número finito de primes.