Olimpíadas ⇒ (Estônia-2000) Teoria dos Números

[cicero444]

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

[Auto Excluído (ID:12031)]

para ser primo com 120, ele não pode ser divisivel por 2, nem por 3, nem por 4 nem por 5

[tex3]p^2 \equiv 1 \mod 3[/tex3]
[tex3]p^2 \equiv 1 \mod 4[/tex3]
ou seja [tex3]p^2 = 3k + 1 = 4n + 1 \rightarrow 3k = 4n \rightarrow k[/tex3] é múltiplo de 4,logo [tex3]p^2 \equiv 1 \mod 12[/tex3]

quanto ao 5
[tex3]p \equiv 2 \mod 5[/tex3] ou [tex3]p \equiv 4 \mod 5[/tex3] então [tex3]p^2 \equiv \pm 1 \mod 5[/tex3]
se [tex3]p \equiv 4 \mod 5 \rightarrow p^2 \equiv 1 \mod 5[/tex3] e então
[tex3]p^2 \equiv 1 \mod 60[/tex3]
depois eu termino

[AdRiaN128]

Seja [tex3]n[/tex3] esse número.Como o número é primo com [tex3]120[/tex3] ele não é divisível por [tex3]3[/tex3],[tex3]5[/tex3] e [tex3]8[/tex3].
Então:
[tex3]n^2\equiv 1 \mod 3 \\
n^2\equiv \pm 1 \mod 5 \\
n^2 \equiv 1 \mod 8[/tex3]

Então temos dois casos:
1)
[tex3]n^2\equiv 1 \mod 3\\
n^2\equiv 1 \mod 5\\
n^2\equiv 1 \mod 8[/tex3]

Então,[tex3]n^2\equiv 1 \mod 120[/tex3]


2)
[tex3]n^2\equiv 1 \mod 3\\
n^2\equiv -1 \mod 5\\
n^2\equiv 1 \mod 8[/tex3]

Então [tex3]n^2\equiv 1 \mod 24[/tex3], ou seja, [tex3]n^2=24k+1[/tex3]. Substituindo:
[tex3]24k+1\equiv -1 \mod 5\\
4k\equiv 3\mod 5\\
k\equiv 2 \mod 5[/tex3]
Ou seja, [tex3]k=5m+2[/tex3]
Então,[tex3]n^2=24(5m+2)+1=120m+49[/tex3]

[tex3]n^2\equiv 49 \mod 120[/tex3]

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