Материал: Михайленко Е.В. Математика. Ч. 1. Элементы общей алгебры

Пример. Число -3577 единственным способом можно представить через положительное число 49 в виде:

-3577 = 49 ∙ (-73).

2.2. Делители и кратные Общий наибольший делитель

Всякое целое, делящее одновременно целые а, b, ..., l, называется их общим делителем. Наибольший из общих делителей называется наибольшим общим делителем и обозначается (а, b, ..., l).

Пример. Число -7 является общим делителем чисел 210, -1925, 770, 3115. Однако, наибольший общий делитель 35 = (210, -1925, 770, 3115).

Если (а, b, ..., l) = 1, то а, b, ..., l называются взаимно простыми.

Если каждое из чисел а, b, ..., l взаимно просто с каждым другим из них,

то а, b, ..., l называются попарно простыми.

Пример. Числа 21, 25, 15, 36 – взаимно простые (попарно простыми не являются). Числа 33, 25, 67, 131 – попарно простые (одновременно взаимно простые).

Рассмотрим общие делители двух чисел.

Если а кратно b, то совокупность общих делителей чисел а и b совпадает с совокупностью делителей одного b; в частности, (а, b) = b.

Пример. Числа 1, 3, 7, 21 совокупность общих делителей чисел 21 и 357. Это совпадает с совокупностью делителей числа 21.

Если а = b∙q + с, то совокупность общих делителей чисел а и b совпадает с совокупностью общих делителей чисел b и с; в частности,

(а, b) = (b, с).

Пример. Если 150 = 18∙7 + 24, то числа 1, 2, 3, 6 совокупность общих делителей чисел 150 и 18, числа 1, 2, 3, 6 совокупность общих делителей чисел

18 и 24.

Отсюда (150, 18) = 6 и (18, 24) = 6.

31

Алгоритм Евклида

Для отыскания общего наибольшего делителя, а также для вывода его важнейших свойств применяется алгоритм Эвклида.

Пусть а и b - положительные целые. Находим ряд равенств:

а = bq1 + r2, b = r2q2 + r3, r2 = r3q3 + r4,

… … …

rn-2 = rn-1qn-1 + rn, rn-1 = rnqn.

Тогда (a, b) = rn.- последнему не равному нулю остатку

Пример.

Применим алгоритм Эвклида к отысканию (525, 231). Для отыскания коэффициентов ряда равенств используем последовательное деление чисел:

Таким образом, составим ряд равенств: 525 = 231 ∙ 2 + 63; 231 = 63 ∙ 3 + 42; 63 = 42 ∙ 1 + 21; 42 = 21 ∙ 2.

Последний не равный нулю остаток r4 = 21. Значит, наибольший общий делитель (525, 231) = 21.

32

Свойства делителей

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

2.Если (а, b) = 1 и ас делится на b, то с делится на b.

3.Если каждое а1, а2, …, аn взаимно просто с каждым b1, b2, …, bn, то и произведение а1а2∙ …∙ аn взаимно просто с произведением b1b2 . . . bn .

4.Чтобы найти общий наибольший делитель чисел а1, а2, …, аn, составляем ряд чисел:

d1 = (а1, а2), d2 = (а2, d1), d3 = (а3, d2), … , dn = (аn, dn-1).

Тогда dn и будет общим наибольшим делителем чисел а1, а2, …, аn.

Пример. Найдем общий наибольший делитель чисел 120, 180, 72, 150. d1 = (120, 180) = 60, d2 = (72, 60) = 12, d3 = (150, 12) = 6.

Таким образом, (120, 180, 72, 150) = 6.

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

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

наименьшим кратным.

Пример. Число 3600 является общим кратным чисел 15, 6, 18, 9. Однако, общее наименьшее кратное [15, 6, 18, 9] = 90.

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

Пример. Для чисел 15 и 6 общие кратные 30, 60, 90, 120, … совпадают с кратными их общего наименьшего кратного 30.

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

Пример. Найдем наименьше общее кратное для чисел 525, 231. [525, 231] = 525 ∙ 231 / (525, 231) = 121275 / 21 = 5775.

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

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

Пример. Числа 1, 2, 3, 5, 7, 11, 13, 17, 19 являются простыми.

33

Свойства простых чисел

1.Число 1 имеет только один положительный делитель, равный 1.

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

3.Наименьший отличный от единицы делитель составного числа а не превосходит а1/2.

4.Число простых чисел бесконечно велико.

Решето Эратосфена

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

1.Выпишем список чисел 1, 2, 3, . . . до заданного числа.

2.Выделяем первое после единицы число 2 и вычеркиваем все последующие числа, кратные 2.

3.Выделяем следующее невычеркнутое число 3 и вычеркиваем все последующие числа, кратные 3.

... ... ... ... ...

4.Повторяем эти действия для чисел 5, 7, ... и всех невычеркнутых в ходе предыдущих действий чисел.

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

Простые числа Ферма и Мерсенна

Простое число называется числом Ферма, если оно имеет вид 2m + 1.

В 1650 году П.Ферма предположил, что числа вида Fn 2nn 1, n 0 простые для любого n. Однако Л.Эйлер в 1732 г. обнаружил, что F5 = 4294967297 – составное число: 4294967297 = 641 6700417. Более того, в

настоящее время при n ≥ 5 не известно ни одного простого числа Ферма.

34

Простые числа вида 2n - 1, где n- простое число, называются простыми числами Мерсенна.

Числа M2=3, M3= 7, M5=31, M7=127, M13, M17 и M19- простые. В 1772 г.

Л.Эйлер установил простоту числа M31, а И.Первушин в 1883 г. – простоту числа M61. В 2002г. найдено число М13 466 917 (39 известное число Мерсенна).

Каноническое разложение натурального числа

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

Пример. Число 518700 можно представить в виде

2 ∙ 2 ∙ 3 ∙ 5 ∙ 5 ∙ 7 ∙ 13 ∙ 19.

Каноническим разложением натурального числа a называется запись a p1 1 p2 2 p3 3 ... pk k

Пример. Представим число 518700 в каноническом виде: 22 ∙ 3 ∙ 52 ∙ 7 ∙ 13 ∙ 19.

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

Пример. Найти (18900, 48510) и [18900, 48510].

Разложим канонически 18900 = 22 ∙ 33 ∙ 52 ∙ 7; 48510 = 2 ∙ 32 ∙ 5 ∙ 72 ∙ 11. Тогда (18900, 48510) = 2 ∙ 32 ∙ 5 ∙ 7; [18900, 48510] = 22 ∙ 33 ∙ 52 ∙ 72 ∙ 11.

2.4. Функции теории чисел Целая и дробная части числа

Рассмотрим функции, которые изучаются в теории чисел. Пусть x – произвольное действительное число.

Целой частью числа x называется наибольшее целое число, не превосходящее x.

Целая часть числа x обозначается через [x]. Пример. Найдем целые части чисел.