Se 2n + 1 é primo, é evidente que mdc(C[2n+1, 1], C[2n+1, 2], C[2n+1, 3], ..., C[2n+1, n]) é igual a (2n+1).
Logo, max (2, 2n + 1) é igual a 2n+1 quando 2n+1 é primo, o que garante que todos os primos ímpares sejam representados. Agora seja 2n+1 um número igual a pq, sendo p e q dois fatores primos distintos, ambos menores que n+1. C [pq, p] = [pq * (pq - 1) * (pq - 2) * ... * (pq - p + 1)] / [2 * 3 * 4 * 5 * ... * p] Logo, C[pq, p] = q * [(pq - 1) * (pq - 2) * ... * (pq - p + 1)] / [2 * 3 * 4 * 5 * ... (p-1)] Observe que nenhum dos fatores do numerador acima é divisível por p, o que garante que C[pq, p] nao é divisível por p. C [pq, q] = [pq * (pq - 1) * (pq - 2) * ... * (pq - q + 1)] / [2 * 3 * 4 * 5 * ... * q] Logo, C[pq, q] = p * [(pq - 1) * (pq - 2) * ... * (pq - q + 1)] / [2 * 3 * 4 * 5 * ... (q-1)] Observe agora que nenhum dos fatores do numerador acima é divisível por q, o que garante que C[pq, q] nao é divisível por q. Mas C[pq, 1] = pq. Daí, o mdc de (pq), um número nao-divisível por p e outro número nao divisível por q é 1. Assim, max (2, 1) = 2, garantindo a presenca do 2 e excluindo compostos da forma pq. Para todos os números compostos cuja representacao em primos só possui expoentes menores que 2, o raciocínio é análogo ao anterior. Para compostos 2n+1 cuja representacao é da forma p^k * q^m * x^h * y^j *... , onde k é o expoente máximo e m é o segundo maior expoente, também vale o raciocínio, mas devemos tomar: C[2n + 1, 1], C[2n+1, p^i] , 0 < i < k+1 C[2n+1, q^i] , 0 < i < m+1 etc etc No entanto, se 2n+1 é igual a p^k, devemos tomar C[p^k, 1] e C[p^k, p^(k-1)] C[p^k, 1] = p^k C[p^k, p^(k-1)] é um número divisível por p, mas que nao é divisível por p^2. Isto garante que o mdc neste caso será igual a p. Entao máx (2, p) = p, que também é primo. ----- Original Message ----- From: "Eric Campos Bastos Guedes" <[EMAIL PROTECTED]> To: "Obm-L" <[EMAIL PROTECTED]> Sent: Domingo, 7 de Outubro de 2001 21:39 Terezan Subject: Problema sobre primos Saudações Quero propor um problema aos companheiros da lista, e ao mesmo tempo comunicar que já o resolvi. Trata-se de uma fórmula para os números primos. Lá vai... Prove que a seguinte função, definida para os inteiros positivos, gera todos os números primos, e apenas primos. f(n) = max(2, mdc(C[2n+1, 1], C[2n+1, 2], C[2n+1, 3], ..., C[2n+1, n]) onde C[a,b] é o número binomial dado por a! / (b! (a-b)!) Esta é uma das fórmulas para primos que descobri e que está no meu livro "Fórmulas que geram números primos" (Papel Virtual editora www.papelvirtual.com.br ) Abraços, Eric.