Cравнения первого степеня вида ax=b(mod m)

@Zavulon · Регистрация: 08.12.2010

Помогите решить сравнения первого степеня вида 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), то вручную перебирать их затруднительно, нужно, чтобы это делала программа. Пожалуйста, обьясните коды доступно.

@Zavulon · 14.12.2010, 00:34 **[ТС]**

хм, господа, в чем дело?
мне нужно не решение этих производных, а именно программа. Может, не там тему подняла? Если да, то переместите пожалуйста.
Алгоритм решения сравнений первой степени $https://www.cyberforum.ru/cgi-bin/latex.cgi?ax\equiv b\left(mod m \right)$ :
Возьмем для примера $https://www.cyberforum.ru/cgi-bin/latex.cgi?124x\equiv 72\left(mod 152 \right)$
1. Найдем НОД $https://www.cyberforum.ru/cgi-bin/latex.cgi?\left(a,m \right)=d$ с помощью алгоритма Евклида:
а) Если $https://www.cyberforum.ru/cgi-bin/latex.cgi?m>a$ , то:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?m=aq_0+r_1; a=r_1q_1+r_2; r_1=r_2q_2+r_3; ... r_n-1=r_nq_n.$
б) Если $https://www.cyberforum.ru/cgi-bin/latex.cgi?m<a$ , то:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?a=mq_0+r_1; m=r_1q_1+r_2; r_1=r_2q_2+r_3; ... r_n-1=r_nq_n.$
Тогда наибольший общий делитель $https://www.cyberforum.ru/cgi-bin/latex.cgi?d=r_n$ .
2. Далее рассматриваются два случая:
а) Если $https://www.cyberforum.ru/cgi-bin/latex.cgi?b$ не кратно $https://www.cyberforum.ru/cgi-bin/latex.cgi?d$ , то у сравнения нет решения.
б) Если $https://www.cyberforum.ru/cgi-bin/latex.cgi?b$ кратно $https://www.cyberforum.ru/cgi-bin/latex.cgi?d$ , то у сравнения есть ровно $https://www.cyberforum.ru/cgi-bin/latex.cgi?d$ решений.
3. Сокращаем уравнение на $https://www.cyberforum.ru/cgi-bin/latex.cgi?d$ : $https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{a}{d}x=\frac{b}{d}\left(mod \frac{m}{d} \right)$ так, чтобы $https://www.cyberforum.ru/cgi-bin/latex.cgi?a$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?m$ стали взаимно простыми числами $https://www.cyberforum.ru/cgi-bin/latex.cgi?\left(\frac{a}{d}, \frac{m}{d} \right)=1$
4. Снова используем алгоритм Евклида для $https://www.cyberforum.ru/cgi-bin/latex.cgi?\left(a_1, m_1 \right)=1$ :
Тоже самое, что и в 1.а)\1.б)
5. Таблица для нахождения числителей подходящих дробей:
a) Если $https://www.cyberforum.ru/cgi-bin/latex.cgi?m>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 |
|____|___|_____|__________|___|_______________|
б) Если $https://www.cyberforum.ru/cgi-bin/latex.cgi?m<a$ , то:
__________________________________________________ _____________
|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. И наконец, $https://www.cyberforum.ru/cgi-bin/latex.cgi?x\equiv {\left(-1 \right)}^{n-1}b{P}_{n-1}\left(mod m \right)$ .
Причем значение икса не должно перевышать $https://www.cyberforum.ru/cgi-bin/latex.cgi?0<x<m-1$ .
Если $https://www.cyberforum.ru/cgi-bin/latex.cgi?x\neq [0,m-1]$ , то к значению $https://www.cyberforum.ru/cgi-bin/latex.cgi?x$ прибавляем $https://www.cyberforum.ru/cgi-bin/latex.cgi?m_1$ до тех пор, пока $https://www.cyberforum.ru/cgi-bin/latex.cgi?x=[0,m_1]$ .
Вот собсно, и все

ЗЫ: извиняюсь за ужасную таблицу

@Zavulon 0 / 0 / 0 Регистрация: 08.12.2010 Сообщений: 3
		1
	Cравнения первого степеня вида ax=b(mod m) 09.12.2010, 02:28. Показов 5566. Ответов 1 Метки нет (Все метки) Помогите решить сравнения первого степеня вида ax=b(mod m) и написать программу, решаюшую такие уравнения на C++. Пример: 2х=5(mod 3). Остаток m -> [0], [1], [2]. x1=0 -> 20-5/3=-5/3 не принадлежит Z. Следовательно, x1=0 не есть решением. x2=1 -> 21-5/3=-1 принадлежит Z. Следовательно, x2=1 есть решением. x3=2 -> 2*2-5/3=-1/3 не принадлежит Z. Следовательно, x3=2 не есть решением. Это примерный алгоритм решения для простых уравнений. Если имеются уравнения вида: 124х=72(mod 152), то вручную перебирать их затруднительно, нужно, чтобы это делала программа. Пожалуйста, обьясните коды доступно. __________________ Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь 0

@Zavulon 0 / 0 / 0 Регистрация: 08.12.2010 Сообщений: 3
	14.12.2010, 00:34 [ТС]	2
	хм, господа, в чем дело? мне нужно не решение этих производных, а именно программа. Может, не там тему подняла? Если да, то переместите пожалуйста. Алгоритм решения сравнений первой степени $https://www.cyberforum.ru/cgi-bin/latex.cgi?ax\equiv b\left(mod m \right)$ : Возьмем для примера $https://www.cyberforum.ru/cgi-bin/latex.cgi?124x\equiv 72\left(mod 152 \right)$ 1. Найдем НОД $https://www.cyberforum.ru/cgi-bin/latex.cgi?\left(a,m \right)=d$ с помощью алгоритма Евклида: а) Если $https://www.cyberforum.ru/cgi-bin/latex.cgi?m>a$ , то: $https://www.cyberforum.ru/cgi-bin/latex.cgi?m=aq_0+r_1;<br /> a=r_1q_1+r_2;<br /> r_1=r_2q_2+r_3;<br /> ...<br /> r_n-1=r_nq_n.$ б) Если $https://www.cyberforum.ru/cgi-bin/latex.cgi?m<a$ , то: $https://www.cyberforum.ru/cgi-bin/latex.cgi?a=mq_0+r_1;<br /> m=r_1q_1+r_2;<br /> r_1=r_2q_2+r_3;<br /> ...<br /> r_n-1=r_nq_n.$ Тогда наибольший общий делитель $https://www.cyberforum.ru/cgi-bin/latex.cgi?d=r_n$ . 2. Далее рассматриваются два случая: а) Если $https://www.cyberforum.ru/cgi-bin/latex.cgi?b$ не кратно $https://www.cyberforum.ru/cgi-bin/latex.cgi?d$ , то у сравнения нет решения. б) Если $https://www.cyberforum.ru/cgi-bin/latex.cgi?b$ кратно $https://www.cyberforum.ru/cgi-bin/latex.cgi?d$ , то у сравнения есть ровно $https://www.cyberforum.ru/cgi-bin/latex.cgi?d$ решений. 3. Сокращаем уравнение на $https://www.cyberforum.ru/cgi-bin/latex.cgi?d$ : $https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{a}{d}x=\frac{b}{d}\left(mod \frac{m}{d} \right)$ так, чтобы $https://www.cyberforum.ru/cgi-bin/latex.cgi?a$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?m$ стали взаимно простыми числами $https://www.cyberforum.ru/cgi-bin/latex.cgi?\left(\frac{a}{d}, \frac{m}{d} \right)=1$ 4. Снова используем алгоритм Евклида для $https://www.cyberforum.ru/cgi-bin/latex.cgi?\left(a_1, m_1 \right)=1$ : Тоже самое, что и в 1.а)\1.б) 5. Таблица для нахождения числителей подходящих дробей: a) Если $https://www.cyberforum.ru/cgi-bin/latex.cgi?m>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 \| \|____\|___\|_____\|__________\|___\|_______________\| б) Если $https://www.cyberforum.ru/cgi-bin/latex.cgi?m<a$ , то: __________________________________________________ _____________ \|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. И наконец, $https://www.cyberforum.ru/cgi-bin/latex.cgi?x\equiv {\left(-1 \right)}^{n-1}b{P}_{n-1}\left(mod m \right)$ . Причем значение икса не должно перевышать $https://www.cyberforum.ru/cgi-bin/latex.cgi?0<x<m-1$ . Если $https://www.cyberforum.ru/cgi-bin/latex.cgi?x\neq [0,m-1]$ , то к значению $https://www.cyberforum.ru/cgi-bin/latex.cgi?x$ прибавляем $https://www.cyberforum.ru/cgi-bin/latex.cgi?m_1$ до тех пор, пока $https://www.cyberforum.ru/cgi-bin/latex.cgi?x=[0,m_1]$ . Вот собсно, и все ЗЫ: извиняюсь за ужасную таблицу 0

Опции темы