Квадратичные сравнения по составному модулю. Решение сравнений и их приложения Решение линейных сравнений по модулю

20.08.2023

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

f (x ) 0 (mod m ); f (х ) = ах + а n . (1)

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

Если сравнению (1) удовлетворяет какое-либо x = x 1, то (согласно 49) тому же сравнению будут удовлетворять и все числа, сравнимые с x 1 , по модулю m : x x 1 (mod m ). Весь этот класс чисел считается за одно решение . При таком соглашении можно сделать следующий вывод.

66.Сравнение (1) будет иметь столько решений, сколько вычетов полной системы ему удовлетворяет .

Пример. Сравнению

6x – 4 0 (mod 8)

среди чисел 0, 1,2, 3, 4, 5, 6, 7 полной системы вычетов по модулю 8 удовлетворяют два числа: х = 2 и х = 6. Поэтому указанное сравнение имеет два решения:

x 2 (mod 8), х 6 (mod 8).

Сравнение первой степени перенесением свободного члена (с обратным знаком) в правую часть можно привести к виду

ax b (mod m ). (2)

Рассмотрим сравнение, удовлетворяющее условию (а , m ) = 1.

Согласно 66 наше сравнение имеет столько решений, сколько вычетов полной системы ему удовлетворяет. Но когда x пробегает полную систему вычетов по модулю т, то ах пробегает полную систему вычетов (из 60). Следовательно, при одном и только одном значении х, взятом из полной системы, ах будет сравнимо с b. Итак,

67. При (а, m) = 1 сравнение ax b (mod m ) имеет одно решение.

Пусть теперь (a , m ) = d > 1. Тогда, чтобы сравнение (2) имело решения, необходимо (из 55), чтобы b делилось на d, иначе сравнение (2) невозможно ни при каком целом х. Предполагая, поэтому b кратным d, положим a = a 1 d , b = b 1 d , m = m 1 d. Тогда сравнение (2) будет равносильно такому (по сокращении на d ): a 1 x b 1 (mod m ), в котором уже (а 1 , m 1) = 1, и потому оно будет иметь одно решение по модулю m 1 . Пусть х 1 – наименьший неотрицательный вычет этого решения по модулю m 1, тогда все числа х, образующие это решение, найдутся в виде

x x 1 (mod m 1). (3)

По модулю же mчисла (3) образуют не одно решение, а больше, именно столько решений, сколько чисел (3) найдется в ряде 0, 1, 2, ..., m – 1 наименьших неотрицательных вычетов по модулю m. Но сюда попадут следующие числа (3):

x 1 , x 1 + m 1 , x 1 + 2m 1 , ..., x 1 + (d – 1) m 1 ,

т.е. всего d чисел (3); следовательно, сравнение (2) имеет d решений.

Получаем теорему:

68. Пусть (a, m) = d. Сравнение ax b (mod m) невозможно, если b не делится на d. При b, кратном d, сравнение имеет d решений..

69.Способ решения сравнения первой степени, основанный на теории непрерывных дробей:

Разлагая в непрерывную дробь отношение m:а ,

и рассматривая две последние подходящие дроби:

согласно свойствам непрерывных дробей (согласно 30 ) имеем

Итак, сравнение имеет решение

для разыскания, которого достаточно вычислить P n – 1 согласно способу, указанному в 30.

Пример. Решим сравнение

111x = 75 (mod 321). (4)

Здесь (111, 321) = 3, причем 75 кратно 3. Поэтому сравнение имеет три решения.

Деля обе части сравнения и модуль на 3, получим сравнение

37x = 25 (mod 107), (5)

которое нам следует сначала решить. Имеем

q
P 3

Значит, в данном случае n = 4, P n – 1 = 26, b = 25, и мы имеем решение сравнения (5) в виде

x –26 ∙ 25 99 (mod 107).

Отсюда решения сравнения (4) представляются так:

х 99; 99 + 107; 99 + 2 ∙ 107 (mod 321),

х º99; 206; 313 (mod 321).

Вычисление обратного элемента по заданному модулю

70.Если целые числа a и n взаимно просты, то существует число a′ , удовлетворяющее сравнению a ∙ a′ ≡ 1(mod n ). Число a′ называется мультипликативным обратным к a по модулю n и для него используется обозначение a - 1 (mod n ).

Вычисление обратных величин по некоторому модулю может быть выполнено решением сравнения первой степени с одним неизвестным, в котором за x принимается число a′ .

Чтобы найти решение сравнения

a ∙x ≡ 1(mod m ),

где (a,m )= 1,

можно воспользоваться алгоритмом Евклида (69) или теоремой Ферма-Эйлера, которая утверждает, что если (a,m ) = 1, то

a φ( m ) ≡ 1(mod m ).

x ≡ a φ( m )–1 (mod m ).

Группы и их свойства

Группы – один из таксономических классов, используемых при классификации математических структур с общими характерными свойствами. Группы имеют две составляющие: множество (G ) и операции (), определенные на этом множестве.

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

Для двух множеств A, B записи B A , B A , B ∩ A , B A , B \ A , A × B означают соответственно, что B является подмножеством множества A (т.е. любой элемент из B содержится также и в A , например, множество натуральных чисел содержится в множестве действительных чисел; кроме того, всегда A A ), B является собственным подмножеством множества A (т.е. B A и B ≠ A ), пересечение множеств B и A (т.е. все такие элементы, которые лежат одновременно и в A , и в B , например пересечение целых чисел и положительных действительных чисел есть множество натуральных чисел), объединение множеств B и A (т.е. множество, состоящее из элементов, которые лежат либо в A , либо в B ), разность множеств B и A (т.е. множество элементов, которые лежат в B , но не лежат в A ), декартово произведение множеств A и B (т.е. множество пар вида (a , b ), где a A , b B ). Через |A | всегда обозначается мощность множества A , т.е. количество элементов в множестве A .

Операция – это правило, согласно которому любым двум элементам множества G (a и b ) ставится в соответствие третий элемент из G: а b.

Множество элементов G с операцией называется группой , если удовлетворяются следующие условия.

Проект по математике по теме

«Сравнения по модулю»

Зарипова Айсылу

Советский район города Казани

МБОУ «СОШ №166», 7а класс

Научный руководитель: Антонова Н.А.

Оглавление

Введение____________________________________________________3

Что такое сравнения________________________________________4

Применение сравнений к решению задач______________________6

Простейшим применением сравнений по модулю является определение делимости чисел___________________________6
Одна задача на сравнения_______________________________8
Применение сравнений по модулю в профессиональной деятельности_________________________________________9

Заключение__________________________________________________10

Список использованной литературы_____________________________11

Введение.

Тема работы: Сравнения по модулю.

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

Цель: Выяснить суть сравнений по модулю, основные методы работы со сравнениями по модулю.

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

Объект исследования: теория чисел.

Предмет исследования: теория сравнений по модулю.

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

I . Что такое сравнения.

Числа и называются сравнимыми по модулю, если делится на, другими словами а и в имеют одинаковые остатки при делении на .

Обозначение

Примеры:

12 и 32 сравнимы по модулю 5, так как 12 при делении на 5 имеет остаток 2 и 32 при делении на 2 имеет остаток 2. Записывается 12 ;

101 и 17 сравнимы по модулю 21;

В значительной степени теория делимости была создана Эйлером. Определение сравнения было сформулировано в книге К.Ф.Гаусса «Арифметические исследования». Эту работу, написанную на латинском языке, начали печатать в 1797 году, но книга вышла в свет лишь в 1801 году из-за того, что процесс книгопечатания в то время был чрезвычайно трудоемким и длительным. Первый раздел книги Гаусса так и называется: «О сравнении чисел». Именно Гаусс предложил утвердившуюся в математике символику сравнений по модулю.

Если

Доказательство:

Если к первому равенству прибавить второе, то получиться

это сумма двух целых чисел, значит, является целым числом, следовательно.

Если из первого равенства вычесть второе, то получиться

это разность двух целых чисел, значит, является целым числом, следовательно.

Рассмотрим выражение:

это разность произведений целых чисел, значит, является целым числом, следовательно.

Это следствие третьего свойства сравнений.

Что и требовалось доказать.

5) Если .

Доказательство: Найдем сумму двух этих выражений:

это сумма двух целых чисел, значит, является целым числом, следовательно, .

Что и требовалось доказать.

6) Если – целое число, то

Доказательство: , где p – целое число, умножим это равенство на, получим: . Так как – произведение целых чисел, то Что и требовалось доказать.

7) Если

Доказательство: рассуждения аналогичны доказательству свойства 6.

8) Если - взаимно простые числа, то

Доказательство: , поделим это выражение на, получим: - взаимно простые числа, значит, делится на нацело, т.е. =. А это значит, что Что и требовалось доказать.

II . Применение сравнений к решению задач.

2.1. Простейшим применением сравнений по модулю является определение делимости чисел.

Пример. Найдите остаток от деления 2 2009 на 7.

Решение: Рассмотрим степени числа 2:

возводя сравнение в степень 668 и умножая на, получаем: .

Ответ: 4.

Пример. Докажите, что 7+7 2 +7 3 +…+7 4 n делится на 100 при любом n из множества целых чисел.

Решение: Рассмотрим сравнения

и т.д. Цикличность остатков объясняется правилами умножения чисел столбиком. Складывая первые четыре сравнения, получаем:

Значит, эта сумма делится на 100 без остатка. Аналогично, складывая следующие сравнения про четыре, получим, что каждая такая сумма делится на 100 без остатка. Значит, вся сумма, состоящая из 4 n слагаемых, делится на 100 без остатка. Что и требовалось доказать.

Пример. Определите, при каком значении n выражение делится на 19 без остатка.

Решение: .

Умножим это сравнение на 20. Получим.

Сложим сравнения, тогда. . Таким образом, правая часть сравнения делится на 19 всегда при любом натуральном n , а, значит, исходное выражение делится на 19 при натуральном n .

Ответ n – любое натуральное число.

Пример. Какой цифрой оканчивается число.

Решение. Для решения этой задачи будем следить только за последней цифрой. Рассмотрим степени числа 14:

Можно заметить, что при нечетном показателе значение степени оканчивается на 4, а при четном – на 6. Тогда оканчивается на 6, т.е. является четным числом. Значит, будет оканчиваться на 6.

Ответ 6.

2.2. Одна задача на сравнения.

В статье Н. Виленкина «Сравнения и классы вычетов» приводится задача, которую решил знаменитый английский физик Дирак в студенческие годы.

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

Один прохожий обнаружил кучу яблок около дерева, на котором сидела мартышка. Пересчитав их, он понял, что если 1 яблоко отдать мартышке, то число оставшихся яблок разделится на n без остатка. Отдав лишнее яблоко мартышке, он взял себе 1/ n оставшихся яблок и ушел. К куче позднее подошел следующий прохожий, затем следующий и т.д. Каждый следующий прохожий, пересчитав яблоки, замечал, что их число при делении на n дает остаток 1 и, отдав мартышке лишнее яблоко, он забирал себе 1/ n оставшихся яблок и шел дальше. После того как ушел последний, n -й прохожий, число яблок, оставшихся в куче, делилось на n без остатка. Сколько яблок было в куче сначала?

Проведя те же рассуждения, что и Дирак мы получили общую формулу для решения класса подобных задач: , где n – натуральное число.

2.3. Применение сравнений по модулю в профессиональной деятельности.

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

Заключение.

В работе изложены основные понятия и свойства сравнений по модулю, на примерах проиллюстрировано применение сравнений по модулю. Материал может быть использован при подготовке к олимпиадам по математике и ЕГЭ.

Приведенный список литературы позволяет при необходимости рассмотреть некоторые более сложные моменты теории сравнений по модулю и ее применения.

Список использованной литературы.

Алфутова Н.Б. Алгебра и теория чисел./Н.Б.Алфутова, А.В.Устинов. М.:МЦНМО, 2002, 466 с.

Бухштаб А.А. Теория чисел. /А.А.Бухштаб. М.: Просвещение, 1960.

Виленкин Н. Сравнения и классы вычетов./Н.Виленкин.//Квант. – 1978.- 10.

Федорова Н.Е. Изучение алгебры и математического анализа. 10 класс. http :// www . prosv . ru / ebooks / Fedorova _ Algebra _10 kl /1/ xht

ru . wikipedia . org / wiki /Сравнение_по_модулю.

Рассмотрим сравнение вида x 2 ≡a (mod p α), где p – простое нечетное число. Как было показано в п.4 §4, решение этого сравнения можно отыскать, решив сравнение x 2 ≡a (mod p ). Причем сравнение x 2 ≡a (mod p α) будет иметь два решения, если a является квадратичным вычетом по модулю p .

Пример:

Решить квадратичное сравнение x 2 ≡86(mod 125).

125 = 5 3 , 5 – простое число. Проверим, является ли 86 квадратом по модулю 5.

Исходное сравнение имеет 2 решения.

Найдем решение сравнения x 2 ≡86(mod 5).

x 2 ≡1(mod 5).

Это сравнение можно было бы решить способом, указанным в предыдущем пункте, но мы воспользуемся тем, что квадратный корень из 1 по любому модулю есть ±1, а сравнение имеет ровно два решения. Таким образом, решение сравнения по модулю 5 есть

x ≡±1(mod 5) или, иначе, x =±(1+5t 1).

Подставим получившееся решение в сравнение по модулю 5 2 =25:

x 2 ≡86(mod 25)

x 2 ≡11(mod 25)

(1+5t 1) 2 ≡11(mod 25)

1+10 t 1 +25 t 1 2 ≡11(mod 25)

10 t 1 ≡10(mod 25)

2 t 1 ≡2(mod 5)

t 1 ≡1(mod 5), или, что то же самое, t 1 =1+5t 2 .

Тогда решение сравнения по модулю 25 есть x =±(1+5(1+5t 2))=±(6+25t 2). Подставим получившееся решение в сравнение по модулю 5 3 =125:

x 2 ≡86(mod 125)

(6+25t 2) 2 ≡86(mod 125)

36+12·25t 2 +625t 2 2 ≡86(mod 125)

12·25t 2 ≡50(mod 125)

12t 2 ≡2(mod 5)

2t 2 ≡2(mod 5)

t 2 ≡1(mod 5), или t 2 =1+5t 3 .

Тогда решение сравнения по модулю 125 есть x =±(6+25(1+5t 3))=±(31+125t 3).

Ответ: x ≡±31(mod 125).

Рассмотрим теперь сравнение вида x 2 ≡a (mod 2 α). Такое сравнение не всегда имеет два решения. Для такого модуля возможны случаи:

1) α=1. Тогда сравнение имеет решение только тогда, когда a ≡1(mod 2), и решением будет x ≡1(mod 2) (одно решение).

2) α=2. Сравнение имеет решения только тогда, когда a ≡1(mod 4), и решением будет x ≡±1(mod 4) (два решения).

3) α≥3. Сравнение имеет решения только тогда, когда a ≡1(mod 8), и таких решений будет четыре. Сравнение x 2 ≡a (mod 2 α) при α≥3 решается так же, как сравнения вида x 2 ≡a (mod p α), только в качестве начального решения выступают решения по модулю 8: x ≡±1(mod 8) и x ≡±3(mod 8). Их следует подставить в сравнение по модулю 16, затем по модулю 32 и т. д. вплоть до модуля 2 α .

Пример:

Решить сравнение x 2 ≡33(mod 64)

64=2 6 . Проверим, имеет ли исходное сравнение решения. 33≡1(mod 8), значит сравнение имеет 4 решения.

По модулю 8 эти решения будут: x ≡±1(mod 8) и x ≡±3(mod 8), что можно представить как x =±(1+4t 1). Подставим это выражение в сравнение по модулю 16

x 2 ≡33(mod 16)

(1+4t 1) 2 ≡1(mod 16)

1+8t 1 +16t 1 2 ≡1(mod 16)

8t 1 ≡0 (mod 16)

t 1 ≡0 (mod 2)

Тогда решение примет вид x =±(1+4t 1)=±(1+4(0+2t 2))=±(1+8t 2). Подставим получившееся решение в сравнение по модулю 32:

x 2 ≡33(mod 32)

(1+8t 2) 2 ≡1(mod 32)

1+16t 2 +64t 2 2 ≡1(mod 32)

16t 2 ≡0 (mod 32)

t 2 ≡0 (mod 2)

Тогда решение примет вид x =±(1+8t 2) =±(1+8(0+2t 3)) =±(1+16t 3). Подставим получившееся решение в сравнение по модулю 64:

x 2 ≡33(mod 64)

(1+16t 3) 2 ≡33(mod 64)

1+32t 3 +256t 3 2 ≡33(mod 64)

32t 3 ≡32 (mod 64)

t 3 ≡1 (mod 2)

Тогда решение примет вид x =±(1+16t 3) =±(1+16(1+2t 4)) =±(17+32t 4). Итак, по модулю 64 исходное сравнение имеет четыре решения: x ≡±17(mod 64)и x ≡±49(mod 64).

Теперь рассмотрим сравнение общего вида: x 2 ≡a (mod m ), (a ,m )=1, - каноническое разложение модуля m . Согласно Теореме из п.4 §4, данному сравнению равносильна система

Если каждое сравнение этой системы разрешимо, то разрешима и вся система. Найдя решение каждого сравнения этой системы, мы получим систему сравнений первой степени, решив которую по китайской теореме об остатках, получим решение исходного сравнения. При этом количество различных решений исходного сравнения (если оно разрешимо) есть 2 k , если α=1, 2 k +1 , если α=2, 2 k +2 , если α≥3.

Пример:

Решить сравнение x 2 ≡4(mod 21).

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

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

МАОУ «Лицей №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.

Свойства:

Рефлексивность сравнений. Любое число aсравнимо само с собой по модулю m (m>0; a,m-целые числа).
Симметричность сравнений. Если число a сравнимо с числом b по модулю m, то число b сравнимо с числом a по тому же модулю(m>0; a,b,m-целые числа).
Транзитивность сравнений. Если число a сравнимо с числом b по модулю m, а число b сравнимо с числом cпо тому же модулю, то число a сравнимо с числом c по модулю m(m>0; a,b,c,m-целые числа).
Если число 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) (посвойству)

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

Сравнение с одним неизвестным 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.