Простые числа и непрерывные дроби

⇐ ПредыдущаяСтр 4 из 10Следующая ⇒

Сумма а + b, разность а – b и произведение ab двух целых а и b являются также целыми. Но частное от деления а на b (если b не равно нулю) может быть как целым, так и не целым.

В случае, когда частное от деления а на b – целое, обозначая его буквой q, имеем a = bq, т.е. а представляется произведением b на целое. Говорим тогда, что а делится на b или что b делит а. При этом а называем кратным числа b, a b – делителем числа а. То обстоятельство, что b является делителем числа а, записывается так: b \ а.

Примеры:

Имеем 21 = 7·3, 0 = 9·0, 85 = 17(–5).

Поэтому можем сказать: 21 делится на 7, 0 делится на 9, 85 делится на 17 или: 7 делит 21, 9 делит 0, 17 делит 85.

Основные теоремы:

1. Если а кратно т, т кратно b, то а кратно b.

Действительно, из , следует . Таким образом, а представляется произведением b на целое число am и тем самым делится на b.

2. Если в равенстве вида k + l + … + n = p + q + … + s относительно всех членов, кроме какого-либо одного, известно, что они кратны b, то и этот один член кратен b.

Действительно, пусть таким одним членом будет k. Имеем

, …, , , , …,

Таким образом, k представляется произведением b на целое число

и тем самым делится на b.

3. Теорема о делении с остатком.

Всякое целое а представляется единственным способом с помощью положительного целого b равенством вида

a = bq + r; < b.

Действительно, одно представление числа а равенством такого вида получим, взяв bq равным наибольшему кратному числа b, не превосходящему а. Допустив же существование представления числа а еще одним равенством того же вида: ; < b и вычитая почленно это последнее равенство из предыдущего, получим

(1)

Отсюда убедимся (теорема 2), что разность r – r₁ кратна b. С другой стороны, легко видеть, что та же разность, как разность двух неотрицательных чисел, меньших b, сама будет численно меньше b, числом же, кратным b и численно меньшим b, является лишь число 0. Поэтому , а отсюда и из равенства (1) будет следовать, что и . Таким образом, второе представление числа а тождественно первому.

Число q называется неполным частным, а число r – остатком от деления а на b. Очевидно, что при r = 0 понятия «неполное частное» и «частное» совпадают.

Примеры:

Пусть b = 14. Имеем

177 = 14·124 + 9, 0 < 9 < 14,

154 = 14·11 + 0, 0 = 0 < 14.

Наибольший общий делитель (НОД)

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

Примеры. Числа 6, 10, 15, ввиду (6, 10, 15) = 1, – взаимно простые. Числа 8, 13, 21, ввиду (8, 13) = (8, 21) = (13, 21) = 1, – попарно простые.

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

Действительно, всякий общий делитель чисел а и b является делителем и одного b. Обратно, раз а кратно b, то (1) всякий делитель числа b является также делителем числа а, т.е. является общим делителем чисел b и а. Таким образом, совокупность общих делителей чисел а и b совпадает с совокупностью делителей одного b. А так как наибольший делитель числа b есть само b, то (а, b) = b.

5. Если

a = bq + c,

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

Действительно, написанное равенство показывает, что всякий общий делитель чисел а и b делит также и с и, следовательно, является общим делителем чисел b и c. Обратно, то же равенство показывает, что всякий общий делитель чисел b и с делит а и, следовательно, является общим делителем чисел а и b. Таким образом, общие делители чисел а и b суть те же, что и общие делители чисел b и с; в частности, должны совпадать и наибольшие из этих делителей, т.е. (a, b) = (b, с).

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

Пусть а и b – положительные целые и а > b. Согласно теореме 3 находим ряд равенств

(2)

………………………

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

Рассматривая равенства (2), идя сверху вниз, убеждаемся, что общие делители чисел с и b одинаковы с общими делителями чисел b и r₂, далее одинаковы с общими делителями чисел r₂ и r₃, чисел r₃ и r₃, ..., чисел r_n_{– 1}и r_n наконец, с делителями одного числа r_n, являющегося последним не равным нулю остатком алгоритма Евклида. Одновременно с этим имеем

и приходим к следующим результатам.

6. Совокупность общих делителей чисел а и b совпадает с совокупностью делителей их общего наибольшего делителя

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

Пример. Применим алгоритм Евклида к отысканию (525, 231). Произведем вспомогательные вычисления

Находим

525 = 231*2 + 63,

231 = 63*3 + 42,

63 = 42*1 + 21,

42 = 21*2.

Здесь последний положительный остаток есть r₄ = 21. Значит, (525, 231) = 21.

8. Обозначая буквою т любое положительное целое, имеем (am, bm) = (a, b)m.

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

Действительно, умножив соотношения (1) почленно на т, получим новые соотношения, где вместо a, b, r₂, ..., r_n будут стоять am, bm, r₂m, ..., r_nm. Поэтому (am, bm) = r_nm и, таким образом, верно утверждение 8.

Применяя утверждение 8, находим

Отсюда следует утверждение 9.

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

Действительно, (ас, b)делит ас и bc, значит, оно делит и (ас, bc), ввиду утверждения 8равное с. Но (ас; b)делит и b, поэтому оно делит и (с, b). Обратно, (с, b)делит ас и b, поэтому оно делит и (ас, b). Таким образом, (ас, b)и (с, b)взаимно делят друг друга и, следовательно, равны между собой.

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

Действительно, в соответствии с теоремой 4, при ас, делящемся на b, имеем (ас, b) = b и получаем b = (с, b). А этим и доказывается делимость с на b.

12.Если каждое взаимно просто с каждым , то и произведение взаимно просто с произведением .

Действительно, согласно 1 находим

и далее, полагая ради краткости = А, точно таким же путем выводим

= ( , A) = ( , A) = ( , A) = 1.

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

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

Пусть и, следовательно (согласно пункту 9), . Пусть М – какое-либо общее кратное чисел а и b. Так как М кратно а, то M = ak, где k – целое. Но М кратно и b. Поэтому

должно быть целым и, следовательно (в соответствии с пунктом 11), к должно делиться на b₁. Поэтому k = b₁t, где t – целое, причем для М получается формула

M = . (3)

Обратно, очевидно, что М, представляемое формулой (3) при любом целом t, будет общим кратным а и b, и, таким образом, формула (3) дает общий вид всех общих кратных чисел a и b.

Наименьшее положительное из этих общих кратных, т.е. общее наименьшее кратное, получаем при t = 1.

Оно будет

(4)

Теперь формулу (3) можно переписать так:

M = mt. (5)

Формулы (4) и (5) приводят к теоремам:

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

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

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

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

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

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

Действительно, пусть q – наименьший отличный от 1 делитель целого а, большего 1. Если бы q было бы составным, то оно имело бы некоторый делитель с условием , причем число а, делясь на q, должно делиться на . А это противоречило бы нашему предположению относительно числа q.

16.Наименьший отличный от единицы делитель составного числа а (согласно предыдущему утверждению он будет простым) не превосходит .

Действительно, пусть q–этот делитель, тогда , откуда, перемножая и сокращая на , получим .

17.Простых чисел бесконечно много.

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

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

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

1, 2,.... N. (6)

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

Вычеркиваем из ряда (6) (как составные) все числа, кратные 2, кроме самого 2. Первое следующее за 2 невычеркнутое число есть 3. Оно не делится на 2 (иначе оно оказалось бы вычеркнутым). Следовательно, 3 делится только на 1 и на самого себя, а потому оно также будет простым.

Вычеркиваем из ряда (6) все числа, кратные 3, кроме самого 3. Первое следующее за 3 невычеркнутое число есть 5. Оно не делится ни на 2, ни на 3 (иначе оно оказалось бы вычеркнутым). Следовательно, 5 делится только на 1 и на самого себя, а потому оно также будет простым.

И так далее.

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

18. Приступая к вычеркиванию кратных простого р, это вычеркивание следует начинать с .

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

⇐ Предыдущая 1 2 345 6 7 8 9 10 Следующая ⇒