IMO-2000 --- problema 5

[Bruno Leite <superbr@xxxxxxx>]

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