@Zavulon

Помогите решить сравнения первого степеня вида ax=b(mod m) и написать программу, решаюшую такие уравнения на C++.

Пример: 2х=5(mod 3). Остаток m -> [0], [1], [2].
x1=0 -> 2*0-5/3=-5/3 не принадлежит Z. Следовательно, x1=0 не есть решением.
x2=1 -> 2*1-5/3=-1 принадлежит Z. Следовательно, x2=1 есть решением.
x3=2 -> 2*2-5/3=-1/3 не принадлежит Z. Следовательно, x3=2 не есть решением.

Это примерный алгоритм решения для простых уравнений. Если имеются уравнения вида: 124х=72(mod 152), то вручную перебирать их затруднительно, нужно, чтобы это делала программа. Пожалуйста, обьясните коды доступно.

0

@Zavulon

хм, господа, в чем дело?
мне нужно не решение этих производных, а именно программа. Может, не там тему подняла? Если да, то переместите пожалуйста.
Алгоритм решения сравнений первой степени :
Возьмем для примера
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. И наконец, .
Причем значение икса не должно перевышать .
Если , то к значению прибавляем до тех пор, пока .
Вот собсно, и все
ЗЫ: извиняюсь за ужасную таблицу

0