KNOWED.RU

Пусть a,b-целые числа, n - натуральное. Рассмотрим сравнение:
ax?b (mod n)
и поставим задачу отыскания всех целочисленных решений этого сравнения. Допустим, что xo-это решение.
ax0=b+nu для некоторого целого u.
Пусть d=(a,n)
Видно, что условие d делит b является необходимым для того, чтобы сравнение имело решения.
Как мы увидим позже, это условие является так же достаточным.

Рассмотрим сначала случай, когда d=1 , т.е (a,n)=1. Пусть [b]n - остаток от деления числа b на n.
Тогда [b]n?Zn.
Множество {[ax]n l x?Zn} совпадает с множеством Zn, поскольку является полной системой вычетов.
Поэтому найдется такое xo?Zn, что [axo]n=[b]n. Отсюда,
axo?b(mod n)
Стало быть, сравнение ax?b (mod n) имеет решение xo.
Покажем, что формула x=xo+nt ,t?Z,
позволяет получить любое решение сравнения ax?b (mod n).
В самом деле, если x - решение сравнения, то вычитая из ax?b (mod n) сравнение axo?b (mod n) получим:
a(x-xo)?0 (mod n), тоесть nla(x-xo). Поскольку (n,a)=1, то nl(x-xo) => x=xo+nt . #.

Теперь рассмотрим случай, когда d=(n,a)>1. Пусть a=a1d, b=b1d, n=n1d, причем (a1,n1)=1.
Рассмотрим сравнение a1x?b1 (mod n1). Понятно, что это сравнение равносильно с исходным ax?b (mod n).
Однако, сравнение a1x?b1 (mod n1) мы уже решать умеем. Его множество решений описывается формулой x=xo+n1t, где
xo- решение сравнения a1x?b1 (mod n1), лежащее между 0 и n1-1, а t-произвольное число.

Приведем пример решения сравнений:
17x?55 (mod 37)

Пользуясь алгоритмом Евклида найдем все такие целые числа u и v, что 17u+37v=1. Имеем:
37=17*2+3
17=5*3+2
3=2*1+1

Отсюда:

1=3-1*2=3-1*(17-5*3)=6*3-17=6(37-2)=6-13*7.
Таким образом, 17(-13)?1 (mod 37)

Умножая последнее сравнение на 55 и учитывая, что -13(55)=-715?-12?25 (mod 37), получаем, что 25-xo. => x=25+37t, t принадлежит Z.
Опубликовано на сайте: http://www.knowed.ru
Прямая ссылка: http://www.knowed.ru/index.php?name=pages&op=view&id=97
1111