|
xatkaru |
|
|
|
Пусть дано квадравтное уравнение Ax^2+Bx+C=0 (mod n), n=p*q, p,q - простые числа
Необходимо решить данное уравнение, используя китайскую теорему об остатках.
Решаем систему из двух уравнений: Ax^2+Bx+C=0 (mod p), Ax^2+Bx+C=0 (mod q), находим x(1,1), x(1,2), x(2,1), x(2,2) - корни соответствующих уравнений.
Вопрос: как отсюда найти корни исходного уравнения? Может, есть какая формула, как в случае китайской теоремы для многочлена первой степени?
|
|
|
|
 |
|
tolstopuz |
|
|
Надо просто четыре раза применить китайскую теорему об остатках к парам  ,  ,  ,  .
|
|
|
|
|
|
Руст |
|
|
|
Всё обстоит не так. Находите корни для каждого простого делителя n. Их количество может быть 0, если D=B^2-4AC не является квадратичным вычетом по модулю простого числа (делителя n). Тогда нет корней и у исходного уравнения. Имеется единственный корень в случае, когда D делится на простое число р, А не делится на р, или А делится на р, но B не делится. Их количество бесконечно, когда все А,В,С делятся на р. Два когда А не делится на р, а дискриминант является квадратичным вычетом (не ноль по модулю р).
При вычислении по модулю n по каждой паре корней по модулю р и q, по китайской теореме находите корень по модулю n.
|
|
|
|
|
|
tolstopuz |
|
|
Руст писал(а): Всё обстоит не так. Ну почему не так? Случай конечной характеристики для квадратного уравнения ничем принципиально не отличается от характеристики 0 - вы просто переформулировали разбор случаев из условий на коэффициенты приведенного уравнения в условия на коэффициенты исходного. А второй абзац вообще полностью совпадает с моим сообщением 
|
|
|
|
|
