Olimpíadas ⇒ Congruências e Teorema Chinês dos Restos Tópico resolvido

[EsleyPires]

Um ponto [tex3](x, y) ∈ Z^2[/tex3] é legal se [tex3]mdc(x, y) = 1[/tex3]. Prove ou disprove: Dado um inteiro positivo [tex3]n[/tex3], existe um ponto [tex3](a, b) ∈ Z^2[/tex3] cuja distância a todo ponto legal é pelo menos [tex3]n[/tex3]?

Essa é mais uma questão do POTI que não apresenta solução no material disponibilizado. Gostaria de saber a solução para ampliar o meu entendimento sobre o Teorema Chinês dos Restos e suas aplicações. Desde já, agradeço qualquer palpite, resposta ou dica dada!

[FelipeMartinMOD]

Pensemos geometricamente nisto. Se tivermos algum ponto dentro do círculo [tex3]((a,b), n)[/tex3] com [tex3](x,y) \in \mathbb Z^2[/tex3] para algum [tex3]n[/tex3], o resultado já falha. Pensando no limite [tex3]n \to \infty[/tex3] a coisa já falha, não?

Se [tex3]\mdc(a,b) =1[/tex3] a coisa falha, pois o próprio ponto dista zero de si mesmo.

Então, [tex3]\mdc (a,b) = d \neq 1[/tex3], o ponto: [tex3]P = (\frac ad, \frac bd)[/tex3] é um dos pontos [tex3](x,y)[/tex3].

A distância entre [tex3]P[/tex3] e [tex3](a,b)[/tex3] é:

[tex3]a^2(1- \frac1{d^2}) ^2 + b^2 (1- \frac1{d^2})[/tex3], basta tomarmos [tex3]n > \sqrt{1-\frac1{d^2}} \sqrt{a^2+b^2}[/tex3].

O único problema aqui é o caso [tex3]d = -1[/tex3], neste caso é só fazer a distância entre [tex3](a,b)[/tex3] e [tex3](-a,b)[/tex3] que é [tex3]2a[/tex3]. Então [tex3]n > 2|a|[/tex3] já não dá.

Um jeito mais direto na verdade seria fazendo a distância de [tex3](a,b)[/tex3] até [tex3](1,2)[/tex3].

EDIT: o problema aqui é que [tex3](a,b)[/tex3] dependem de [tex3]n[/tex3] na verdade né? Então a minha expressão para o [tex3]n[/tex3] ficou enviezada. Desconsidere essa solução, mas vou deixá-la aqui para que os outros vejam esse erro. Acho-o importante.