Re: [obm-l] DUVIDA - Primo

["Domingos Jr." <dopikas@xxxxxxxxxx>]

2^{2k+1} = 2*4^k ~ 2(3+1)^k ~ 2 (mod 3)
logo 2^{2k+1} + 1 ~ 0 (mod 3) ou seja, se n é ímpar, 2^n + 1 é divisível por
3, então só para n = 1 temos 2^n+1 e 1 = 2^0.

suponha n = s*m, e s = 2^k, com k > 0.

2^n + 1 = 2^(sm) + 1 = (2^s + 1)(2^{s(m-1)} - 2^{s(m-2)} + 2^{s(m-3)} -
... - 2^{s(1)} + 1)
portanto 2^n + 1 é composto se m > 1

um exemplo da fatoração acima:
2^20 + 1 = 2^(5*2^2) + 1 = (2^4 + 1)(2^16 - 2^12 + 2^8 - 2^4 + 1)

[ ]'s

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================