Решить сравнения в кольцах вычетов

[Turmat]

Помогите разобраться, как решить например такое сравнение не подбором
$x^2\equiv10 \mod 13$

-- 10.10.2011, 22:25 --

То есть я так понимаю, что по свойству симметричности получаем, что
$10\equiv x^2 \mod 13$
Значит $x^2=36,49$
То есть $x=6,7$

[nnosipov]

Turmat в сообщении #491458 писал(а):

как решить например такое сравнение не подбором

Поскольку модуль сравнения довольно мал, подбор $x$ вполне адекватен (и Вы легко с этим справились). Другое дело, когда модуль сравнения велик. Вот здесь пришлось бы изобретать что-то другое. Но это уже другая тема.

[Turmat]

А тогда вопрос, до какого числа нужно перебирать?
То есть $x$ перебирать до числа, по которому $\mod$ берется?

[Хорхе]

Ну вроде для 13 (и сравнимых с ним по модулю 8) формула есть. Сейчас поищу.

-- Пн окт 10, 2011 22:53:25 --

Вот, нашел. (Вернее, не я нашел, а Лагранж Лежандр.) Если $p\mod 8 = 5$, то решение уравнения $x^2 = a\pmod p$ -- это

$$ x = \begin{cases} \pm a^{(p+3)/8},\quad & a^{(p-1)/4}=1 \pmod p,\\ \pm a^{(p+3)/8}2^{(p-1)/4},\quad & a^{(p-1)/4}=-1 \pmod p. \end{cases} $$

Если $a^{(p-1)/4}\neq \pm 1$, то решений нет

[nnosipov]

Turmat в сообщении #491469 писал(а):

То есть $x$ перебирать до числа, по которому $\mod$ берется?

До примерно половины этого числа.

Хорхе в сообщении #491470 писал(а):

Ну вроде для 13 (и сравнимых с ним по модулю 8) формула есть.

Да, действительно есть. Чтобы ТС правильно понял, добавлю: в этой формуле $p$ предполагается простым числом.

[Хорхе]

А, ну простое, конечно

Для 13, естественно, никакого смысла эту формулу использовать нет. Для всех небольших чисел решается лучше всего подбором.