Re: [obm-l] Sobre as olimpiadas ao redor do mundo(e um certoDEOLIVEIRASOU...)

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

Title: Re: [obm-l] Sobre as olimpiadas ao redor do mundo(e um certo DEOLIVEIRASOU...)

on 16.04.03 20:40, DEOLIVEIRASOU@aol.com at DEOLIVEIRASOU@aol.com wrote:

> Valeu grande dirichlet....o Claudio pratica( grande Claudiao) me mandou a solucao...de qualquer forma obrigado pela dica.
> Aproveitando a deixa , esse recado vai para o Claudio sobre o problema da eureka( Olimpiadas ao redor do mundo. O enunciado segue na integra...meu teclado esta com problemas , entao vou tentar nao ser ambiguo com o enunciado...
> Problema------- Determine todos os restos possiveis da divisao do quadrado de um numero primo com 120 por 120( Estönia 2000). Vi uma ideia num problema russo de 1940(47?). Fiz um esboco, mas ainda nao parei pra trabalhar nele....
>   Antes que me esqueca, valeu a resolucao do problema dos primos da forma 101010.......101, Claudio.
>         Crom 

Oi, Crom:

Agora eu entendi! O problema eh:
Seja n um inteiro tal que mdc(n,120) = 1.
Quais os restos possiveis da divisao de n^2 por 120?

O algorimo da divisao diz que existem inteiros q e r tais que:
n^2 = 120q + r   com   0 <= r <= 119.

Alem disso, temos que:
mdc(n,120) = 1 <==> mdc(n^2,120) = 1

Assim:
mdc(n^2,120) = mdc(120q + r,120) = mdc(r,120) = 1.

Logo, r limita-se aos Phi(120) = Phi(8*3*5) = (8-4)*(3-1)*(5-1) = 32 inteiros tais que 1 <= r <= 120 e mdc(r,120) = 1.

A questao agora eh: variando-se n, todos os 32 valores de r sao de fato obtidos?

A resposta eh nao. Eis o porque:

A equacao n^2 = 120q + r eh equivalente a congruencia:
n^2 == r (mod 120), ou seja, r eh um resto quadratico (mod 120)

Assim, a resposta do problema eh: r pertence a intersecao dos seguintes 3 conjuntos:
A = {0,1,2,3,...,119}
B = {x inteiros tais que mdc(x,120) = 1}
C = {x inteiros tais que x eh um resto quadratico (mod 120)}

A inter B inter C eh obtido tomando-se os 16 elementos de A inter B que sao menores do que 60, elevando-os ao quadrado e reduzindo-os (mod 120). 

Isso porque:
mdc(x,120) = 1 <==> mdc(120 - x,120)
e
x^2 == (120-x)^2 (mod 120)

Assim:
A inter B inter {1,2,...,60} = 
{01,07,11,13,   17,19,23,29,   31,37,41,43,   47,49,53,59}

Os quadrados correspondentes (reduzidos mod 120 serao):
{01,49,01,49,   49,01,49,01,   01,49,01,49,   49,01,49,01}

Ou seja, os restos possiveis sao 1 e 49.

*****

Repare que a solucao acima, apesar de correta, segue a linha do "eu sou burro mas nao sou cego", ou seja, usa conceitos e ferramentas que sao mais ou menos obvios dado o enunciado  (algoritmo da divisao - pois o enunciado fala em resto da divisao; propriedades basicas do mdc e da funcao Phi de Euler - pois n eh dito ser primo com 120; finalmente, a definicao de resto quadratico - pois o problema pede os restos de n ao quadrado - essa eh a parte do "eu nao sou cego") mas no final calcula no braco os quadrados de 16 numeros e os reduz mod 120 (essa eh a parte do "eu sou burro") e chega num resultado aparentemente surpreendente: estes 16  quadrados sao congruentes apenas a 1 ou 49 (mod 120).

Uma maneira mais sofisticada de se resolver o problema seria observar que:
mdc(n,120) = 1 ==> 
mdc(n,8*3*5) = 1 ==>
mdc(n,8) = mdc(n,3) = mdc(n,5) = 1

No entanto:
mdc(n,8) = 1 ==>
n eh impar ==>
n == 1, 3, 5 ou 7 (mod 8) ==>
n^2 == 1 (mod 8)

mdc(n,3) = 1 e o pequeno teorema de Fermat ==>
n^2 == 1 (mod 3)

mdc(n,5) = 1 e o pequeno teorema de Fermat ==>
n^4 == 1 (mod 5) ==>
n^2 == 1 (mod 5)   ou   n^2 == -1 (mod 5)

Pelo teorema chines dos restos, existe uma unica solucao em n^2 (mod 120) para cada um dos dois sistemas de congruencias resultante:
n^2 == 1 (mod 8)
n^2 == 1 (mod 3)
n^2 == 1 (mod 5)

ou

n^2 == 1 (mod 8)
n^2 == 1 (mod 3)
n^2 == -1 (mod 5)

A solucao do primeiro eh obviamente n^2 == 1 (mod 120)

A solucao do segundo pode ser obtida da seguinte forma (solucao excessivamente detalhada para ilustrar o metodo):
n^2 == -1 (mod 5) ==>
n^2 = -1 + 5a (a inteiro) ==>

-1 + 5a == 1 (mod 3) ==>
5a == 2 (mod 3) ==>
2a == 2 (mod 3) ==>
a == 1 (mod 3) ==>
a = 1 + 3b (b inteiro) ==>

n^2 = -1 + 5(1 + 3b) ==>
n^2 = 4 + 15b ==>

4 + 15b == 1 (mod 8) ==>
15b == -3 (mod 8) ==>
-b == -3 (mod 8) ==>
b == 3 (mod 8) ==>
b = 3 + 8c (c inteiro) ==>

n^2 = 4 + 15(3 + 8c) ==>
n^2 = 49 + 120c ==>
n^2 == 49 (mod 120)

Ou seja, os restos possiveis sao 1 e 49.

*****

A primeira solucao que me ocorreu foi a bracal. No entanto, depois de verificar que aqueles 16 quadrados eram congruentes a apenas dois numeros, eu passei a achar que deveria haver algo especial com quadrados modulo 120. Foi so entao que eu imaginei a segunda solucao. Acho que a medida em que a pessoa vai ficando mais experiente, as solucoes mais sofisticadas (e, espera-se, menos bracais) vao aparecedo com mais naturalidade. 

Conclusao: tambem em matematica, parece que vale 1% de inspiracao e 99% de transpiracao - quanto mais voce estuda e pratica, mais inteligente voce fica...

Um abraco,
Claudio.