Квадратные уравнения в кольцах

[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]

Надо просто четыре раза применить китайскую теорему об остатках к парам $(x_{11}, x_{21})$, $(x_{11}, x_{22})$, $(x_{12}, x_{21})$, $(x_{12}, x_{22})$.

[Руст]

Всё обстоит не так. Находите корни для каждого простого делителя n. Их количество может быть 0, если D=B^2-4AC не является квадратичным вычетом по модулю простого числа (делителя n). Тогда нет корней и у исходного уравнения. Имеется единственный корень в случае, когда D делится на простое число р, А не делится на р, или А делится на р, но B не делится. Их количество бесконечно, когда все А,В,С делятся на р. Два когда А не делится на р, а дискриминант является квадратичным вычетом (не ноль по модулю р).
При вычислении по модулю n по каждой паре корней по модулю р и q, по китайской теореме находите корень по модулю n.

[tolstopuz]

Руст писал(а):

Всё обстоит не так.

Ну почему не так? Случай конечной характеристики для квадратного уравнения ничем принципиально не отличается от характеристики 0 - вы просто переформулировали разбор случаев из условий на коэффициенты приведенного уравнения в условия на коэффициенты исходного. А второй абзац вообще полностью совпадает с моим сообщением