Теория чисел

[SpBTimes]

Известно, что квадрат натурального числа $n$, при делении на $k$, дает в остатке $10$, а куб числа $n$ при делении на $k$ дает в остатке $33$. Найти $k$.
Задача с прошедшей 7 декабря школьной олимпиады. А как решить?

[Руст]

Очень просто, k делитель $10^3-33=967$ больше 33.

[SpBTimes]

Руст
А можно поподробнее. как к этому прийти? В моих попытках ничего подобного не обнаруживалось.

[DjD USB]

У меня почему-то получилось, что $33^2-10^3$ делится на k

-- Сб дек 14, 2013 21:56:58 --

$$(n^3)^2 \equiv 33^2 \pmod k$$

$$(n^2)^3 \equiv 33^2 \pmod k$$

$$10^3-33^2 \equiv0 \pmod k$$

[SpBTimes]

А, я болван.
$n^2 \equiv 10 (\mod k)$, $n^3 \equiv 33 (\mod k)$
Тогда и $n^6 \equiv 10^3 (\mod k)$ и $n^6 \equiv 33^2 (\mod k)$
Тогда $33^2 - 10^3$ делится на $k$, т.е. $k$ - делитель $89$, больший $33$. Ну а т.к. $89$ - простое, оно и будет ответом, если только найдется такое $n$

[DjD USB]

SpBTimes в сообщении #801007 писал(а):

А, я болван.
$n^2 \equiv 10 (\mod k)$, $n^3 \equiv 33 (\mod k)$
Тогда и $n^6 \equiv 10^3 (\mod k)$ и $n^6 \equiv 33^2 (\mod k)$
Тогда $33^2 - 10^3$ делится на $k$, т.е. $k$ - делитель $89$, больший $33$. Ну а т.к. $89$ - простое, оно и будет ответом, если только найдется такое $n$

Ну да. Думаю можно пример привести или решить сравнение первой степени с 1 неизвестным:

$$ 10n \equiv 33 \pmod {89}$$

[SpBTimes]

Да, это понятно. Что-то я тупанул.
Спасибо!

[Руст]

Я забыл, что первый раз в условии квадрат.