ШВЕЦОВ К.И., БЕВЗ Г.П."СПРАВОЧНИК ПО ЭЛЕМЕНТАРНОЙ МАТЕМАТИКЕ. АРИФМЕТИКА, АЛГЕБРА", 1965

ГЛАВНАЯ СТРАНИЦА / МЕНЮ САЙТА / СОДЕРЖАНИЕ ДАННОЙ СТАТЬИ

11. Простые и составные числа

1. Простые и составные числа. Всякое число (Здесь имеются в виду только натуральные числа) делится на единицу и само на себя. Существуют числа, которые делятся не только на единицу и сами на себя, но имеют еще и другие делители. Например, число 12, кроме 1 и 12, имеет еще делители: 2, 3, 4, 6.

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

2. Таблица простых чисел. Для решения многих теоретических вопросов и практических задач большую помощь оказывают таблицы простых чисел. Поэтому еще в древности математики составляли эти таблицы. Очень простой способ составления таких таблиц нашел древнегреческий математик Эратосфен (III в. до н.э). Способ Эратосфена состоит в том, что из ряда натуральных чисел последовательно вычеркиваются все составные. Пусть, например, надо найти все простые числа в натуральном ряде от 1 до 30. Для этого выпишем все натуральные числа от 1 до 30 в порядке возрастания. Первое из них, 1 - не простое, вычеркиваем его. Следующее за ним число 2 простое, оставляем, а каждое второе после 2, т.е. 4, 6, 8, ... вычеркиваем. Следующее простое число 3 оставляем, а каждое третье, начиная после 3, вычеркиваем. Следующее простое число 5, оставляем, а каждое пятое, начиная после 5, вычеркиваем (при этом считаем и уже вычеркнутые числа). В результате получаем:

.

Оставшиеся невычеркнутые числа 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 - простые, меньшие 30.

Такой способ составления таблиц простых чисел называют "решетом Эратосфена".

Примечание. Если требуется составить таблицу простых чисел, не превышающих 𝑛, то указанным выше способом вычеркивают все составные числа, делящиеся на 2, 3, 5, и т.д. до наибольшего простого числа 𝑝, не превышающего . Например, если надо составить таблицу простых чисел, не превышающих 1000, надо вычеркнуть все составные, делящиеся на каждое простое число до 31 включительно.

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

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

В этом справочнике приведена таблица простых чисел, не превышающих 6000.

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

Известно, что последовательность простых чисел бесконечна (теорема Евклида). Среди простых чисел есть много таких, разность которых равна 2, например, 3 и 5, 5 и 7, 11 и 13, 17 и 19, ..., 179 и 181, ..., 10016957 и 10016959. Такие пары чисел называют простыми числами-близнецами. Есть предположение, что чисел-близнецов существует бесконечно много. Однако это не удается никому ни доказать, ни опровергнуть. Многие проблемы простых чисел можно было бы решить, если бы мы умели определять, сколько есть простых чисел, меньших любого натурального 𝑛. Однако этого мы сейчас еще не умеем делать. Известны только методы, дающие возможность приближенно находить количество простых чисел, меньших данного числа. В решении этой проблемы большое значение имеют работы великого русского ученого П.Л. Чебышева (1821-1894). В наше время ряд вопросов теории простых чисел разрешен известным советским математиком И. М. Виноградовым (род. 1891).

Литература. И.Я. Депман, История арифметики, Учпедгиз, 1959.

В. Серпинский, Что мы знаем и чего не знаем о простых числах. Физматгиз, М., 1963.

З. Трост, Простые числа, Физматгиз, М., 1959.

4. Разложение чисел на простые множители. Разложить число на простые множители - значит представить его в виде произведения простых чисел.

Составное число разлагается на простые множители единственным образом (с точностью до порядка сомножителей). Это значит, что если, например, число 20 разложилось на две двойки и пятерку, то оно и всегда будет так разлагаться независимо от того, начнем ли мы разложение с множителей 2 или с 5:

20 = 2 · 2 · 5 = 2 · 5 · 2 = 5 · 2 · 2.

Способы разложения чисел на простые множители изложим на примерах.

Пример 1. Пусть требуется разложить на простые множители число 315. На основании признаков делимости 2 не будет делителем числа 315, а 3 будет делителем 315. Тогда пишем число 315, проводим справа от него вертикальную черту и справа от черты пишем найденный делитель 3, а под числом 315 - частное от деления 315 на 3, т.е. 105.

Далее с числом 105 поступаем так же и устанавливаем, что 105 тоже имеет 3 своим делителем. Пишем число 3 справа от 105 за чертой, а под числом 105 записываем число 35, являющееся частным от деления 105 на 3. Число 35 на 3 не делится, поэтому испытываем следующее по величине простое число 5. Выполнив с 35 те же операции, справа от 35 пишем 5, а под ним число 7. Так как 7 простое число, то делим его самого на себя, под ним пишем 1.

Таким образом, этот процесс испытаний продолжаем до тех пор, пока не получим в частном 1. Числа, записанные справа от вертикальной черты, и составят все простые множители числа 315, т.е. 315 = 3 · 3 · 5 · 7.

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

Пример 2. Разложить на простые множители 5600.

Решение. Замечаем, что 5600 = 56 · 100. Число 56 равно произведению 7 · 8, следовательно, равно произведению трех двоек и одной семерки. Число 100 равно произведению двух двоек и двух пятерок.

Поэтому

5600 = 2 · 2 · 2 · 2 · 2 · 5 · 5 · 7.

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

5500 = 25 · 52 · 7.

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

5. Разложение на множители больших чисел. Если данное число небольшое, или если оно делится на небольшое простое число, то его без особого труда можно разложить на множители. Но в общем случае разложение чисел на множители очень трудоемко. Например, не так легко разложить на множители сравнительно небольшое число 12091. Испытывая числа 2, 3, 5, 7, 11, 13, 17, 19, 23 и т.д., мы долгое время не можем обнаружить его делители. А ведь данное число не простое!

Несколько лет математики не могли разложить на множители число 549755813881. И только недавно электронная вычислительная машина обнаружила, что это число (оно равно 239 - 7) простое.

12. Общие делители и кратные

1. Делители числа. Делителем данного числа называется число, на которое данное число делится без остатка. Всякое простое число, например 13, имеет только два делителя: единицу и самого себя. Всякое составное число имеет более двух делителей, например число 6 имеет 4 делителя: 1, 2, 3 и 6. Чтобы найти делители данного составного числа, предварительно раскладывают его на простые множители; каждый из этих множителей будет простым делителем данного числа. Перемножением же простых множителей по два, по три, по четыре и т.д. получают составные делители данного числа.

Пример. Найти все делители числа 50.

Решение. 50 = 2 · 52, следовательно, 50 делится на 1, 2, 5, 2 · 5, 52, 2 · 52. Других делителей число 50 не имеет.

Ответ. 1, 2, 5, 10, 25, 50

Известно правило, по которому можно легко определять количество всех делителей данного числа. Для этого надо увеличить на единицу показатель степени каждого сомножителя канонического разложения данного числа и полученные числа перемножить.

Пример. Сколько делителей имеет число 5600?

Решение. 5600 = 25 · 52 · 7; (5 + 1) · (2 + 1) · (1 + 1) = 36.

Ответ. Число 5600 имеет 36 делителей.

2. Общий делитель нескольких чисел. Общим делителем нескольких чисел называется число, на которое все данные числа делятся без остатка. Например, числа 25 и 35 имеют общие делители: 1 и 5; числа 42 и 105 имеют общие делители: 1, 3, 7 и 21. Среди всех общих делителей всегда имеется наибольший. Это число называется наибольшим общим делителем (НОД). В наших примерах в первом случае НОД равен 5, во втором - 21.

Пишут: НОД (25, 35) = 5; НОД (42, 105) = 21.

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

Первый способ - посредством разложения на простые множители. Чтобы найти НОД нескольких чисел, раскладывают каждое из этих чисел на простые множители и выписывают все общие множители, причем каждый из них берут с наименьшим показателем, встречающимся в этих разложениях.

Пример. Найти НОД чисел: 210, 1260 и 245.

Разложим эти числа на простые множители:

210 = 2 · 3 · 5 · 7; 1260 = 22 · 32 · 5 · 7; 245 = 5 · 72. Тогда НОД будет 5 · 7 = 35.

Второй способ - посредством последовательного деления. Он называется еще алгоритмом Евклида. Чтобы найти НОД двух чисел, делят большее число на меньшее, и если получается остаток, то делят меньшее число на остаток; если снова получается остаток, то делят первый остаток на второй. Так продолжают делить до тех пор, пока в остатке не получится нуль. Последний делитель и будет НОД данных чисел.

Пример. Найти НОД чисел 391 и 299.

Разделив число 391 на 299, получим в остатке 92. Разделив 299 на 92, получим в остатке 23. Разделив 92 на 23, получим в остатке 0. Следовательно, 23 есть НОД чисел 391 и 299.

Запись удобно расположить так:

Чтобы найти таким способом НОД трех и более чисел, находят сначала наибольший общий делитель каких-нибудь двух из них, затем - наибольший общий делитель найденного делителя и какого-нибудь третьего данного числа и т.д.

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

Примеры. Числа 15 и 22 взаимно просты; числа 7, 19, 32 и 84 взаимно просты; числа 18 и 15 не взаимно просты, так как НОД (18, 15) = 3.

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

Примеры. 6, 9 и 4 - числа взаимно просты, но не попарно взаимно просты; числа 8, 9, 7 и 55 - попарно взаимно просты.

4. Общее кратное чисел. Общим кратным данных чисел называется любое натуральное число, которое делится на каждое из данных чисел (без остатка).

Например, числа 12, 24 и 36 являются общими кратными чисел 3 и 4.

5. Наименьшее общее кратное (НОК). Из всех общих кратных особый интерес представляет наименьшее общее кратное.

Наименьшим общим кратным нескольких чисел называется самое меньшее натуральное число, которое делится на каждое из данных чисел. Например, для трех чисел: 6, 15 и 20 наименьшее общее кратное есть 60, так как никакое число, меньшее 60, не делится на 6, на 15 и на 20, а 60 делится на эти числа.

Пишут: НОК (6, 15, 20) = 60.

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

Первый способ - посредством разложения на простые множители. Чтобы найти НОК нескольких чисел, надо разложить эти числа на простые множители, затем, взяв разложение одного из них, умножить его на недостающие простые множители из разложений других чисел.

Пример. Найти НОК чисел 72 и 108.

Разложим данные числа на множители:

72 = 23 · 32,

108 = 22 · 33.

Выпишем все множители числа 108 (это удобнее, так как число 108 больше 72) и, добавив множитель 2, который еще дополнительно имеется в числе 72, получим:

НОК (72, 108) = 23 · 33 = 216.

Если большее из данных чисел делится на все остальные, то оно и будет наименьшим общим кратным этих чисел. Например, НОК (60, 120, 40) = 120.

Если никакая пара данных чисел не имеет общих множителей отличных от единицы, то для нахождения наименьшего общего кратного данных чисел их нужно перемножить. Например, наименьшее общее кратное чисел 7, 8 и 11 равно их произведению, т.е. НОК (7, 8, 11) = 7 · 8 · 11 = 616.

Второй способ. Известно, что , т.е.: наименьшее общее кратное двух чисел равно произведению этих чисел, деленному на их наибольший общий делитель (В.М. Брадис, Теоретическая арифметика, Учпедгиз, 1954, стр. 68).

Используя эту зависимость, можно определить НОК.

Пример. Найти НОК чисел 360 и 70. Так как НОД (360, 70) = 10, то НОК (360, 70) = 360 · 70 : 10 = 2520.

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

⇦ Ctrl предыдущая страница / следующая страница Ctrl ⇨

ГЛАВНАЯ СТРАНИЦА / МЕНЮ САЙТА / СОДЕРЖАНИЕ ДАННОЙ СТАТЬИ 

cartalana.orgⒸ 2008-2020 контакт: koshka@cartalana.org