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