[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [obm-l] Re: [obm-l] Teoria dos Números
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 dudasta@terra.com.br 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" <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
> =========================================================================
>
=========================================================================
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
=========================================================================