Программы решения сравнений

Прошу помощи в написании программы для решения сравнений, уже голову сломал, вроде всё просто должно быть, но никак не доходит... Алгоритм решения сравнений первой степени : Возьмем для примера 1. Найдем НОД с помощью алгоритма Евклида: а) Если , то:б) Если , то:Тогда наибольший общий делитель . 2. Далее рассматриваются два случая: а) Если не кратно , то у сравнения нет решения. б) Если кратно , то у сравнения есть ровно решений. 3. Сокращаем уравнение на : так, чтобы и стали взаимно простыми числами 4. Снова используем алгоритм Евклида для : Тоже самое, что и в 1.а)\1.б) 5. Таблица для нахождения числителей подходящих дробей: a) Если , то: _____________________________________________ |Q_n:| 0 | q_0 | q_1 | ... | q_n | |____|___|_____|__________|___|_______________| |P_n:| 1 | q_0 | q_0q_1+1 | ... | p_n-1q_n+p_n-2 | |____|___|_____|__________|___|_______________| б) Если , то: _______________________________________________________________ |Q_n:| 0 | 0 | q_0 | q_1 | q_2 | ... | q_n | |____|___|___|_____|__________|__________|_____|________________| |P_n:| 1 | 0 | 1 | q_1 | q_1q_2+1 | ... | p_n-1q_n+p_n-2 | |____|___|___|_____|__________|__________|_____|________________| 6. И наконец, . Причем значение икса не должно перевышать . Если , то к значению прибавляем до тех пор, пока .С нахождением НОД всё разуметься понятно, а вот далее начинают возникать проблемы
4 ответа

Если ещё актуально, могу скинуть вариант реализации на си. Думаю без особых проблем переведёте на Delphi.P.S. Для программной реализации Вы выбрали слишком суровый алгоритм, это для ручного счёта.


Alexdemath, Да, если можно. Был бы очень благодарен.


Eskal, смотри здесьhttp://www.np.ac.rs/index.php/yu/pre...rithm/downloadна 2-й стр. подраздел "2 Solving of modular equations" (c псевдокодом).


Благодарю.