ГЛАВА 9. ЭЛЕМЕНТЫ ТЕОРИИ ЧИСЕЛ

Теория чисел занимается, в основном, изучением свойств целых чисел. Целыми числами называются числа Z = {..., -3, -2, -1, 0, 1, 2, 3,...}.

Для любых a, в Є Z, a + в – сумма, разность а – в и произведение aв являются целыми числами. Но частное от деления а на в (если в не равно нулю) может быть как целым, так и не целым. В случае, когда частное являются целым, то обозначают а = вq, где q – целое число, а в тогда называют делителем числа а и записывают так: в \ а. В общем случае единственным является представление а = вq + r, о ≤ r < в, где r называют остатком от деления.

Наибольший общий делитель

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

Например, (10, 15) = 5, (8, 21) = 1.

Свойства наибольшего общего делителя

1. Если а= вq, то (а, в) = в.

2. Если а =вq + r, тогда общие делители чисел a и в суть те же, что и общие делители чисел в и r, в частности, (а, в) = (в, r).

3. Для определения наибольшего общего делителя применяется алгоритм Евклида. Он состоит в следующем. Пусть а и в – положительные целые числа и а > в. Составим ряд равенств:

a = вq₁+ r₂ o < r₂ < в

в = r₂q₂+ r₃ o < r₃ < r₂ (9.1.1)

r₂ = r₃q₃+ r₄ o < r₄ < r₃

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

r_n-2 = r_n-1 q_n-1 + r_n o < r_n < r_n-1

r_n-1 = r_nq_{n ,}

заканчивающийся, когда получается некоторое r_n+1 = 0. Последнее неизбежно случится, так как ряд в, r₂, r₃, убывающих целых чисел не может содержать более в положительных.

4. Из формул (9.1.1) алгоритма Евклида следует, что (а, в) = (в, r₂) = (r₂, r₃) = … = (r _n-1, r_n) = r_n.

Наибольший общий делитель равен последнему не равному нулю остатку алгоритма Евклида.

5. Из формул алгоритма Евклида следует также, что существуют целые t₁ и t₂, что t₁ a₁ + t₂ в = r_n.

В частности, если (а,в) = 1, то t₁ а + t₂в= 1.

Пример найдем (525, 231).

525 = 231·2 + 63

231 = 63·3 + 42

63 = 42·1 + 21

42 = 21·2

Последний остаток есть 21, значит, НОД = (525, 231,) = 21

Наименьшее общее кратное

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

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

1. Число 1 имеет только один положительный делитель, именно 1. В этом отношении число 1 в ряде натуральных чисел стоит совершенно особо. Всякое целое, больше 1, имеет не менее двух делителей, именно 1 и самого себя; если других делителей нет, то число называется простым. Целое, больше 1, имеющее кроме 1 и самого себя другие положительные делители, называют составным.

2. Наименьший, отличный от единицы, делитель целого большего единицы, есть число простое. В противном случае, можно было бы выбрать делитель еще меньше.

3. Наименьший отличный от единицы делитель (он будет простым) составного числа а не превосходит . Действительно, пусть q – именно этот делитель, тогда а= qв и в ≥ q (q – наименьший делитель), откуда a ≥ q² или q ≤ .

4. Простых чисел бесконечно много. Это следует из того, что каковы бы ни были различные простые числа р₁, р_{2 ,} р₃ ….. р_к, можно получить новое простое, среди них не находящееся. Таковым будет простой делитель суммы p₁ p_{2 …..} p_k+1, который, деля всю сумму, не может совпадать ни с одним из простых р₁, р₂, …, р_к.

5. Решето Эрастофена для составления таблицы простых чисел. Данный способ состоит в следующем.

Выписываем числа

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ….., N

Первое, большее 1, число этого ряда есть 2. Оно делится только на себя и на 1 и, следовательно, оно простое. Вычеркиваем из ряда (как составные) все числа, кратные 2, кроме самого себя.

Первое, следующее за 2 не вычеркнутое число есть 3 – оно также будет простым. С ним, как и с числом 2, проделываем ту же процедуру и т.д. Если указанным способом уже вычеркнуты все числа, кратные простым, меньшим p ( < p), то все не вычеркнутые, меньшие p², будут простые.

Составление таблицы простых чисел, не превосходящих N, закончено, как только вычеркнуты все составные, кратные простых, не превосходящих .

Сравнения и классы вычетов

Два целых числа а и в называются сравнимыми по модулю n (n – натуральное), если а-в делится на n без остатка. Это записывается так
а ≡ в (mod n) (9.4.1)

n – называется модулем сравнения (2.4.1). Например, 35=2
(mod 11), 25≡-11 (mod 9).

Запись а≡0 ( mod n), означает, что само а делится на n, т.е. а=kn.

Зафиксировав некоторый модуль сравнения n, можно всякое натуральное с представить в виде:

с=kn + r, (9.4.2.)

где k – частное от деления n, а r – остаток, совпадающий с одним из чисел

0, 1, 2,…, n-1 (9.4.3)

Остаток r называют вычетом числа с по модулю n. Заметим, что запись вида (9.4.2.), где 0 ≤ r ≤ n-1 допускает не только натуральные, но и любые числа.

Очевидно, из равенства (9.4.2) следует, что с ≡ r (mod n), т.е. всякое число сравнимо со своим остатком (вычетом) по модулю n. Пусть а и в два произвольных числа, записанных в виде (9.4.2):

а=к₁ n+r₁ в = к₂n+ r₂

Каждый из остатков r₁ и r₂ – это одно из чисел (9.4.3), поэтому их разность может делиться на n лишь в одном случае, когда r ₁= r₂. Но тогда и разность a-в = (к₁ – к₂) n + r­₁ – r₂ может делиться на n тогда и только тогда, когда r₁=r₂. Отсюда следует, что а ≡ в имеют одинаковые остатки при делении на n.

В теории чисел доказывается ряд свойств сравнений, во многом аналогичных свойствам обычным равенств.

Подобно тому, как мы это делаем с равенствами, сравнения по одинаковому модулю можно складывать и перемножить и т.д. (Так, перемножив сравнения 17 5 (mod 4) и 7 3 (mod 4), получим, как нетрудно убедиться верное сравнения 119=15 (mod 4). Вообще, если а≡в₁, а₂ в₂, то а­₁+ а₂≡ в₁+в₂, а₁а₂ в₁+в₂.

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

Доказать, что число (2002)^k + (2003)^k при любом нечетном натуральном к делится на 3.

Замечаем, что 2002 ≡ 1 (mod 3), 2003 ≡ 2 (mod 3). Заменяя в исходном выражении числа 2002 и 2003 их вычетами по модулю 3, получаем (2002)^k + (2003)^k ≡ 1^k + 2^k (mod 3).

Следовательно, левая часть сравнения делится на 3 тогда и только тогда, когда на 3 делится сумма 1+2^k. Для степеней двойки имеет:

2² ≡ 1, 2³ ≡ 2, 2⁴ ≡ 1, 2⁵ ≡ 2, и т.д.

Вообще, применяя индукцию по к, убеждаемся, что 2^k ≡ 1 при к четном и 2^k ≡ 2 при к нечетном. Таким образом при нечетном к

1+2^k ≡ 1+2≡0 (mod 3)

т.е., если к нечетно, то исходное выражение делится на 3.

В разобранной задаче числа 2002 и 2003 могли бы быть заменены любыми числами а и в, дающим при делении на 3 остатки соответственно 1 и 2.

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

= { с | с r (mod n) }

Иными словами, класс состоит из всех тех целых числе, которые записываются в виде (9.4.2.). Класс, определяемый равенством (9.4.4) называется классом вычетов.

Каждому вычету 0, 1, 2,..., n-1, отвечает свой класс вычетов, так что имеется ровно n различных классов вычетов.

Ясно, что эти классы попарно не пересекаются и каждое целое число попадает ровно в один класс.

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

В самом деле, пусть - ₁ и ₂ два класса вычетов. Выберем любые два числа из этих классов: . Пусть оказалось, что сума а₁ + а₂ имеет вычет r, а произведение а₁ а₂ – вычет s:

Поясним данное определение на примере, взяв за модуль сравнения n=2. В этом случае имеем два класса вычетов - и операции над ними выглядят так:

Часто, когда это не вызывает путаницы в обозначениях классов вычетов, опускают черту.

Выпишем, например, таблицы умножения и сложения классов по модулю 4 в этих упрощенных обозначениях:

Эти таблицы можно понимать и буквально, считая, что они определяют две операции на множестве {0, 1, 2, 3} – сложение и умножение по модулю 4.

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

Определение: Функция Эйлера φ(m) определяется для всех целых положительных m и равна количеству чисел ряда 1, 2,..., m-1, взаимно простых с m, где число 1 полагается взаимно простым с любым из чисел и φ(1)=1.

Примеры: φ(1)=1, φ(2)=1, φ(3)=2, φ(4)=2, φ(5)=4, φ(6)=2.

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

Функция Мебиуса

Определение. Функция Мебиуса μ(n) определяется для всех целых положительных n и равна

где

p_i – простые числа, α_i – кратность p_i в разложении.

Функция Мебиуса применяется в исследованиях по теории чисел.

9.7. Задания для самостоятельной работы по главе 9

1. Найти (343; 667) алгоритмом Евклида.

2. Найти (285; 437) алгоритмом Евклида.

3. Найти (255; 391) алгоритмом Евклида.

4. Проиллюстрировать решето Эрастофена для составления таблицы простых числе ряда: 1, 2,....50.

5. Проиллюстрировать решето Эрастофена для составления таблицы простых чисел ряда:

1, 2,.......100.

6. Доказать следующие свойства сравнений:

а≡а (mod m) – свойство рефлексивности,

а≡в (mod m) ═> в≡а (mod m) – свойство симметричности,

а≡в (mod m), в ≡ с (mod m) ═> a≡c (mod m) – свойство транзитивности.

7. Доказать свойство сравнений:

а≡в (mod m) ═> (a, m)=(в, т).

8. Доказать свойство сравнений:

а≡в (mod m), c ≡ d (mod m) ═> a+c≡в+d (mod m).

11. Найти значения функции Эйлера:

φ(7), φ(8), φ(9), φ(10).

12. Найти значения функции Мебиуса:

μ(8), μ(9), μ(10), μ(11)

Список литературы

1. Курош А.Г. Курс высшей алгебры. – М.: Наука, 1968.

2. Гельфанд И.М. Лекции по линейной алгебре. – М.: Наука, 1971.

3. Фаддеев Д.К. Лекции по алгебре. – М.: Наука, 1984.

4. Головина Л.И. Линейная алгебра и некоторые ее приложения. – М.: Наука, 1975.

5. Блох Э.Л, Лошинский Л.И., Турин В.Я. Основы линейной алгебры и некоторые ее приложения. – М.: Высшая школа, 1971.

6. Воеводин В.В. Линейная алгебра. – М.: Наука, 1974.

7. Ильин В.А., Позняк Э.Г. Линейная алгебра. – М., 1974.

8. Проскуряков И.В., Сборник задач по линейной алгебре. – М.: Лаборатория Базовых Знаний, 2000.

9. Алферова З.В., Матричная алгебра. – М.: МЭСИ, 1997.

10. Линейная алгебра: учебное пособие / Балюкевич Э.Л., Горбовцов Г.Я., Громенко Т.С., Ковалева Л.Ф., Мокеева И.К.; Моск. эконом.-стат. ин-т. – М., 1988.

11. Виноградов И.М. Основы теории чисел. СПб., Издательство «Лань», 2004.

12. Колосов В.А. Теоремы и задачи алгебры, теории чисел и комбинаторики. М., Гелиос АРВ, 2001.

13. Алфутова Н.Б., Устинов А.В. Алгебра и теория чисел. Сборник задач. М., МЦНМО, 2002

14. Смолин Ю.Н. Алгебра и теория чисел. М., Флинта Наука. 2006.

Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор...

Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)...

ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между...

Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: