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

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

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

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, закончено, как только вычеркнуты все составные, кратные простых, не превосходящих.

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

Два целых числа а и в называются сравнимыми по модулю 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.

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

Подобно тому, как мы это делаем с равенствами, сравнения по одинаковому модулю можно складывать и перемножить и т.д. (Так, перемножив сравнения 175 (mod 4) и 73 (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
0	0	1	2	3
1	1	2	3	0
2	2	3	0	1
3	3	0	1	2

*	0	1	2	3
0	0	0	0	0
1	0	1	2	3
2	0	2	0	2
3	0	3	2	1

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