2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

 
 
 
 
Сообщение07.11.2005, 15:01 
Спасибо. А можно по подробнее.

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

 
 
 
 
Сообщение08.11.2005, 06:55 
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$.

 
 
 
 
Сообщение08.11.2005, 17:26 
Большое спасибо всем за помощь

 
 
 
 
Сообщение21.11.2005, 18:41 
Возникли проблемы с решением сравнения $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$. Как решить систему таких сранений. Модуль - прстое число.

 
 
 
 
Сообщение21.11.2005, 19:29 
Аватара пользователя
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 окружайте формулу знаками $.

 
 
 
 
Сообщение21.11.2005, 20:11 
А как решить систему таких сравнений.

 
 
 [ Сообщений: 9 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group