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" <[EMAIL PROTECTED]>
> 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 [EMAIL PROTECTED]
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
=========================================================================
