Olimpíadas ⇒ (Estônia - 2000) Aritmética Tópico resolvido

[cicero444]

Determine todos os restos possíveis da divisão do quadrado de um número primo com 120 por 120.

[Cássio]

Veja que [tex3]120=2^3\times 3\times 5.[/tex3] Seja [tex3]x[/tex3] um número inteiro tal que [tex3]\text{mdc}(x,120)=1.[/tex3]

Então queremos encontrar todos os [tex3]r\in\mathbb{Z},\ \ 0\le r<120[/tex3] tal que [tex3]x^2\equiv r\pmod{120}[/tex3]

Mas isso é o mesmo que resolver o sistema:

[tex3]\begin{cases}x^2\equiv r\pmod{8}\\x^2\equiv r\pmod{3}\\ x^2\equiv r\pmod{5}\end{cases}[/tex3]

Vamos por partes:

[tex3]x^2\equiv r\pmod{8}:[/tex3]

Lembrando que [tex3]x[/tex3] só é primo com 120 se também for primo com 8, vamos atribuir os possíveis valores para [tex3]x,[/tex3] que são eles [tex3]x\equiv (1,\ 3,\ 5,\ 7)\pmod{8}\ \ \Longrightarrow\ \ x^2\equiv 1\pmod{8}.[/tex3] Ou seja: [tex3]r\equiv 1\pmod{8}.[/tex3]



[tex3]x^2\equiv r\pmod{3}:[/tex3] Vamos também atribuir os possíveis valores para [tex3]x:[/tex3]

[tex3]x\equiv (1\ \ \text{ou}\ \ 2)\pmod{3}\ \ \Longrightarrow\ \ x^2\equiv 1\pmod{3}.[/tex3] Ou seja, [tex3]r\equiv 1\pmod{3}.[/tex3]


[tex3]x^2\equiv r\pmod{5}:[/tex3] Da mesma forma, [tex3]x[/tex3] só pode ser

[tex3]x\equiv (1,\ 2,\ 3,\ 4)\pmod{5}\ \ \Longrightarrow\ \ x^2\equiv r\equiv (1\ \ \text{ou}\ \ 4)\pmod{5}.[/tex3]



Portanto, temos dois sistemas possíveis:

[tex3]\begin{cases}r\equiv 1\pmod{8}\\ r\equiv 1\pmod{3}\\ r\equiv 1\pmod{5} \end{cases}[/tex3]

ou

[tex3]\begin{cases}r\equiv 1\pmod{8}\\ r\equiv 1\pmod{3}\\ r\equiv 4\pmod{5} \end{cases}[/tex3]

Não sei se você conhece o teorema chinês do resto. Resolvendo usando o tal teorema, chegamos a resposta do primeiro sistema: [tex3]r\equiv 1\pmod{120}.[/tex3] E do segundo sistema: [tex3]r\equiv 49\pmod{120}.[/tex3]

Portanto, os possíveis restos são [tex3]1[/tex3] e [tex3]49.[/tex3]


Abraço.

[NãoCriativo]

Muito Obrigado, Cássio