Re: IMO-2000 --- problema 5

[Carlos Gustavo Tamm de Araujo Moreira <gugu@xxxxxxx>]

    Oi,Bruno,
          A sua solucao tem um problema:q-1 de fato nao pode dividir 3
elevado a k,mas nao precisa ser primo com 3,e portanto voce nao pode
concluir que q-1 divide 2u.
          Abracos,
                    Gugu
P.S.:Oi,Nicolau,manda a minha solucao xroteada...
>
>Oi pessoal
>
>Agora estou enviando a minha solucao do quinto problema da IMO-2000.
>Corrijam-me se acharem alguma besteira...
>
>Vou usar o sinal de igual para congruência.
>
>Temos que 2^n+1 é multiplo de n e n é divisível por 2000 primos.
>Seja k o maior inteiro tal que 3^k divide n. Seja q o menor primo(fora o 3)
>que divide n (logo q>3). (ou ainda: q é o menor primo que divide n/(3^k)...
>) E seja P=n/((3^k)*q). Veja que P é um produto de milhares de primos,
>contendo talvez uma potência de q em sua fatoração. Mas veja que qualquer
>primo de P é maior ou igual a q.
>
>Entao n=q*P*3^k.
>Temos 2^n=-1(mod n) e portanto 2^n=-1(mod q)
>2^(q*P*3^k)=-1(mod q) ->pelo pequeno teorema de Fermat ->  (2^(P*3^k))^q =
>-1 = 2^(P*3^k) (mod q)
>Logo
>
> 2^(2*P*3^k) = 1 (mod q)
>
>Seja r uma raiz primitiva mod q e seja u tal que r^u=2 (mod q), com 0<u<=q-1
>Então r^(2*P*u*3^k) = 1 (mod q)
>
>Por isso q-1 divide 2*P*u*3^k
>
>Mas q-1 não divide 3^k pois q-1 é par. E q-1 não divide P pois q-1 é menor
>que qualquer primo de P.
>
>Logo q-1 divide 2*u com 0<u<=q-1
>Por isso u=q-1 ou u=(q-1)/2
>
>Como r^u=2(mod q), se u for q-1 teremos 1=2 mod q absurdo. Entao u=(q-1)/2
>Mas aí r^u=+-1(mod q) ->q=1(absurdo) ou q=3(absurdo por definicao de q)
>
>Portanto não existe um tal n.
>---------------------------------------
>
>Bruno Leite
>
>
>