Re: IMO-2000 --- problema 5

[Bruno Leite <superbr@xxxxxxx>]

At 22:51 10/08/00 -0300, you wrote:
>
>    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

Nossa, é mesmo....e nem dá pra consertar....

Bom, valeu.. :-)

Bruno Leite

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