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

["Eduardo Casagrande Stabel" <dudasta@xxxxxxxxxxxx>]

Olá Cláudio!

Eu acho que você sabe as soluções dos exercícios. Mas envio as minhas,
gostei do problema um. O problema dois é clássico.

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.

2) O caso p = 2 pode ser tratado em separado, é claro que x = 1 é uma
solução da congruência x^2 + 1 == 0 (mod 2).

Consideremos p um primo ímpar. Se p == 1 (mod 4), considere a equação P(x) =
x^(p - 1) + 1 == 0 (mod p). Ela possui p - 1 raízes módulo p (só o zero não
é raiz dela). Como p é impar, p - 1 é par e podemos fatorar o polinômio como

P(x) = { x^[ (p-1)/2 ] - 1 }.{ x^[ (p-1)/2 ] + 1 }

O primeiro termo em chaves contribui com (p-1)/2 raízes e o segundo com
(p-1)/2 raízes, portanto cada um deles tem pelo menos uma raiz. Seja x uma
raíz do segundo, e chame p = 4k + 1, temos

x^[ (p-1)/2 ] + 1 = x^[ 4k / 2 ] + 1 = x^(2k) + 1 = (x^k)^2 + 1 == 0 (mod p)

Temos X = x^k satisfazendo a congruência X^2 + 1 == 0 (mod p).

Reciprocamente, se existe um x satisfazendo x^2 + 1 == 0 (mod p). Temos p
dividindo x^2 + 1 = (x + i)(x - i). Mas o domínio Z[i] é fatorial (de
fatoração única), portanto se p for irredutível (em Z[i]) ele deve dividir x
+ i ou x - i. Se p(e + fi) = x +- i então pf = +-1, contradição, logo p é um
elemento redutível de Z[i]. Ou seja, p = (a + bi)(c + di). Tomando normas:
p^2 = (a^2 + b^2)(c^2 + d^2), que implica (sem perda de generalidade) que p
= (a^2 + b^2). Mas os quadrados módulo 4 são 0 e 1, logo p é == 0, 1 ou 2
(mod 4), como ele é ímpar só resta a possibilidade p == 1 (mod 4).

Este problema que eu propus, e que você resolveu muito bem, estava no
parágrafo oito do capíulo de teoria dos grupos do livro dos Hernstein. Este
parágrafo falava sobre automorfismos. Eu suspeito que a idéia era usar algum
dos resultados sobre automorfismos do livro. Será que lhe surge alguma idéia
de o que o Hernstein tinha em mente?

Abração,
Duda.

From: "Claudio Buffara" <claudio.buffara@terra.com.br>
> Oi, Duda:
>
> Que tal estes aqui?
>
> 1) Prove que se n eh inteiro e n > 1, entao n nao divide 2^n - 1.
>
> 2) Se p eh primo, entao a congruencia x^2 + 1 == 0 (mod p) tem solucao se
e
> somente se p = 2 ou p == 1 (mod 4).
>
> Um abraco,
> Claudio.
>
> on 16.08.03 05:54, Eduardo Casagrande Stabel at dudasta@terra.com.br
wrote:
>
> > Olá pessoal!
> >
> > Prove que se n > 1 e a > 0 são inteiros então n | PHY(a^n - 1).
> >
> > PHY é a função de Euler.
> >
> > Abraço,
> > Duda.
> >
> >
=========================================================================
> > 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
> >
=========================================================================
> >
>
> =========================================================================
> 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
> =========================================================================
>
>

=========================================================================
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
=========================================================================