Модулярная арифметика. Сравнения по модулю, их

  свойства.

Определение 7.1. Рассмотрим целые числа  и . Если при делении на число  числа  и дают одинаковые остатки, то говорят, что  и   сравнимы по модулю .

Этот факт обозначают следующим образом: , или .

Пример. – верно, так как  и .

Следующая теорема устанавливает очевидное необходимое и достаточное условие сравнимости чисел по модулю.

Теорема 7.1 (признак сравнения по модулю). Для того, чтобы целые числа  и  были сравнимы по модулю , необходимо и достаточно чтобы .

Доказательство. Необходимость. Пусть . Это значит, что , где  и , где . Тогда . Поскольку , .

Достаточность. Пусть . Тогда  где . Разделим число  на , получим, , где . Тогда . Следовательно, . Значит, при делении на  число  дает такой же остаток, что и число . А это и означает, что .

Следствие. Если , где – остаток от деления числа  на , то .

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

 

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

 

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

1. Бинарное отношение  на множестве целых чисел Z является отношением эквивалентности.    

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

Доказательство этого утверждения следует непосредственно из определения сравнения по модулю.

1) Рефлексивность: .

2) Симметричность: .

3) Транзитивность:  .

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

Пример. Положим  Тогда отношение задает 5 классов вычетов на множестве Z:

 ;

;

;

;

.

Классы вычетов по модулю m обычно обозначаются , где .

2. Сравнения по одному и тому же модулю можно почленно складывать:                                        

.

Доказательство.  По определению сравнения по модулю

, где ; , где .

Тогда , где m .

3. Сравнения по одному и тому же модулю можно почленно вычитать:                                    

.

Доказательство этого свойства аналогично доказательству

предыдущего.

    4. К обеим частям сравнения можно прибавлять одно и то же число:

, .

Доказательство этого утверждения следует непосредственно из признака сравнения по модулю.

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

    5. Сравнения по одному и тому же модулю можно почленно перемножать:

     .

Доказательство. По определению сравнения по модулю

 

, где .

Тогда . Поскольку , последнее равенство означает, что .

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

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

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

Доказательство этого утверждения непосредственно следует из свойства 5 и из рефлексивности свойства сравнения по модулю: .

    Рассмотрим теперь свойства сравнений, зависящие от модуля.

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

    Доказательство. Пусть  и n. Тогда  и , где . Следовательно, n .

    7. Если  и , то .

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

    8. Пусть два числа сравнимы по модулю m и k – общий делитель этих чисел. Пусть d – наибольший общий делитель чисел m и k. Если данные числа разделить на k, то частные от деления будут сравнимы по модулю :

.

    Доказательство. По свойству НОД (§ 3, теорема 3) имеем: , ,где . Тогда m

.

Поскольку , из свойства 3 взаимно простых чисел следует, что . Это означает, что . Но , следовательно, .

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

    Доказательство следует из того, что .

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

    Доказательство следует непосредственно из утверждения теоремы.

Примеры. 1) Cравнение , очевидно, верно. Поскольку , обе части сравнения можно разделить на 3, полученное сравнение  также верно.

2) Рассмотрим верное сравнение . Числа 21 и 33 имеют общий делитель 3, который не взаимно прост с модулем равным 6. Поэтому применить следствие 2 (т. е. разделить обе части сравнения на 3) нельзя, полученное сравнение  – неверно. Однако, можно применить теорему:  – верное сравнение.

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

1) Доказать, что число  делится на 7.

Найдем остаток от деления числа 839 на 7:

.

Следовательно, . Тогда по свойствам сравнения по модулю . Это и означает, что  делится на 7.

2) Найти остаток от деления числа  на 11.

 Найдем сначала остаток от деления на 11:

Теперь найдем остаток от деления на 11:

Сложим найденные остатки:

             

Таким образом, мы получили, что искомый остаток равен 2

Простые числа

Определение 8.1. Натуральное число называется простым, если оно имеет ровно два различных делителя. Если натуральное число имеет больше двух различных делителей, то оно называется составным.

Из определения следует, что число 1 не является ни простым, ни составным. 

Теорема 8.1. Наименьший делитель составного числа, отличный от 1, является простым числом.

Доказательство. Рассмотрим составное число n. Расположим его делители в порядке возрастания: . Докажем, что  – простое число. Предположим, что это утверждение неверно, и  – составное число. Тогда среди его делителей есть число , удовлетворяющее условиям: . Поскольку  и , из транзитивности делимости следует, что  . При этом из свойств делимости (свойства 5) следует, что . Значит, число  – не наименьший делитель числа n, отличный от 1. Полученное противоречие доказывает утверждение теоремы.

Введем понятие канонического разложения натурального числа.

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

Рассмотрим процесс разложения на множители составного числа n. По теореме 8.1 наименьший делитель числа n, отличный от 1, является простым числом. Обозначим его . Тогда , где – натуральное число, . Если число  является простым, то процесс закончен. Если число  – составное, то его наименьший делитель, отличный от 1, является простым числом. Обозначим его . Тогда  и , причем . Если число  является простым, то процесс закончен. Если число  – составное, то найдем  – его наименьший делитель, отличный от 1 и т. д. Продолжая процесс, получим , где числа – простые и . Поскольку убывающая последовательность натуральных чисел может содержать только конечное число членов, данный процесс на некотором шаге закончится. Получим разложение числа n на простые множители. Среди них могут оказаться равные, объединяя их и записывая в порядке возрастания, получим каноническое разложение числа n: , где числа  – простые,  – натуральные.

    Заметим, что число 1 не будучи ни простым, ни составным числом, не имеет канонического разложения.

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

    Теорема 8.2 (Евклида). Множество простых чисел бесконечно.

    Доказательство. Предположим, что утверждение теоремы неверно: множество простых чисел конечно и p – самое большое простое число. Рассмотрим число . Поскольку , число n – составное. Рассмотрим каноническое разложение числа n: , где – простые числа. Тогда , , так как p – самое большое простое число. Очевидно, что  для . При этом для . Тогда по свойству делимости (свойство 4)  – неверно, поскольку число 1 не делится на . Значит  – неверно. Полученное противоречие доказывает справедливость утверждения теоремы.

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

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

Теорема 8.3. Если число n составное, то в его каноническом разложении найдется хотя бы одно простое число , не превосходящее .

    Доказательство. Рассмотрим каноническое разложение числа n:

, где – простые числа. Предположим, что утверждение теоремы неверно:  для . Тогда  для . При этом  для . Заметим, что . Действительно, если , то данное утверждение, очевидно, верно. Если же , то , в противном случае число n было бы простым. Следовательно, . Полученное противоречие доказывает справедливость утверждения теоремы.

    Следствие. Если , и n не делится ни на одно простое число, не превосходящее , то число n – простое.

    Доказательство следствия следует непосредственно из утверждения теоремы.

Пример. Докажем, что число 1051 – простое. Для этого проверим, делится ли 1051 на простые числа, не превосходящие , а именно числа 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31. Как нетрудно установить, число 1051 на перечисленные простые числа не делится, следовательно, является простым.

 

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

Определение 9.1. Функцией Эйлера называется функция , определенная на множестве натуральных чисел , сопоставляющая каждому натуральному числу m  количество натуральных чисел, взаимно простых с m и не превосходящих m.

Примеры. 1) Найдем . Для этого выпишем числа, не превосходящие 9 и взаимно простые с 9: 1, 2, 4, 5, 7, 8. Таким образом, получим, что .

2) Найдем . Поскольку число 11 – простое, все числа, не превосходящие 11, за исключением его самого, взаимно просты с ним, следовательно, .

3) Очевидно, что  и .

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

Теорема 9.1. Пусть n – натуральное число, отличное от 1. Рассмотрим его каноническое разложение: . Тогда      .

Доказательство. Рассмотрим последовательность натуральных чисел:

1, 2,…, n. Вычеркнем из этой последовательности все числа, которые делятся на . Таких чисел будет . Останется  чисел, которые на  не делятся. Затем из оставшихся чисел вычеркнем все числа, делящиеся на . Их будет . Останется чисел. Продолжая вычеркивать числа, делящиеся на , получим требуемую формулу

            .

Теорема доказана.

Примеры. Вычислим значения функции Эйлера, используя формулу из теоремы.

1) ,

2) ,

3) .

Заметим, что по данной формуле вычислить значение нельзя, так как число 1 не имеет канонического разложения.

 

                  Свойства функции Эйлера.

 

1. Если p – простое число, а k – натуральное число, то . 

Доказательство. По теореме 9.1 .

2. Мультипликативное свойство функции Эйлера.

Если числа n и m взаимно просты, то .

Доказательство. Рассмотрим канонические разложения чисел n и m:

 и . Тогда каноническое разложение произведения чисел n и m с точностью до порядка сомножителей равно:

                  ,

поскольку все сомножители данного произведения различны, что следует из взаимной простоты чисел n и m.

По теореме 9.1

.

Теорема 9.2 (Эйлера). Рассмотрим натуральные числа  и m: . Тогда .

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

2) Будем далее считать, что  и . Выпишем различные натуральные числа, меньшие m и взаимно простые с m: . Рассмотрим произведения  и найдем остатки от деления каждого из этих произведений на m:

                        , ,

                        ,                  (9.1)

                         ……………..

 

                        , .

3) Докажем, что все остатки  различны. Пусть это утверждение

неверно. Предположим, например, что . Тогда, вычитая из первого равенства второе, получим

.

Отсюда следует, что . При этом число a не делится на m, так как числа a и m взаимно просты и . Тогда, очевидно, , значит, по свойству делимости 5 . Но  и , следовательно, . Полученное противоречие доказывает, что сделанное нами предположение о равенстве остатков неверно.

4) Докажем, что все остатки взаимно просты с m. Пусть это утверждение неверно. Предположим, например, что  и m не взаимно просты: . Тогда  и , где . Но . Тогда .

При этом  (по условию теоремы) и  (по определению чисел ), следовательно, . Однако, d – общий делитель чисел  и m, и, как мы предположили, . Полученное противоречие доказывает, что сделанное нами предположение, неверно.

5) Таким образом, мы получили, что числа – различны и

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

                  .

Систему равенств (9.1) можно привести к виду:

                       ,

                       ,                                       (9.2)

                        ………………..

                      .

Перемножая левые и правые части сравнений (9.2), получим:

                            (9.3)

Поделив обе части (9.3) на , получим требуемое равенство.

Теорема 9.3 (Ферма). Пусть p – простое число, и натуральное число a не делится на p. Тогда .

Доказательство. Доказательство теоремы непосредственно следует из теоремы Эйлера. Действительно, если число a не делится на простое число p, то . Тогда по теореме Эйлера . Но , следовательно, .

Следствие. В условиях теоремы Ферма .

Доказательство. Умножив обе части сравнения на число a, получим требуемое утверждение.

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

Примеры. 1) Найти остаток от деления числа  на 7.

Положим  Условия теоремы Ферма выполняются: , следовательно, . Возведем обе части сравнения в степень 4, получим . Поскольку ,

. Значит, остаток от деления числа  на 7 равен 4.

2) Найти остаток от деления числа  на 34.

Положим  Условия теоремы Эйлера выполняются: . Вычислим . Заметим, что . Тогда по теореме Эйлера , а . Значит,

, то есть искомый остаток равен 13.

3) Найти остаток от деления числа  на число .

Числа 1, 2, 3, 4, 5 и 6 взаимно просты с числом 7. Тогда по теореме Ферма    

               , , ,  , ,  .

Возведем обе части каждого сравнения в степень 3, получим

               , , ,  , ,  .

Сложим правые и левые части сравнений и прибавим к обеим частям по 1, получим . Следовательно, число a делится на 7 без остатка.