Решение сравнений

[Folko]

Есть ли какие-нибудь методы решение сравнений вида $a*x^n = b(\mod c)$, где $a,b,c$ - произвольные числа ($c$ может быть не равным $p$ или $p^k$, где $p$ - простое число).

[Гость]

Сначала разлагают c на множители. Потом, используя китайскую тероему об остатках, задачу сводят к решению сравнения по модулям вида p^k, где p - простое число.

[Folko]

Спасибо. А можно по подробнее.

[Folko]

Насколько я понял, мне надо разложить число с на элементарные делители, затем составить систему сравнений вида a*x^n = b(mod p^k) и решать ее?

[maxal]

Folko писал(а):

Насколько я понял, мне надо разложить число с на элементарные делители, затем составить систему сравнений вида a*x^n = b(mod p^k) и решать ее?

Да. Решение сравнения $a*x^n \equiv b \pmod c$, где $c=p_1^{k_1}\cdot\ldots\cdot p_m^{k_m}$, равносильно решению системы сравнений $a*x^n \equiv b \pmod{p_i^{k_i}}$ для $i=1..m$.

[Folko]

Большое спасибо всем за помощь

[Folko]

Возникли проблемы с решением сравнения $a*x^n\equiv b\pmod c $
Например $2x^3 \equiv 17 \pmod {41}$
Я составляю $2*u+41*v = 1$ Отсюда ясно, что $u = 21, v = -1$ и тогда переписываю
$x^3 \equiv 17*21 \pmod {41}$ Использую неравенство $x^n \equiv b \pmod c = n*ind x \equiv ind b \pmod c$ получаю $3*ind x \equiv ind 29 \pmod {41}$
или как и вначале $ind x \equiv 7*14 \pmod {41} \Rightarrow ind x \equiv 16 \pmod {41}\Rightarrow x = 6^1^6 \pmod {41}\Rightarrow x = 18$. Но $2*18^3 \pmod {41} = 20$(6 - первообразный корень) В чем ошибка? Может я вообще неправильно делаю? Как правильно решить сранение вида $a*x^n\equiv b \pmod c$. Как решить систему таких сранений. Модуль - прстое число.

[Someone]

Folko писал(а):

Использую неравенство x^n \equiv b \pmod c = n*ind x \equiv ind b \pmod c получаю 3*ind x \equiv ind 29 \pmod {41}

Вот здесь должно быть $3\mathrm{ind}(x)\equiv\mathrm{ind}(29)\pmod{40}$, то есть, $3\mathrm{ind}(x)\equiv 7\pmod{40}$, откуда $\mathrm{ind}(x)=29$ и $x=6^{29}\equiv 22\pmod{41}$. Проверка даёт $2\cdot 22^3=2\cdot 10648\equiv 17\pmod{41}$.

P.S. Внутри тега math окружайте формулу знаками $.

[Folko]

А как решить систему таких сравнений.