WikiSort.ru - Не сортированное

Неоднозначность

Нахождение коэффициентов Безу эквивалентно решению диофантового уравнения первого порядка с двумя неизвестными:

${\displaystyle ax+by=d,}$ где ${\displaystyle d=}$ НОД${\displaystyle (a,b).}$

Или, что то же самое:

${\displaystyle {\frac {a}{d}}x+{\frac {b}{d}}y=1.}$

Отсюда следует, что коэффициенты Безу ${\displaystyle x,y}$ определены неоднозначно — если какие-то их значения ${\displaystyle x_{0},y_{0}}$ известны, то всё множество коэффициентов даётся формулой^[8]

${\displaystyle \left\{\left(x_{0}+{\frac {kb}{d}},y_{0}-{\frac {ka}{d}}\right)\mid k=0,\pm 1,\pm 2,\pm 3\dots \right\}.}$

Ниже будет показано, что существуют коэффициенты Безу, удовлетворяющие неравенствам ${\displaystyle |x|<\left|{\frac {b}{d}}\right|}$ и ${\displaystyle |y|<\left|{\frac {a}{d}}\right|}$ .

Вычисление коэффициентов с помощью алгоритма Евклида

Имеется викиучебник по теме
«Программные реализации расширенного алгорима Евклида»

Для нахождения коэффициентов Безу можно использовать расширенный алгоритм Евклида нахождения НОД и представить остатки в виде линейных комбинаций a и b^[9]. Шаги алгоритма записываются в следующем виде:

${\displaystyle r_{1}=a-bq_{0},}$

${\displaystyle r_{2}=b-r_{1}q_{1}=b-(a-bq_{0})q_{1}=b(1+q_{0}q_{1})-aq_{1},}$

${\displaystyle r_{3}=r_{1}-r_{2}q_{2}=(a-bq_{0})-(b(1+q_{0}q_{1})-aq_{1})q_{2}=a(1+q_{1}q_{2})-b(q_{0}+q_{2}+q_{0}q_{1}q_{2}),}$

…

${\displaystyle r_{n}=r_{n-2}-r_{n-1}q_{n-1}=\dots =ax+by.}$

Пример

Найдём соотношение Безу для ${\displaystyle a=991,b=981.}$ Формулы алгоритма Евклида имеют вид

${\displaystyle 991=981\cdot 1+10,}$

${\displaystyle 981=10\cdot 98+1,}$

${\displaystyle 10=1\cdot 10.}$

Таким образом, НОД${\displaystyle (991,981)=1}$ . Из этих формул получаем:

${\displaystyle 10=991-1\cdot 981,}$

${\displaystyle 1=981-10\cdot 98=981-98\cdot (991-981)=99\cdot 981-98\cdot 991.}$

В итоге соотношение Безу имеет вид

${\displaystyle 1=99\cdot 981-98\cdot 991.}$

Вычисление коэффициентов с помощью непрерывных дробей

Альтернативный (по существу эквивалентный) способ решения уравнения ${\displaystyle ax+by=d}$ использует непрерывные дроби. Разделим обе части уравнения на НОД: ${\displaystyle a_{1}x+b_{1}y=1}$ . Далее разложим ${\displaystyle {\frac {|a_{1}|}{|b_{1}|}}}$ в непрерывную дробь и подсчитаем подходящие дроби ${\displaystyle {\frac {p_{k}}{q_{k}}}}$ . Последняя (${\displaystyle n}$ -я) из них будет равна ${\displaystyle {\frac {|a_{1}|}{|b_{1}|}}}$ и связана с предыдущей обычным соотношением:

${\displaystyle p_{n}q_{n-1}-q_{n}p_{n-1}=(-1)^{n-1}.}$

Подставив в эту формулу ${\displaystyle p_{n}=a_{1};q_{n}=b_{1}}$ и умножив обе части на ${\displaystyle d}$ , получаем

${\displaystyle aq_{n-1}-bp_{n-1}=\pm d.}$

С точностью до знака, это соотношение Безу. поэтому предпоследняя подходящая дробь ${\displaystyle {\frac {p_{n-1}}{q_{n-1}}}}$ даёт модули решения: ${\displaystyle |x|}$ есть знаменатель этой дроби, а ${\displaystyle |y|}$  — числитель. Осталось, исходя из первоначального уравнения, найти знаки ${\displaystyle x,y}$ ; для этого достаточно найти последние цифры в произведениях ${\displaystyle |ax|,|by|}$ ^[10].

Минимальные пары коэффициентов

Приведённый в предыдущем разделе алгоритм через непрерывные дроби, как и эквивалентный ему алгоритм Евклида, даёт в результате пару ${\displaystyle (x,y)}$ , удовлетворяющую неравенствам

${\displaystyle |x|<\left|{\frac {b}{d}}\right|;\quad |y|<\left|{\frac {a}{d}}\right|.}$

Этот факт следует из того, что дроби ${\displaystyle {\frac {|y|}{|x|}}}$ и ${\displaystyle {\frac {|a_{1}|}{|b_{1}|}}}$ , как указано выше, образуют последовательные подходящие дроби, а числитель и знаменатель следующей подходящей дроби всегда больше, чем у предыдущей^[10][11]. Для краткости можно назвать такую пару минимальной, таких пар всегда две.

Пример. Пусть ${\displaystyle a=12,b=42}$ . НОД(12, 42) = 6. Ниже приведены некоторые элементы списка пар коэффициентов Безу, причём минимальные пары выделены красным цветом:

${\displaystyle {\begin{alignedat}{3}&\dots \\&12\times &\color {blue}{-10}&{}+42\times &\color {blue}{3}&{}=6\\&12\times &\color {red}{-3}&{}+42\times &\color {red}{1}&{}=6\\&12\times &\color {red}{4}&{}+42\times &\color {red}{-1}&{}=6\\&12\times &\color {blue}{11}&{}+42\times &\color {blue}{-3}&{}=6\\&12\times &\color {blue}{18}&{}+42\times &\color {blue}{-5}&{}=6\\&\dots \end{alignedat}}}$

Решение диофантовых уравнений первой степени

Рассмотрим решение в целых числах диофантовых уравнений вида

${\displaystyle ax+by=c.}$

Обозначим ${\displaystyle d={}}$ НОД${\displaystyle (a,b).}$ Очевидно, уравнение имеет целочисленные решения только в том случае, когда ${\displaystyle c}$ делится на ${\displaystyle d}$ . Будем считать это условие выполненным, и одним из приведённых выше алгоритмов найдём коэффициенты Безу ${\displaystyle x,y}$ :

${\displaystyle ax+by=d.}$

Тогда решением исходного уравнения будет пара^[10] ${\displaystyle c_{1}x,c_{1}y}$ , где ${\displaystyle c_{1}=c/d}$ .

Решение сравнений первой степени

Для решения сравнений первой степени

${\displaystyle ax\equiv b{\pmod {m}}}$

его достаточно преобразовать к виду^[7]

${\displaystyle ax+my=b.}$

Практически важным частным случаем является нахождение обратного элемента в кольце вычетов, то есть решение сравнения

${\displaystyle ax\equiv 1{\pmod {m}}.}$