Теория остатков

Случай 2. Пусть (a,m)=d . В этом случае, для разрешимости сравнения ax b(mod m) необходимо, чтобы d делило b , иначе сравнение вообще выполняться не может. Действительно, ax b(mod m) бывает тогда, и только тогда, когда ax- b делится на m нацело, т.е. ax- b=t · m ,

t Z , откуда b=ax- t m , а правая часть последнего

равенства кратна d .

Пусть b=db 1 , a=da 1 , m=dm 1 . Тогда обе части сравнения xa 1 d b 1 d(mod m 1 d) и его модуль поделим на d :

xa 1 b 1 (mod m 1 ) ,

где уже а 1 и m 1 взаимно просты. Согласно случаю 1 этого пункта, такое сравнение имеет единственное решение x 0 :

x x 0 (mod m 1 ) (*)

По исходному модулю m , числа (*) образуют столько решений исходного сравнения, сколько чисел вида (*) содержится в полной системе вычетов: 0,1,2, ., m-2, m-1 . Очевидно, что из чисел x=x 0 +t m в полную систему наименьших неотрицательных вычетов попадают только x 0 , x 0 +m 1 , x 0 +2m 1 , ., x 0 +(d-1)m 1 , т.е. всего d чисел. Значит у исходного сравнения имеется d решений.

Подведем итог рассмотренных случаев в виде следующей теоремы

Теорема 1. Пусть (a,m)=d . Если b не делится на d , сравнение ax b(mod m) не имеет решений. Если b кратно d , сравнение ax b(mod m) имеет d штук решений.

Пример. Решить сравнение 111x 75(mod 321) .

Решение. (111,321)=3 , поэтому поделим сравнение и его модуль на 3:

37x 25(mod 107) и уже (37,107)=1 .

Включаем алгоритм Евклида (как обычно, подчеркнуты неполные частные):

107=37 2+33

37=33 1+4

33=4 8+1

4=1 4

Имеем n=4 и цепная дробь такова:

Таблица для нахождения числителей подходящих дробей:

Значит, x (-1) 3 26 25 -650(mod 107) -8(mod 107) 99(mod 107) .

Три решения исходного сравнения:

x 99(mod 321), x 206(mod 321), x 313(mod 321) ,

и других решений нет.

Теорема 2. Пусть m>1, (a,m)=1 Тогда сравнение ax b(mod m) имеет решение: x ba (m)-1 (mod m) .

Доказательство. По теореме Эйлера, имеем: a (m) 1(mod m) , следовательно, a ba (m)-1 b(mod m) .

Пример. Решить сравнение 7x 3(mod 10) . Вычисляем:

(10)=4; x 3 7 4-1 (mod 10) 1029(mod 10) 9(mod 10) .

Видно, что этот способ решения сравнений хорош (в смысле минимума интеллектуальных затрат на его осуществление), но может потребовать возведения числа а в довольно большую степень, что довольно трудоемко. Для того, чтобы как следует это прочувствовать, возведите самостоятельно число 24789 в степень 46728.

Теорема 3. Пусть р – простое число, 0<a<p . Тогда сравнение ax b(mod p) имеет решение:

где C a p – биномиальный коэффициент.

Доказательство непосредственно следует из очевидного сравнения

которое нужно почленно поделить на взаимно простое с модулем число 1 2 3  . a-1 .

Пример. Решить сравнение 7x 2(mod 11) . Вычисляем:

На этом пункт 19 можно было бы и закончить, но невозможно, говоря о решении сравнений первой степени, обойти стороной вопрос о решении систем сравнений первой степени. Дело в том, что умение решать простейшие системы сравнений не только является неотъемлемой частью общечеловеческой культуры, позволяющей гражданину не падать в ямы, расщелины и открытые люки. Такое умение, кроме всего прочего, пригодится нам при изучении сравнений произвольной степени, о которых пойдет речь в следующих пунктах.

Лемма 1 (Китайская теорема об остатках). Пусть дана простейшая система сравнений первой степени:

где m 1 ,m 2 , .,m k попарно взаимно просты. Пусть, далее, m 1 m 2 .m k =M s m s ; M s M s 1(mod m s ) (Очевидно, что такое число M s всегда можно подобрать хотя бы с помощью алгоритма Евклида, т.к. (m s ,M s )=1 ); x 0 =M 1 M 1 b 1 +M 2 M 2 b 2 + .+M k M k b k . Тогда система (*) равносильна одному сравнению

x x 0 (mod m 1 m 2 .m k ) ,

т.е. набор решений (*) совпадает с набором решений сравнения x x 0 (mod m 1 m 2 .m k ) .

Доказательство. Имеем: m s делит M j , при s j. Следовательно, x 0 M s M s b s (mod m s ) , откуда x 0 b s (mod m s ) . Это означает, что система (*) равносильна системе

которая, очевидно, в свою очередь, равносильна одному сравнению x x 0 (mod m 1 m 2 .m k ) .

В следующей лемме, для краткости формулировки, сохранены обозначения леммы 1.

Лемма 2. Если b 1 ,b 2 , .,b k пробегают полные системы вычетов по модулям m 1 ,m 2 , .,m k соответственно, то x 0 пробегает полную систему вычетов по модулю m 1 m 2 .m k .

Доказательство. Действительно, x 0 =A 1 b 1 +A 2 b 2 + .+A k b k пробегает m 1 m 2 .m k различных значений. Покажем, что все они попарно не сравнимы по модулю m 1 m 2 .m k .

Ну пусть оказалось, что

A 1 b 1 +A 2 b 2 + .+A k b k A 1 b' 1 +A 2 b' 2 + .+A k b' k (mod m 1 m 2 .m k )

Значит,

A 1 b 1 +A 2 b 2 + .+A k b k A 1 b' 1 +A 2 b' 2 + .+A k b' k (mod m s )

для каждого s , откуда

M s M s b s M s M s b' s

Вспомним теперь, что M s M s 1(mod m s ) , значит M s M s 1+m s t , откуда (M s M s ,m s )=1 . Разделив теперь обе части сравнения

 Скачать реферат