Oi, Duda:
As solucoes que eu tinha em mente sao um pouco diferentes - ambas dependem
do pequeno teorema de Fermat e a do 2o. tambem envolve o teorema de Wilson:
1) Suponha que n > 1 e n | 2^n - 1.
Eh facil ver que n nao pode ser par, certo?
Assim, supondo n impar, seja p o menor fator primo (impar) de n.
Nesse caso, mdc(n,p-1) = 1, pois todos os fatores primos de p-1 sao < p e
todos os de n sao >= p (voce usou a mesma consideracao na sua solucao).
p | n e n | 2^n - 1 ==> p | 2^n - 1
Mas, pelo PTF, temos que p | 2^(p-1) - 1.
Logo:
p | mdc(2^n - 1,2^(p-1) - 1) ==>
p | 2^mdc(n,p-1) - 1 ==>
p | 2^1 - 1 = 1 ==>
contradicao.
*****
2) Como voce disse, p = 2 eh trivial. Assim, suponhamos que p eh impar.
IDA:
Seja N uma solucao de x^2 == -1 (mod p) ==> N^2 == -1 (mod p).
Isso implica que mdc(N,p) = 1.
Elevando a congruencia ao expoente (p-1)/2, teremos:
N^(p-1) == (-1)^((p-1)/2) (mod p)
Mas, por pequeno Fermat, temos que N^(p-1) == 1 (mod p).
Ou seja, (-1)^((p-1)/2) == 1 (mod p) ==> (p-1)/2 eh par ==> p == 1 (mod 4).
VOLTA:
Seja p um primo tal que p == 1 (mod 4).
O teorema de Wilson diz que (p-1)! == -1 (mod p).
Mas (p-1)! = 1*2*3*...*((p-1)/2)*((p+1)/2)*...*(p-3)*(p-2)*(p-1)
Alem disso, mod p:
(p+1)/2 == -(p-1)/2
(p+3)/2 == -(p-3)/2
...
p - 3 == -3
p - 2 == -2
p - 1 == -1
Multiplicando tudo, obtemos:
(p-1)! == (-1)^((p-1)/2) * [((p-1)/2)!]^2
Ou seja: (-1)^((p-1)/2) * [((p-1)/2)!]^2 == -1 (mod p)
Mas p == 1 (mod 4) ==> (p-1)/2 eh par ==> (-1)^((p-1)/2) = 1 ==>
[((p-1)/2)!]^2 == -1 (mod p) ==>
((p-1)/2)! eh uma solucao de x^2 == -1 (mod p).
******
Nao sei quanto a automorfismos, mas considere o grupo G dos inversiveis (mod
a^n-1). Eh claro que |G| = Phi(a^n - 1).
Como mdc(a,a^n-1) = 1, o conjunto H = {1, a, a^2, ...,a^(n-1)} eh de fato um
subgrupo de G e tal que |H| = n. Assim, pelo teorema de Lagrange temos que n
divide Phi(a^n - 1).
Um abraco,
Claudio.
on 17.08.03 10:44, Eduardo Casagrande Stabel at [EMAIL PROTECTED] wrote:
> 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
> =========================================================================
>
=========================================================================
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
=========================================================================
