Re: Problema sobre primos

["Alexandre F. Terezan" <aleterezan@xxxxxxxxxxxxx>]

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" <mathfire@ig.com.br>
To: "Obm-L" <obm-l@mat.puc-rio.br>
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.