Сравнения по простому и составному модулю. Решение сравнений

Сравнение с одним неизвестным x имеет вид

Где . Еслиa n не делится на m , то и называется степенью сравнения.

Решением сравнения называется всякое целое число x 0 , для которого

Если х 0 удовлетворяет сравнению, то, согласно свойству 9 сравнений, этому сравнению будут удовлетворять все целые числа, сравнимые с x 0 по модулю m . Поэтому все решения сравнения, принадлежащие одному классу вычетов по модулю т , будем рассматривать как одно решение. Таким образом, сравнение имеет столько решений, сколько элементов полной системы вычетов ему удовлетворяет.

Сравнения, множества решений которых совпадают, называются равносильными.

2.2.1 Сравнения первой степени

Сравнение первой степени с одним неизвестным х имеет вид

(2.2)

Теорема2.4. Для того чтобы сравнение имело хотя бы одно решение, необходимо и достаточно, чтобы число b делилось на НОД(a , m ).

Доказательство. Сначала докажем необходимость. Пусть d = НОД(a , m ) и х 0 - решение сравнения. Тогда, то есть разностьах 0 − b делится на т. Значит, существует такое целое число q , что ах 0 − b = qm . Отсюда b = ах 0 − qm . А поскольку d , как общий делитель, делит числа а и т, то уменьшаемое и вычитаемое делятся на d , а значит и b делится на d .

Теперь докажем достаточность. Пусть d - наибольший общий делитель чисел а и т, и b делится на d . Тогда по определению делимости существуют такие целые числа a 1 , b 1 ,т 1 , что.

Расширенным алгоритмом Евклида найдем линейное представление числа 1 = НОД(a 1 , m 1 ):

для некоторых x 0 , y 0 . Домножим обе части последнего равенства на b 1 d :

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

,

то есть , и- решение сравнения. □

Пример2.10. Сравнение 9х = 6 (mod 12) имеет решение, так как НОД(9, 12) = 3 и 6 делится на 3. □

Пример2.11. Сравнение 6х = 9 (mod 12) не имеет решений, так как НОД(6, 12) = 6, а 9 не делится на 6. □

Теорема 2.5. Пусть сравнение (2.2) разрешимо и d = НОД(a , m ). Тогда множество решений сравнения (2.2) состоит из d классов вычетов по модулю т, а именно, если х 0 - одно из решений, то все другие решения - это

Доказательство. Пусть х 0 - решение сравнения (2.2), то есть и, . Значит, существует такое q , что ах 0 − b = qm . Подставляя теперь в последнее равенство вместо х 0 произвольное решение вида, где, получаем выражение

, делящееся на m . □

Пример 2.12. Сравнение 9х =6 (mod 12) имеет ровно три решения, так как НОД(9, 12)=3. Эти решения: х 0 = 2, х 0 + 4 = 6, х 0 + 2∙4=10.□

Пример2.13. Сравнение 11х =2 (mod 15) имеет единственное решение х 0 = 7,таккакНОД(11,15)=1.□

Покажем, как решать сравнение первой степени. Не умаляя общности, будем считать, что НОД(a , т) = 1. Тогда решение сравнения (2.2) можно искать, например, по алгоритму Евклида. Действительно, используя расширенный алгоритм Евклида, представим число 1 в виде линейной комбинации чисел a и т :

Умножим обе части этого равенства на b , получим: b = abq + mrb , откуда abq - b = - mrb , то есть a ∙ (bq ) = b (mod m ) и bq - решение срав­нения (2.2).

Еще один путь решения - использовать теорему Эйлера. Опять считаем, что НОД(а, т) = 1. Применяем теорему Эйлера: . Умножим обе части сравнения наb : . Переписывая последнее выражение в виде , получаем, что- решение сравнения (2.2).

Пусть теперь НОД(a , m ) = d >1. Тогда a = a t d , m = m t d , где НОД(а 1 , m 1) = 1. Кроме того, необходимо b = b 1 d , для того чтобы сравнение было разрешимо. Если х 0 - решение сравнения а 1 x = b 1 (mod m 1), причем единственное, поскольку НОД(а 1 , m 1) = 1, то х 0 будет решением и сравнения а 1 xd = db 1 (mod m 1), то есть исходного сравнения (2.2). Остальные d - 1 решений находим по теореме 2.5.

Два целых числа а и в сравнимы по модулю натурального числа m є N, если при делении на m они дают одинаковый остаток. .

Теорема (критерий сравнимости): . Следствие 1 : каждое число сравнимо по модулю m со своим остатком от деления на m: . Следствие 2: число сравнимо по модулю m, т. и т. т., к. оно делится на этот mod.

Основные свойства сравнения: 1). Относительные сравнения являются относительно эквивалентными. 2). Сравнения по одному и тому же модулю можно почленно вычитать: . Слагаемое можно переносить из одной части в другую, при этом знак меняем на противоположный. 3). В каждой части сравнения можно прибавлять любое число, кратное модулю: сравнения по одному и тому же модулю можно почленно умножать. Следствия: 1. Обе части сравнения можно возводить в любую натуральную степень. 2. Обе части сравнения можно умножать на любое натуральное число. 4). Обе части сравнения и модуль можно умножить на одно и то же число или сократить на любой их общий делитель. 5). Если сравнение имеет место по нескольким модулям то оно имеет место и по модулю, который равен их наибольшему кратному или наибольшему общему делителю

6). Если сравнение имеет место по модулю m, то оно имеет место и по любому

делителю числа m. 7). Общий делитель одной части сравнения и модуль является делителем другой части сравнения: , .

Малая теорема Ферма: если a и m – взаимнопростые числа, тогда . Функция Эйлера – это число положительных чисел, не превосходящие n и взаимнопростые с n. Если целое число a взаимнопростое с m, то . Теорема Эйлера : если целое число a взаимнопростое с m, то . Теорема Ферма: 1. Если целое число a не делит p, где р – простое, то . 2. Если р – простое и а –любое целое число, тогда . Отношение сравнимости – это классы эквивалентности. Классы эквивалентности также называются классами вычетов, а их эквивалентности называют вычетами.

Решение сравнений: Пусть , , mєN. Тогда называется сравнением к – степени с одним неизвестным и имеет не более, чем m классов решений. Решениями данного сравнения будут являться классы вычетов по модулю m. Сравнения первой степени с одной неизвестной можно записать в виде: если: 1). это сравнение не имеет решения (например 5x ). 2). Если решение этого сравнения. 3). .

Теорема: Пусть , , то , d – класов решений mod m. Методы решения сравнений: 1). Метод испытания полной системы вычетов. 2). Метод преобразования коэффициентов. Прибавляется или вычитается из правой части любое число, кратное модулю, заменяя коэффициенты в левой части на число сравнений с модулем. Можно преобразовать сравнения так, что его можно будет сократить на а и получить решение.

Сравнение чисел по модулю

Подготовила проект: Зутикова Ирина

МАОУ «Лицей №6»

Класс: 10«а»

Научный руководитель: Желтова Ольга Николаевна

Тамбов

2016

• Проблема
• Цель проекта
• Гипотеза
• Задачи проекта и план их достижения
• Сравнения и их свойства
• Примеры задач и их решения
• Используемые сайты и литература

Проблема:

Большинство учеников редко используют сравнение чисел по модулю для решений нестандартных и олимпиадных заданий.

Цель проекта:

Показать, как с помощью сравнения чисел по модулю можно решать нестандартные и олимпиадные задания.

Гипотеза:

Более глубокое изучение темы «Сравнение чисел по модулю» поможет ученикам решать некоторые нестандартные и олимпиадные задания.

Задачи проекта и план их достижения:

1.Подробно изучить тему «Сравнение чисел по модулю».

2.Решить несколько нестандартных и олимпиадных заданий, используя сравнение чисел по модулю.

3.Создать памятку для учеников на тему «Сравнение чисел по модулю».

4.Провести урок по теме «Сравнение чисел по модулю» в 10«а» классе.

5.Дать классу домашнее задание по теме «Сравнение по модулю».

6.Сравнить время выполнения задания до и после изучения темы «Сравнение по модулю».

7.Сделать выводы.

Прежде чем начать подробно изучать тему «Сравнение чисел по модулю», я решила сравнить, как она представлена в различных учебниках.

• Алгебра и начала математического анализа. Углубленный уровень. 10 класс (Ю.М.Колягин и др.)
• Математика: алгебра, функции, анализ данных. 7 класс (Л.Г.Петерсон и др.)
• Алгебра и начала математического анализа. Профильный уровень. 10 класс (Е.П.Нелин и др.)
• Алгебра и начала математического анализа. Профильный уровень. 10 класс (Г.К.Муравин и др.)

Как я выяснила, в некоторых учебниках эта тема даже не затрагивается, не смотря на углубленный уровень. А наиболее понятно и доступно тема представлена в учебнике Л.Г.Петерсона (Глава: Введение в теорию делимости), поэтому попробуем разобраться в «Сравнении чисел по модулю», опираясь на теорию из этого учебника.

Сравнения и их свойства.

Определение: Если два целых числа a и b имеют одинаковые остатки при делении на некоторое целое число m (m>0), то говорят, что a и b сравнимы по модулю m , и пишут:

Теорема: тогда и только тогда, когда разность aи bделится на m.

Свойства:

1. Рефлексивность сравнений. Любое число aсравнимо само с собой по модулю m (m>0; a,m-целые числа).
2. Симметричность сравнений. Если число a сравнимо с числом b по модулю m, то число b сравнимо с числом a по тому же модулю(m>0; a,b,m-целые числа).
3. Транзитивность сравнений. Если число a сравнимо с числом b по модулю m, а число b сравнимо с числом cпо тому же модулю, то число a сравнимо с числом c по модулю m(m>0; a,b,c,m-целые числа).
4. Если число a сравнимо с числом b по модулю m, то число a n сравнимо счислом b n по модулю m(m>0; a,b,m-целые числа;n-натуральное число).

Примеры задач и их решения.

1.Найти последнюю цифру числа 3 999 .

Решение:

Т.к. последняя цифра числа - это остаток от деления на 10, то

3 999 =3 3 *3 996 =3 3 *(3 4 ) 249 =7*81 249 7(mod 10)

(Т.к. 34=81 1(mod 10);81 n 1(mod10) (по свойству))

Ответ:7.

2.Доказать,что 2 4n -1 делится на 15 без остатка. (Физтех2012)

Решение:

Т.к. 16 1(mod 15), то

16 n -1 0(mod 15) (по свойству); 16n= (2 4 ) n

2 4n -1 0(mod 15)

3.Доказать, что 12 2n+1 +11 n+2 делится без остатка на 133.

Решение:

12 2n+1 =12*144 n 12*11 n (mod 133) (по свойству)

12 2n+1 +11 n+2 =12*11 n +11 n *121=11 n *(12+121) =11 n *133

Число (11 n *133)без остатка делится на 133. Следовательно,(12 2n+1 +11 n+2 )делится без остатка на 133.

4.Найти остаток от деления на 15 числа 2 2015 .

Решение:

Т.к.16 1(mod 15), то

2 2015 8(mod 15)

Ответ:8.

5.Найти остаток от деления на 17 числа 2 2015 . (Физтех2015)

Решение:

2 2015 =2 3 *2 2012 =8*16 503

Т.к.16 -1(mod 17), то

2 2015 -8(mod 15)

8 9(mod 17)

Ответ:9.

6.Доказать, что число 11 100 -1 делится на 100 без остатка. (Физтех2015)

Решение:

11 100 =121 50

121 50 21 50 (mod 100) (по свойству)

21 50 =441 25

441 25 41 25 (mod 100) (по свойству)

41 25 =41*1681 12

1681 12 (-19) 12 (mod 100) (по свойству)

41*(-19) 12 =41*361 6

361 6 (-39) 6 (mod 100)(по свойству)

41*(-39) 6 =41*1521 3

1521 3 21 3 (mod100) (по свойству)

41*21 3 =41*21*441

441 41(mod 100) (по свойству)

21*41 2 =21*1681

1681 -19(mod 100) (по свойству)

21*(-19)=-399

399 1(mod 100) (по свойству)

Значит 11 100 1(mod 100)

11 100 -1 0(mod 100) (по свойству)

7.Даны три числа: 1771,1935,2222. Найти число, при делении на которое остатки трёх данных чисел будут равны. (ВШЭ2016)

Решение:

Пусть неизвестное нам число будет равно а,тогда

2222 1935(mod a); 1935 1771(mod a); 2222 1771(mod a)

2222-1935 0(moda) (посвойству); 1935-1771 0(moda) (по свойству); 2222-1771 0(moda) (по свойству)

287 0(mod a); 164 0(mod a); 451 0(mod a)

287-164 0(moda) (по свойству); 451-287 0(moda)(по свойству)

123 0(mod a); 164 0(mod a)

164-123 0(mod a) (посвойству)

41

Олимпиада ВШЭ2016

Рассмотрим сравнения первой степени вида

ax ≡ b(mod m),

Как решать такое сравнение? Рассмотрим два случая.

Случай 1. Пусть а и m взаимно просты. Тогда несократимая дробь m/a сама просится разложиться в цепную дробь:

Эта цепная дробь, разумеется, конечна, так как m/a - рациональное число. Рассмотрим две ее последние подходящие дроби:

Вспоминаем важное свойство числителей и знаменателей подходящих дробей: mQ n-1 -aP n-1 =(-1) n . Далее (слагаемое mQ n-1 , кратное m , можно выкинуть из левой части

сравнения):

-aP n-1 ≡ (-1) n (mod m) т.е.

aP n-1 ≡ (-1) n-1 (mod m) т.е.

a[(-1) n-1 P n-1 b] ≡ b(mod m)

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

x ≡ (-1) n-1 P n-1 b(mod m)

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

Решение. (111, 322)=1. Включаем алгоритм Евклида:

322=111 · 2+100

(В равенствах подчеркнуты неполные частные.) Значит, n=4 , а соответствующая цепная

дробь такова:

Посчитаем числители подходящих дробей, составив для этого стандартную таблицу:

Числитель предпоследней подходящей дроби равен 29, следовательно, готовая формула

дает ответ: x ≡ (-1) 3 ⋅ 29 ⋅ 75 ≡ -2175 ≡ 79(mod 322)

Случай 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 .

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

Имеем 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) .

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

ϕ (10)=4; x ≡ 3 ⋅ 7 4-1 (mod 10) ≡ 1029(mod 10) ≡ 9(mod 10) .

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

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

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

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

Лемма 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) .

Пример. Однажды средний товарищ подошел к умному товарищу и попросил его найти число, которое при делении на 4 дает в остатке 1, при делении на 5 дает в остатке 3, а при делении на 7 дает в остатке 2. Сам средний товарищ искал такое число уже две недели. Умный товарищ тут же составил систему:

которую начал решать, пользуясь леммой 1. Вот его решение:

b 1 =1 ; b 2 =3 ; b 3 =2 ; m 1 m 2 m 3 , т.е. M 1 =35, M 2 =28, M 3 =20 .

т.е. M 1 ∇ =3, M 2 ∇ =2, M 3 ∇ =6. Значит x 0 =35 ⋅ 3 ⋅ 1+28 ⋅ 2 ⋅ 3+20 ⋅ 6 ⋅ 2=513. После этого, по лемме 1, умный товарищ сразу получил ответ:

x ≡ 513(mod 140) ≡ 93(mod 140),

т.е. наименьшее положительное число, которое две недели искал средний товарищ, равно 93. Так умный товарищ в очередной раз помог среднему товарищу.

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

Рассмотрим систему сравнений

Где f1(x), f2(x), …. , fs(x)€Z[x].

Теорема 1. Пусть M = - наименьшее общее кратное чисел m1,m2,…,ms . Если а удовлетворяет системе (2), то и любое число из класса а по модулю М удовлетворяет этой системе.

Доказательство. Пусть b€ классу а. Так как а ≡ b(mod M), то а ≡b(mod m), i= 1,2,...,s (свойство сравнений 16). Следовательно, b, как и а, удовлетворяет каждому сравнению системы, что и доказывает теорему. Поэтому естественно считать решением системы (2) класс по модулю М.

Определение. Решением системы сравнений (2) называется класс чисел по модулю М = , удовлетворяющих каждому сравнению системы.

12. Сразу заметим, что нечётные числа не удовлетворяют второму сравнению. Взяв чётные числа из полной системы вычетов по модулю 12, непосредственной проверкой убеждаемся, что 2-му сравнению удовлетворяют числа 2, -2, 6, а система имеет два решения: х ≡ 2(mod l2), х ≡ -2(mod 12).

Рассмотрим систему сравнений 1-ой степени (3)

Теорема2. Пусть d=(m1,m2), М = .

Если с1 - с2 не делится на d, то система (3) не имеет решений.

Если (c1 -c2):d, то система (3) имеет одно решение - класс по модулю М.

Доказательство. Из 1-го сравнения x = c1+m1t, t€Z. Подставляем во 2-е сравнение: с1+ m1t ≡ c2(mod m2) или

m1t ≡ c2-cl (mod m2). Это сравнение имеет решение только если (с2 – с1): d.

И решение представляет собой класс по модулю (теорема 4 из §2).

Пусть решение , то есть , где k€Z.

M== , то есть x≡c1+m1t0(mod M) - решение

Примеры.

1. :2, система имеет одно решение класс по модулю 24. Из 1-го сравнения х =2+6t. Подставив вместо х во 2-е сравнение, имеем: 2 + 6t≡ 4(tnod 8); 6t≡ 2(mod 8); -2t≡2(mod8); t≡-1(mod 4); t=-1+4k; x=2+6(-1+4k); x=-4+24k, то есть x≡-4(mod 24).

2. 7-3 не делится на 3, система не имеет решений.

Следствие 1. Система сравнений (4)

Либо не имеет решений, либо имеет одно решение – класс по модулю M=.

Доказательство. Если система первых двух сравнений не имеет решений, то и (4) ие имеет решений. Если она имеет решение х ≡ a(mod), то, добавив к этому сравнению третье сравнение системы, получим снова систему вида (3), которая либо имеет одно решение, либо не имеет решений. Если имеет решение, то будем так продолжить, пока не исчерпаем все сравнения системы (4). Если решение есть, то это класс по модулю М.

Замечание. Здесь использовано свойство НОК: =.

Следствие 2 . Если m1,m2,…,ms попарно взаимно простые, то система (4) имеет одно решение - класс по модулю M=m1m2…ms.

Пример:

Так как модули попарно взаимно простые, система имеет одно решение - класс по модулю 105 = 5*3*7. Из первого сравнения

Подставляем во второе сравнение: 2 +5t≡ 0(mod 3) или 2t≡-2(mod3), t=-1+3k, x=2+5(-1+3k), x=-3+15k. Подставим в третье сравнение:

3+15k≡5(mod7), 15k≡8(mod 7), k=1+7l. тогда x=-3+15(1+7l); x=12+105l; x≡12(mod 105).

Познакомимся с другим способом решения этой системы, (Используем то, что система имеет одно решение.) Умножим обе части и модуль первого сравнения на 21, второго-на 35б третьего – на 15: из суммы первого и третьего вычтем второе:

(36 -35)х ≡ 75 + 42(modl05); x≡117(mod105); x≡12(mod105).

Рассмотрим теперь систему сравнений первой степени общего вида

Если некоторое сравнение этой системы не имеет решений, то и система не имеет решений. Если же каждое сравнение системы (5) разрешимо, то решим его относительно х и получим равносильную систему вида (4):

Где (теорема 4, §2).

По следствию 1 система либо не имеет решений, либо имеет одно решение.

Пример:

Решив каждое сравнение системы, получим равносильную систему

Эта система имеет одно решение - класс по модулю 105. Умножив первое сравнение и модуль на 3, а второе на 35, получим

Вычитая из второго сравнения первое, умноженное на 11, получаем 2х ≡-62(modl05), откуда х ≡ -31(modl05).

Задачи, сводящиеся к рассмотрению системы сравнений 1-ой степени, рассматривались в арифметике китайского математика Сун Тзу, жившего примерно в начале нашей эры. У него вопрос ставился в следующей форме- найти число, дающее заданные остатки при делении на заданные числа. Он даёт и способ решения, эквивалентный следующей теореме.

Теорема (китайская теорема об остатках). Пусть m1,m2,…,ms- попарно взаимно простые числа, М = mlm2...ms, β1, β2,…, βs подобраны так, что

Тогда решение системы

Будет иметь вид x≡x0(mod M).

Доказательство. Поскольку получим x0≡

Аналогичным образом проверяем, что x0≡c2(mod m2),…, x0≡cs(mod ms), то есть x0 удовлетворяет всем

сравнениям системы.

10. Сравнения 1-й степени. Неопределённые уравнения

§ 2. Сравнения 1-й степени. Неопределённые уравнения

Сравнение 1-ой степени может быть приведено к виду ax≡b(mod m).

Теорема 4. Если (a,m) = 1, то сравнение ах ≡b(mod m) (2) имеет единственное решение.

Доказательство. Возьмём 0,1,2,...,m-1 - полную систему вычетов по модулю m. Так как (а,m) = 1, то 0,а,2а,...,(m-1)а - тоже полная система вычетов (теорема 3, §2, гл 2.). В ней найдётся одно и только одно число, сравнимое с b по модулю m (принадлежащее тому же классу, что и b). Пусть это ах 0 , то есть ax 0 € классу b или ax 0 ≡b(mod m). x ≡x 0 (mod m) - единственное решение (2). Теорема доказана.

Теорема 5. Если (а, m)= 1, то решением сравнения ах≡b(mod m) является класс х 0 ≡a φ (m)-1 b(mod m).

Доказательство. Так как (a,m) = 1, то по т. Эйлерa а φ(m) ≡1(mod m). Легко видно, что x 0 ≡a φ (m)-1 b (mod m)- решение сравнения (2). Действительно,a(a φ (m)-1 b)≡a φ (m) b≡b(mod m). Из теоремы 4 следует, что это решение единственное.

Рассмотрим методы решений сравнения ах ≡b(mod m).

1. Метод подбора. Взяв полную систему вычетов по модулю m, выбираем числа, удовлетворяющие сравнению.

2. Использование теоремы Эйлера (теорема 5).

3. Метод преобразования коэффициентов. Надо попытаться преобразовать коэффициенты так, чтобы правую часть можно было бы разделить на коэффициент при х. Преобразования, о которых идёт речь, следующие: замена коэффициентов абсолютно наименьшими вычетами, замена числа b сравнимым по модулю числом (прибавлением числа, кратного модулю) с тем, чтобы последнее делилось на а, переход от а и b к другим, сравнимым с ними числам, у которых оказался бы общий делитель и т.п. При этом пользуемся свойствами сравнений и основанными на них теоремами о равносильных сравнениях.

1) 223x ≡ 115(mod ll).

Сначала заменим коэффициенты наименьшими по абсолютной величине вычетами: Зх ≡ 5(mod 11). Если воспользоваться теоремой

Эйлера, то

х≡3 φ(11)-1 *5=3 9 *5≡(3 3) 3 *5≡(27) 3 *5≡5 3 *5≡125*5≡4*5≡9(modll).

Однако проще преобразовать коэффициенты. Заменим сравнение равносильным, прибавив к правой части число, кратное модулю:

3x ≡ 5 + 22(mod 11). Разделив обе части на число 3, взаимно простое с модулем, получим х ≡ 9(mod l1).

2) 111x≡ 8(mod 34).

Используем метод преобразования коэффициентов.

(111-3*34)x≡8(mod 34), 9x≡8+34≡42(mod 34), 3x≡14(mod 34), 3x≡14+34≡48(mod 34), x≡16(mod 34).

Теорема 6. Если (a, m) = d и b не делится на d, то сравнение (1) не имеет решений.

Доказательство (от противного). Пусть класс x 0 - решение, то есть ax 0 ≡b (mod m) или (ax 0 -b):m, а, следовательно, (ax 0 -b):d. Но a:d, тогда иb:d - противоречие. Следовательно, сравнение не имеет решений.

Теорема 7. Если (a,m)= d, d>1, b:d, то сравнение(1) имеет d

решений, которые составляют один класс вычетов по модулю и находится по формулам

Где с удовлетворяет вспомогательному сравнению

Замечание. Согласно теореме сравнение (1) решается следующим образом.

1) Убедившись, что (a,m) = d, d> 1 и b:d, делим обе части в сравнения (2) на d и получаем вспомогательное сравнение a 1 x≡b 1 (mod m 1) , где . Сравнение имеет единственное решение. Пусть класс с – это решение.

2) Записываем ответ x 0 ≡c(mod m), x 1 ≡c+m 1 (mod m), x 2 ≡c+2m 1 (mod m), … , x d -1 ≡c+(d-1)m 1 (mod m).

Доказательство. Вспомогательное сравнение по теореме 2(3) равносильно исходному сравнению (2). Так как ( 1, То вспомогательное сравнение имеет единственное решение – класс по модулю m 1 = . Пусть x≡c(mod m 1) – это решение. Класс чисел с по модулю m 1 распадается на d классов по модулю m: .

Действительно, любое число из класса х0 по модулю m 1 имеет вид x 0 +m 1 t. Разделим t с остатком на d: t = dq +r, где 0≤r

Итак, сравнение (1) имеет d решений по модулю m: х0 , x0+m1,..., х0 +(d-1)m1.(сверху черточки горизонтальные)

Примеры.

1) 20x≡ 15(mod 108). Так как (20,108) = 4 и 15 не делится на 4, то решений нет.

2) 20x≡ 44(mod 108). (20,108) = 4 и 44:4, следовательно, сравнение имеет четыре решения. Разделив обе части и модуль на 4,получим:

5х≡11(mod 27); 5 x≡11-81 ≡ -70(mod27), х ≡ -14 ≡ 13(mod 27). Тогда х≡13 + 27r(mod 108), где г= 0,1,2,3. I jj

Ответ: x≡13(modl08); х ≡ 40(modl08); х ≡ 67(modl08); x≡94(modl08).

Применение теории сравнений к решению неопределённых уравнении

Рассмотрим неопределённое или, как его иначе называют, Диофантово уравнение первой степени с двумя неизвестными ах + by = с, где a,b,c€Z. Требуется решить это уравнение в целых числах. Если (a,b)=d и с не делится на d, то очевидно, чТО сравнение не имеет решений в целых числах. Если же с делится на d, ТО поделим обе части уравнения на d. Поэтому достаточно рассмотреть случай, когда (а, b) =1.

Так как ах отличается от с на число, кратное b, то ах ≡ c(mod b) (без ограничения общности можно считать, что b > 0). Решая это сравнение, получим х ≡x1 (mod b) или x=x1+bt, где t€Z. Для определения Соответствующих значений у имеем уравнение а(х1 + bt) + by = с, откуда

Причём -целое число, оно является частным значением неизвестного y, соответствующим x1(получается, как и x1, при t=0). А общее решение уравнения примет вид систему уравнений x=x1+bt, y=y1-at, где t- любое целое число.

Заметим , что 1) уравнение ах + by = с можно было решать, начав со сравнения by ≡ c(mod а), так как by отличается от с на число, кратное а;

2)в качестве модуля удобнее выбирать наименьший из модулей а и b.

Пример , 50x – 42y= 34.

Разделим обе части уравнения на 2.

25х ≡ 17(mod2l); 4х ≡ 17 (mod 21) или 4х ≡ 17-21 ≡ -4(mod21).

х ≡ -1 (mod 21), то есть x=-1+21t, t€Z. Подставим найденное х в уравнение. 25(-1 + 21t)- 21y= 17; 21у =-42 + 25* 21t и у =-2 + 25t.