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

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

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

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

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

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

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

Оглавление

Введение____________________________________________________3

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

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

   История возникновение понятия сравнений по модулю_____4

   Свойства сравнений___________________________________4

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

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

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

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

Заключение__________________________________________________10

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

Введение.

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

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

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

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

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

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

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

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

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

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

Обозначение

Примеры:

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

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

1. История возникновение понятия сравнений по модулю.

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

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

Если

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

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

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

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

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

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

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

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

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

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 /Сравнение_по_модулю.

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

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

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

На n они дают одинаковые остатки.

Эквивалентные формулировки: a и b сравнимы по модулю n , если их разность a - b делится на n , или если a может быть представлено в виде a = b + k n , где k - некоторое целое число. Например: 32 и −10 сравнимы по модулю 7, так как

Утверждение « a и b сравнимы по модулю n » записывается в виде:

Свойства равенства по модулю

Отношение сравнения по модулю обладает свойствами

Любые два целых числа a и b сравнимы по модулю 1.

Для того, чтобы числа a и b были сравнимы по модулю n , необходимо и достаточно, чтобы их разность делилась на n .

Если числа и попарно сравнимы по модулю n , то их суммы и , а также произведения и тоже сравнимы по модулю n .

Если числа a и b сравнимы по модулю n , то их степени a k и b k тоже сравнимы по модулю n при любом натуральном k .

Если числа a и b сравнимы по модулю n , и n делится на m , то a и b сравнимы по модулю m .

Для того, чтобы числа a и b были сравнимы по модулю n , представленному в виде его канонического разложения на простые сомножители p i

необходимо и достаточно, чтобы

Отношение сравнения является отношением эквивалентности и обладает многими свойствами обычных равенств. Например, их можно складывать и перемножать: если

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

Нельзя также выполнять операции со сравнениями, если их модули не совпадают.

Другие свойства:

Связанные определения

Классы вычетов

Множество всех чисел, сравнимых с a по модулю n называется классом вычетов a по модулю n , и обычно обозначается [a ] n или . Таким образом, сравнение равносильно равенству классов вычетов [a ] n = [b ] n .

Поскольку сравнение по модулю n является отношением эквивалентности на множестве целых чисел , то классы вычетов по модулю n представляют собой классы эквивалентности; их количество равно n . Множество всех классов вычетов по модулю n обозначается или .

Операции сложения и умножения на индуцируют соответствующие операции на множестве :

[a ] n + [b ] n = [a + b ] n

Относительно этих операций множество является конечным кольцом , а если n простое - конечным полем .

Системы вычетов

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

0,1,...,n − 1

или абсолютно наименьшие вычеты, состоящие из чисел

,

в случае нечётного n и чисел

в случае чётного n .

Решение сравнений

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

В теории чисел , криптографии и других областях науки часто возникает задача отыскания решений сравнения первой степени вида:

Решение такого сравнения начинается с вычисления НОД (a, m)=d . При этом возможны 2 случая:

• Если b не кратно d , то у сравнения нет решений.
• Если b кратно d , то у сравнения существует единственное решение по модулю m / d , или, что то же самое, d решений по модулю m . В этом случае в результате сокращения исходного сравнения на d получается сравнение:

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

Практическое вычисление значения c можно осуществить разными способами: с помощью теоремы Эйлера , алгоритма Евклида , теории цепных дробей (см. алгоритм) и др. В частности, теорема Эйлера позволяет записать значение c в виде:

Пример

Для сравнения имеем d = 2 , поэтому по модулю 22 сравнение имеет два решения. Заменим 26 на 4, сравнимое с ним по модулю 22, и затем сократим все 3 числа на 2:

Поскольку 2 взаимно просто с модулем 11, можно сократить левую и правую части на 2. В итоге получаем одно решение по модулю 11: , эквивалентное двум решениям по модулю 22: .

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

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

История

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

Содержание.

Введение

§1. Сравнение по модулю

§2. Свойства сравнений

1. Свойства сравнений, не зависящие от модуля
2. Свойства сравнений, зависящие от модуля

§3. Система вычетов

1. Полная система вычетов
2. Приведённая система вычетов

§4. Теорема Эйлера и Ферма

1. Функция Эйлера
2. Теорема Эйлера и Ферма

Глава2. Теория сравнений с переменной

§1. Основные понятия, связанные с решением сравнений

1. Корни сравнений
2. Равносильность сравнений
3. Теорема Вильсона

§2. Сравнения первой степени и их решения

1. Метод подбора
2. Способы Эйлера
3. Метод алгоритма Евклида
4. Метод цепных дробей

§3. Системы сравнений 1-ой степени с одним неизвестным

§4. Деление сравнений высших степеней

§5. Первообразные корни и индексы

1. Порядок класса вычетов
2. Первообразные корни по простому модулю
3. Индексы по простому модулю

Глава3. Приложение теории сравнений

§1. Признаки делимости

§2. Проверка результатов арифметических действий

§3. Обращение обыкновенной дроби в конечную

десятичную систематическую дробь

Заключение

Литература

Введение

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

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

Слово «модуль» происходит от латинского modulus, что по–русски означает «мера», «величина».

Утверждение «а сравнимо с b по модулю m» обычно записывают в виде a b (mod m) и называют сравнением.

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

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

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

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

Дипломная работа состоит из трёх глав, причём каждая глава разбита на параграфы, а параграфы на пункты.

В первой главе изложены общие вопросы теории сравнений. Здесь рассматриваются понятие сравнения по модулю, свойства сравнений, полная и приведённая система вычетов, функция Эйлера, теорема Эйлера и Ферма.

Вторая глава посвящена теории сравнений с неизвестной. В ней излагаются основные понятия, связанные с решением сравнений, рассматриваются способы решения сравнений первой степени (метод подбора, способ Эйлера, метод алгоритма Евклида, метод цепных дробей, с помощью индексов), систем сравнений первой степени с одной неизвестной, сравнений высших степеней и др.

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

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

Глава1. Общие вопросы теории сравнений

§1. Сравнение по модулю

Пусть z-кольцо целых чисел, m-фиксированное целое число и m·z-множество всех целых чисел, кратных m.

Определение 1. Два целых числа a и b называют сравнимыми по модулю m, если m делит a-b.

Если числа a и b сравнимы по модулю m, то пишут a b (mod m).

Условие a b (mod m) означает, что a-b делится на m.

a b (mod m)↔(a-b) m

Определим, что отношение сравнимости по модулю m совпадает с отношением сравнимости по модулю (-m) (делимость на m равносильно делимости на –m). Поэтому, не теряя общности, можно считать, что m>0.

Примеры.

Теорема. (признак сравнимости дух чисел по модулю m): Два целых числа a и b сравнимы по модулю m тогда и только тогда, когда a и b имеют одинаковые остатки при делении на m.

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

Пусть остатки при делении a и b на m равны, то есть a=mq₁+r, (1)

B=mq₂+r, (2)

Где 0≤r≥m.

Вычтем (2) из (1), получим a-b= m(q₁- q₂), то есть a-b m или a b (mod m).

Обратно, пусть a b (mod m). Это означает, что a-b m или a-b=mt, t z (3)

Разделим b на m; получим b=mq+r в (3), будем иметь a=m(q+t)+r, то есть при делении a на m получается тот же остаток, что и при делении b на m.

Примеры.

5=4·(-2)+3

23=4·5+3

24=3·8+0

10=3·3+1

Определение 2. Два или несколько чисел, дающие при делении на m одинаковые остатки, называются равноостаточным или сравнимыми по модулю m.

Примеры.

Имеем: 2m+1-(m+1)²= 2m+1 - m²-2m-1=- m², а (- m²) делится на m => наше сравнение верно.

1. Доказать, что следующее сравнения являются неверными:

Если числа сравнимы по модулю m, то они имеют с ним один и тот же НОД.

Имеем: 4=2·2, 10=2·5, 25=5·5

НОД(4,10) = 2, НОД(25,10) = 5, следовательно наше сравнение неверно.

§2. Свойства сравнений

1. Свойства сравнений, не зависящие от модуля.

Многие свойства сравнений аналогичны свойствам равенств.

а) рефлексивности: a a (mod m) (всякое целое число a сравнимо с самим собой по модулю m);

В) симметричности: если a b (mod m), то и b a (mod m);

С) транзитивности: если a b (mod m), а b с (mod m), то a с (mod m).

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

По условию m/(a-b) и m/ (c-d). Следовательно, m/(a-b)+(c-d), m/(a+c)-(b+d) => a+c b+d (mod m).

Примеры.

Найти остаток при делении на 13.

Решение: -1 (mod 13) и 1 (mod 13), тогда (-1)+1 0 (mod 13), то есть остаток от деления на 13 равен 0.

a-c b-d (mod m).

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

По условию m/(a-b) и m/(c-d). Следовательно, m/(a-b)-(c-d), m/(a-c)-(b-d) => (a-c) b-d (mod m).

1. (следствие свойств 1, 2, 3). К обеим частям сравнения можно прибавлять одно и то же целое число.

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

Пусть a b (mod m) и k –любое целое число. По свойству рефлексиности

k=k (mod m), а согласно свойствам 2 и 3 имеем a+k b+k (mod m).

a·c ·d (mod m).

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

По условию, a-b є mz, c-d є mz. Следовательно a·c-b·d = (a·c - b·c)+(b·c- b·d)=(a-b)·c+b·(c-d) є mz, то есть a·c ·d (mod m).

Следствие. Обе части сравнения можно возводить в одну и ту же целую неотрицательную степень: если а b (mod т) и s - целое неотрицательное число, то a s b s (mod m).

Примеры.

Решение: очевидно 13 1 (mod 3)

2 -1 (mod 3)

5 -1 (mod 3), тогда

- · 1-1 0 (mod 13)

Ответ: искомый остаток равен нулю, и А делится на 3.

Решение:

Докажем, что 1+ 0(mod13) или 1+ 0(mod 13)

1+ =1+ 1+ =

Так как 27 1 (mod 13), то 1+ 1+1·3+1·9 (mod 13).

ч.т.д.

3. Найдём остаток при делении с остатком числа на 24.

Имеем: 1 (mod 24), поэтому

1 (mod 24)

Прибавляя к обеим частям сравнения по 55, получаем:

(mod 24).

Имеем: (mod 24), поэтому

(mod 24) при любом k є N.

Следовательно (mod 24). Поскольку (-8) 16(mod 24), искомым остатком является 16.

1. Обе части сравнения можно умножать на одно и то же целое число.

2.Свойства сравнений, зависящие от модуля.

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

Так как a b (mod т) , то (а - b) т. А так как т n , то в силу транзитивности отношения делимости (а - b n) , то есть а b (mod n).

Пример.

Найти остаток от деления 196 на 7.

Решение:

Зная, что 196= , можно записать 196 (mod 14). Воспользуемся предыдущим свойством, 14 7, получим 196 (mod 7), то есть 196 7.

1. Обе части сравнения и модуль можно умножить на одно и то же целое положительное число.

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

Пусть a b (mod т ) и с-целое положительное число. Тогда a-b = mt и ac-bc=mtc, или ac bc (mod mc).

Пример.

Выяснить, является ли значение выражения целым числом.

Решение:

Представим дроби в виде сравнений: 4 (mod 3)

1 (mod 9)

31 (mod 27)

Сложим почленно эти сравнения (свойство 2), получим 124 (mod 27) Мы видим, что 124 не делится целочисленно на 27, следовательно значение выражения тоже не является целым числом.

1. Обе части сравнения можно разделить на их общий множитель, если он взаимно простой с модулем.

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

Если cа cb (mod m), то есть m/c(a-b) и число с взаимно простое с m, (с,m)=1, то m делит a-b. Следовательно, a b (mod т ).

Пример.

60 9 (mod 17), после деления обеих частей сравнения на 3 получим:

20 (mod 17).

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

Пример.

8 (mod 4), но 2 (mod 4).

1. Обе части сравнения и модуль можно разделить на их общий делитель.

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

Если ka kb (mod km), то k (a-b) делится на km. Следовательно, a-b делится на m, то есть a b (mod т ).

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

Пусть Р (х) = с 0 х п + с 1 х n-1 + ... + c n-1 x+ с n . По условию a b (mod т ), тогда

a k b k (mod m) при k = 0, 1, 2, …,n. Умножая обе части каждого из полученных n + 1 сравнений на c n-k , получим:

c n-k a k с n-k b k (mod m), где k = 0, 1, 2, …,n.

Складывая последние сравнения, получим: Р (а) Р (b) (mod m). Если а (mod m) и c i d i (mod m), 0 ≤ i ≤n, то

(mod m). Таким образом, в сравнении по модулю m отдельные слагаемые и множители можно заменять числами, сравнимыми по тому же модулю m.

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

a n c(mod m) и n k(mod m) не следует, что а k с (mod m).

Свойство 11 имеет ряд важных применений. В частности, c его помощью можно дать теоретическое обоснование признаков делимости. Для иллюстрации в качестве примера дадим вывод признака делимости на 3.

Пример.

Всякое натуральное число N можно представить в виде систематического числа: N = а 0 10 n + а 1 10 n-1 + ... + а n-1 10 + а n .

Рассмотрим многочлен f (х) = а 0 х n + a 1 x n-1 + ... + а n-1 х+а n . Так как

10 1 (mod 3), то по свойству 10 f (10) f(1) (mod 3) или

N = а 0 10 n + а 1 10 n-1 + ... + а n-1 10 + а n а 1 + а 2 +…+ а n-1 + а n (mod 3), т. е. для делимости N на 3 необходимо и достаточно, чтобы сумма цифр этого числа делилась на 3.

§3. Системы вычетов

1. Полная система вычетов.

Числа равноостаточные, или, что то же самое, сравнимые по модулю m, образуют класс чисел по модулю m.

Из такого определения следует, что всем числам класса отвечает один и тот же остаток r, и мы получим все числа класса, если в форме mq+r заставим q пробегать все целые числа.

Соответственно m различным значением r имеем m классов чисел по модулю m.

Любое число класса называется вычетом по модулю m по отношению ко всем числам того же класса. Вычет, получаемый при q=0, равный остатку r, называется наименьшим неотрицательным вычетом.

Вычет ρ, самый малый по абсолютной величине, называется абсолютно наименьшим вычетом.

Очевидно, при r имеем ρ=r; при r> имеем ρ=r-m; наконец, если m четное и r= , то за ρ можно принять любое из двух чисел и -m= - .

Выберем из каждого класса вычетов по модулю т по одному числу. Получим т целых чисел: х 1 ,…, х m . Множество {х 1 ,…, х т } называют полной системой вычетов по модулю m .

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

Пример.

Составить несколько полных систем вычетов по модулю т = 5. Имеем классы: 0, 1, 2, 3, 4.

0 = {... -10, -5,0, 5, 10,…}

1= {... -9, -4, 1, 6, 11,…}

Составим несколько полных систем вычетов, взяв по одному вычету из каждого класса:

0, 1, 2, 3, 4

5, 6, 2, 8, 9

10, -9, -8, -7, -6

5, -4, -3, -2, -1

и т. д.

Наиболее употребительны:

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

1, 2, …,m. В нашем примере: 1, 2, 3, 4, 5.

1. Полная система абсолютно наименьших вычетов. Вслучае нечетного m абсолютно наименьшее вычеты представляются рядом.

- ,…, -1, 0, 1,…, ,

а в случае четного m каким – либо из двух рядов

1, …, -1, 0, 1,…, ,

, …, -1, 0, 1, …, .

В приведенном примере:-2, -1, 0, 1, 2.

Рассмотрим теперь основные свойства полной системы вычетов.

Теорема 1 . Любая совокупность m целых чисел:

x l ,x 2 ,…,х m (1)

попарно не сравнимых по модулю m, образует полную систему вычетов по модулю m.

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

1. Каждое из чисел совокупности (1) принадлежит некоторому классу.
2. Любые два числа x i и x j из (1) несравнимы между собой, т. е. принадлежат различным классам.
3. Всего в (1) m чисел, т. е. столько же, сколько имеется классов по модулю т.

х 1 ,х 2 ,…,х т - полная система вычетов по модулю m.

Теорема 2 . Пусть (а, т) = 1, b - произвольное целое число; тогда если х 1 ,х 2 ,…,х т -полная система вычетов по модулю m, то и совокупность чисел ах 1 + b, ах 2 + b,…, ах m + b тоже полная система вычетов по модулю m.

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

Рассмотрим

Ах 1 + b, ах 2 + b,…, ах m + b (2)

1. Каждое из чисел совокупности (2) принадлежит некоторому классу.
2. Любые два числа ax i +b и ax j + b из (2) несравнимы между собой, то есть принадлежат различным классам.

Действительно, если бы в (2) имелись такие два числа, что

ax i +b ax j + b (mod m), (i = j), то получили бы ax i ax j (mod т). Так как (а, т) = 1, то свойству сравнений можно сократить обе части сравнения на а . Получаем x i x j (mod m).

По условию же x i x j (mod т) при (i = j) , так как х 1 ,х 2 , ..., х m - полная система вычетов.

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

Итак, ах 1 + b, ах 2 + b,…, ах m + b - полная система вычетов по модулю m.

Пример .

Пусть т = 10, а = 3, b = 4.

Возьмем какую-нибудь полную систему вычетов по модулю 10, например: 0, 1, 2,…, 9. Составим числа вида ах + b. Получим: 4, 7, 10, 13, 16, 19, 22, 25, 28, 31. Полученная совокупность чисел - полная система вычетов по модулю 10.

1. Приведённая система вычетов.

Докажем следующую теорему.

Теорема 1 .

Числа одного и того же класса вычетов по модулю m имеют с m один и тот же наибольший общий делитель: если a b (mod m), то (а, m) = (b, m).

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

Пусть a b (mod m). Тогда а = b +mt, где t є z. Из этого равенства следует, что (а, т) = (b, т).

Действительно, пусть δ-общий делитель a и m, тогда a δ, m δ. Так как а = b +mt, то b=a-mt, следовательно b δ. Поэтому любой общий делитель чисел a и m является общим делителем m и b.

Обратно, если m δ и b δ, то а = b +mt делится на δ, a потому любой общий делитель m и b является общим делителем a и m. Теорема доказана.

Определение 1. Наибольший общий делитель модуля т и любого числа а из данного класса вычетов по т называется наибольшим общим делителем т и этого класса вычетов.

Определение 2. Класс вычетов а по модулю т называется взаимно простым с модулем m , если наибольший общий делитель а и т равен 1 (то есть если т и любое число из а взаимно просты).

Пример.

Пусть т = 6. Класс вычетов 2 состоит из чисел {..., -10,-4, 2, 8, 14, ...}. Наибольший общий делитель любого из этих чисел и модуля 6 равен 2. Значит, (2, 6) = 2. Наибольший общий делитель любого числа из класса 5 и модуля 6 равен 1. Значит, класс 5 взаимно прост с модулем 6.

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

Определение 3. Совокупность вычетов по модулю m, взятых по одному из каждого взаимно простого с т класса вычетов по этому модулю, называется приведенной системой вычетов.

Из определения 3 следует способ получения приведенной системы вычетов по модулю т: надо выписать какую-либо полную систему вычетов и удалить из нее все вычеты, не взаимно простые с m. Оставшаяся совокупность вычетов - приведенная система вычетов. Приведенных систем вычетов по модулю m, очевидно, можно составить бесчисленное множество.

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

Пример.

Если т = 8, то 1, 3, 5, 7 - приведенная система наименьших неотрицательных вычетов, 1, 3, -3,-1 - приведенная система абсолютно наименьших вычетов.

Теорема 2.

Пусть число классов, взаимно простых с m, равно k. Тогда любая совокупность k целых чисел

попарно несравнимых по модулю m и взаимно простых с m, представляет собой приведенную систему вычетов по модулю m.

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

А) Каждое число совокупности (1) принадлежит некоторому классу.

1. Все числа из (1) попарно несравнимы по модулю т, то есть принадлежат различным классам по модулю m.
2. Каждое число из (1) взаимно просто с т, то есть все эти числа принадлежат различным классам, взаимно простым с модулем m.
3. Всего в (1) имеется k чисел, то есть столько, сколько должна содержать приведенная система вычетов по модулю m.

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

§4. Функция Эйлера.

Теоремы Эйлера и Ферма.

1. Функция Эйлера.

Обозначим через φ (т) число классов вычетов по модулю m, взаимно простых с m, то есть число элементов приведенной системы вычетов по модулю т. Функция φ (т) является числовой. Ее называют функцией Эйлера.

Выберем в качестве представителей классов вычетов по модулю т числа 1, ... , т - 1, т. Тогда φ (т) - количество таких чисел, взаимно простых с т. Иными словами, φ (т) - количество положительных чисел, не превосходящих m и взаимно простых с m.

Примеры.

1. Пусть т = 9. Полная система вычетов по модулю 9 состоит из чисел 1, 2, 3, 4, 5, 6, 7, 8, 9. Из них взаимно просты с 9 числа 1,2,4, 5, 7, 8. Так как количество этих чисел равно 6, то φ (9) = 6.
2. Пусть т = 12. Полная система вычетов состоит из чисел 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12. Из них взаимно просты с 12 числа 1, 5, 7, 11. Значит,

φ(12) = 4.

При т = 1 полная система вычетов состоит из одного класса 1. Общим натуральным делителем чисел 1 и 1 является 1, (1, 1) = 1. На этом основании полагают φ(1) = 1.

Перейдем к вычислению функции Эйлера.

1) Если т = р - простое число, то φ (р) = р- 1.

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

Вычеты 1, 2, ... , р- 1 и только они взаимно просты с простым числом р. Поэтому φ (р) = р - 1 .

2) Если т = р к - степень простого числа р, то

φ(т) = (р - 1) . (1)

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

Полная система вычетов по модулю т = р к состоит из чисел 1,..., p k - 1, р к Натуральные делители т являются степенями р. Поэтому число а может иметь общий делитель с m, отличный от 1 , лишь в случае, когда а делится на р. Но среди чисел 1 , ... , p k -1 на р делятся лишь числа р, 2р, ... , р 2 , ... р к , количество которых равно р к : р = р к-1 . Значит, взаимно просты с т = р к остальные р к - р к-1 = p k-l (p-1) чисел. Тем самым доказано, что

φ (р к ) = р к-1 (р-1).

Теорема 1.

Функция Эйлера мультипликативна, то есть для взаимно простых чисел m иn имеем φ (mn) = φ(m) φ (n).

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

Первое требование в определении мультипликативной функции выполняется тривиальным образом: функция Эйлера определена для всех натуральных чисел, причем φ (1) = 1. Нам надо лишь показать, что если тип взаимно простые числа, то

φ (тп) = φ (т) φ (п). (2)

Расположим полную систему вычетов по модулю тп в виде п х т - матрицы

1 2 т

т + 1 т + 2 2т

………………………………

(п - 1) т+ 1 (п - 1) m + 2 пт

Поскольку т и п взаимно просты, то число х взаимно просто с тп тогда и только тогда, когда х взаимно просто с т и х взаимно просто с п . Но число km + t взаимно просто с т в том и только том случае, когда t взаимно просто с т. Поэтому числа, взаимно простые с m, располагаются в тех столбцах, для которых t пробегает приведенную систему вычетов по модулю т. Число таких столбцов равно φ (т). В каждом столбце представлена полная система вычетов по модулю п. Из этих вычетов φ (п) взаимно просты с п. Значит, общее количество чисел, взаимно простых и с т и с n, равно φ (т) φ (n )

(φ (т) столбцов, в каждом из которых берется φ (п) чисел). Эти числа, и только они, взаимно просты с тп. Тем самым доказано, что

φ (тп) = φ (т) φ (п).

Примеры.

№1 . Доказать справедливость следующих равенств

φ(4n) =

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

№2 . Решить уравнение

Решение: так как (m)= , то = , то есть =600, =75, =3· , тогда х-1=1, х=2,

y-1=2, y=3

Ответ: х=2, y=3

Мы можем вычислить значение функции Эйлера (m), зная каноническое представление числа m:

m= .

В силу мультипликативности (m) имеем:

(m)= .

Но по формуле (1) получаем, что

-1), и поэтому

(3)

Равенство (3) можно переписать в виде:

Поскольку =m, то (4)

Формула (3) или, что то же самое, (4) и является искомой.

Примеры.

№1 . Чему равна сумма

Решение: ,

, =18 (1- ) (1- =18 , тогда = 1+1+2+2+6+6=18.

№2 . На основании свойств числовой функции Эйлера доказать, что в последовательности натуральных чисел существует бесконечное множество простых чисел.

Решение: Пологая количество простых чисел конечным множеством, допустим, что - наибольшее простое число и пусть a= есть произведение всех простых чисел, на основании одного из свойств числовой функции Эйлера

Так как a≥ , то a – составное число, но так как его каноническое представление содержит все простые числа, то =1. Имеем:

=1 ,

что невозможно, и таким образом доказано, что множество простых чисел бесконечно.

№3 .Решить уравнение , где х= и =2.

Решение: Используем свойство числовой функции Эйлера,

,

и по условию =2.

Выразим из =2 , получим , подставим в

:

(1+ -1=120, =11 =>

Тогда х= , х=11·13=143.

Ответ: х= 143

2. Теорема Эйлера и Ферма.

В теории сравнений важную роль играет теорема Эйлера.

Теорема Эйлера.

Если целое число a взаимно простое с m, то

(1)

Доказательство. Пусть

(2)

есть приведённая система вычетов по модулю m.

Если a -целое число, взаимно простое с m, то

(3)