[obm-l] Re: [obm-l] Re: [obm-l] Teoria dos Números

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

1) Seja n = b * p^i onde p é o menor primo que divide n e b não é divisível
por p. Se n dividir 2^n - 1, nós deveremos ter 2^(b*p^i) == 1 (mod p), o que
implica que b*p^i é um múltiplo da ordem de 2 no módulo p. A ordem de 2 no
módulo p, por sua vez, divide Phi(p) = p - 1, portanto b*p^i e Phi(p) = p -
1 são múltiplos da ordem de 2 no módulo p. Mas p - 1 não possui fatores
primos maiores do que p, e b*p^i não posssui fatores primos menores do que
p, isto só se verifica se Phi(p) = p - 1 = 1. Ou seja, n precisa ser
múltiplo de 2. Mas é claro que 2^n - 1 é um número ímpar e não pode ser
divisível por n, que é par


-----

A minha sol. ficou bem parecida:

seja p um primo que divide n (p > 2, pois n não pode ser par!)
n = p*m[0] para algum m[0] inteiro
2^n - 1 = 2^(p*m[0]) - 1 = (2^p)^m[0] - 1 = 2^m[0] - 1 (mod p)
pois 2^p = 2 (mod p)
se p|m[0] então tome m[0] = p*m[1] e temos
2^n - 1 = 2^m[0] - 1 = 2^m[1] - 1 (mod p), continue o processo até obter
m[k] tq p não divide m[k], logo
2^n - 1 = 2^m[k] - 1 (mod p)
mas se n|[2^n-1] temos que p|[2^n-1] e logo
2^m[k] = 1 (mod p), mas isso ocorre <=> (p-1)|m[k], mas (p - 1) é par, logo
m[k] é par e n é par, absurdo!

[ ]'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
=========================================================================