Лекция 3. Простые и составные числа План

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

2. Распределение простых чисел в натуральном ряду.

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

Содержание

1. Каждое натуральное число р ≠ 1 имеет по крайней мере два делителя: 1 и p.

Определение 6. Натуральное число р ≥ 1 называется простым, если оно не имеет делителей, отличных от 1 и р.

Например, числа 7, 13, 19 являются простыми, так как каждое из них делится только само на себя и на единицу.

Определение 7. Натуральное число п ≥ 1 называется составным, если оно имеет более двух делителей.

Например, 12 – составное число, так как имеет делители: 1, 2, 3, 4, 6, 12.

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

I кл. – число 1 (один делитель);

II кл. – простые числа (два делителя);

III кл. – составные числа (более двух делителей).

Известно, что нуль делится на любое натуральное число, то есть имеет бесконечно много делителей. Поэтому множество N₀ целых неотрицательных чисел по числу натуральных делителей разбивают на четыре непересекающихся класса. К трем вышеуказанным классам добавляется

IV кл. – число 0 (бесконечно много делителей).

Теорема 16. (О существовании простого делителя.) Если d ≠ 1 – наименьший делитель натурального числа n > 1, то d – простое число.

Доказательство. Будем рассуждать методом от противного. Предположим, что d – составное число. Тогда, по определению 7, d делится на 1, d и некоторое число t, где 1 < t < d. Следовательно, имеем и, а по транзитивности отношения делимости это означает, что. Получили противоречие с тем, что d – наименьший делитель числа п. Тем самым теорема доказана.

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

Теорема 17. Множество простых чисел бесконечно.

Доказательство. Проведем доказательство методом от противного. Предположим, что множество простых чисел конечно. Тогда элементы его можно занумеровать числами отрезка натурального ряда. Пусть – все простые числа и других простых чисел нет. Рассмотрим число

.

Число п является натуральным и, значит, должно принадлежать одному из трех вышеупомянутых классов. Но I кл., так как п > 1; II кл., так как п больше любого простого числа p_i (i = 1, 2, ..., k). Остается предположить, что III кл., то есть n – составное число. Тогда, по теореме 16, п должно делиться хотя бы на одно из простых чисел p_i (i = 1, 2, ..., k). Пусть , 1 ≤s ≤ k. Рассматривая равенство (10) замечаем, что в нем ,, а значит, по теореме 2 о делимости разности,, что невозможно. Полученное противоречие доказывает теорему.

2. Поскольку множество простых чисел бесконечно, то самого большого простого числа нет. Однако математики старались и стараются до сих пор обнаружить простоту тех или иных больших чисел. К концу прошлого века наибольшим известным простым числом было 39-значное число 2¹²⁷ – 1. В 50-60-х годах нашего столетия с помощью ЭВМ было найдено несколько новых простых чисел-гигантов.

До конца 70-х годов наибольшим известным простым числом было число 2¹¹²¹³ – 1, имеющее в десятичной записи 3376 знаков. В 1992 году англичане установили простоту числа, состоящего из 227832 знаков. Затем американцы в течение двух лет с помощью самых высокопроизводительных на то время ЭВМ анализировали более четверти миллиона больших чисел и открыли простое число 2⁸⁵⁹⁴³³ – 1, которое содержит в записи 258716 знаков. Чтобы представить это число нагляднее, заметим, что для записи его через принтер понадобилось 8 больших газетных страниц. Это число является самым большим из известных нам простых чисел.

Некоторые пары простых чисел отличаются друг от друга лишь на 2 единицы. Например: 3 и 5; 11 и 13; 17 и 19; 29 и 31 и т.д. Такие пары простых чисел называют близнецами. Есть гипотеза о том, что существует бесконечно много пар близнецов.

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

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

Доказательство. Рассмотрим k последовательно идущих в натуральном ряду чисел:

(k + 1)! + 2; (k + 1)! + 3; (k + 1)! + 4; ... ; (k + 1)! + (k + 1).

Легко заметить, что все эти числа составные. Действительно, первое из них делится на 2, второе – на 3, третье (последнее) – на k + 1. Теорема доказана.

Для составления таблиц простых чисел существуют различные приемы. Наиболее известный из них – «решето Эратосфена» – был предложен в III в. до н.э. древнегреческим ученым Эратосфеном и состоит в следующем.

Пусть требуется составить таблицу простых чисел, не превосходящих п. Для определенности положим п = 50, хотя в любом случае рассуждения проводятся аналогично.

Выпишем все натуральные числа от 1 до 50 включительно. Затем вычеркнем из этого списка 1, так как 1, по определению, не является простым числом. Первое из оставшихся чисел – 2 – число простое. Выделим его, а все кратные ему числа (это четные числа) вычеркнем. Первое из оставшихся чисел – 3 – число простое. Выделим его, а все кратные ему числа вычеркнем. При этом некоторые из чисел окажутся вычеркнутыми ранее. Повторяя этот процесс, через конечное число шагов мы отсеем все составные числа, а простые окажутся выделенными.

Этот прием получил название «решето» потому, что во времена Эратосфена писали острой палочкой на восковых дощечках. Эратосфен выколол составные числа, в результате получилась дощечка, похожая на решето.

Всвязи с описанным процессом возникает вопрос: на каком этапе можно прекратить вычисления и сделать вывод о том, что все оставшиеся числа будут простыми? Ответ на этот вопрос дает теорема итальянского математика Фибоначчи (1170-1228 гг.).

Теорема 19. Если натуральное число п не имеет простых делителей р ≤ , топ – простое число.

Доказательство. Рассуждая методом от противного, предположим, что условие теоремы выполнено, но п – составное число. Тогда п = ab, где 1 < a < п, 1 < b < п. Числа а и b не могут быть одновременно больше, чем , так как тогда аb было бы больше, чем п. Пусть, например, а ≤ . Посколькуа > 1, то, по теореме 16, оно имеет простой делитель р, то есть и. Тогда, по транзитивности отношения делимости, , гдер ≤ а ≤ . Но это противоречит условию теоремы, так как п не имеет простых делителей р ≤ . Теорема доказана.

Следует отметить тот факт, что многие математики предлагали ряд способов, рассчитанных на уменьшение объема выкладок при установлении простоты чисел. Примером служит теорема Софии Жермен (Франция, 1776-1831 гг.).

Теорема 20. Число п⁴ + 4 при п > 1 всегда составное.

Доказательство. Преобразуем число п⁴ + 4 тождественно: п⁴ + 4 = п⁴ + 4 + 4п² – 4п² = (п⁴ + 4п² + 4) – 4п² = (п² + 2)² – 4п² = (п² + 2 – 2п)(п² + 2 + 2п).

Очевидно, что число п² + 2n + 2 > 2 при любом натуральном п > l. Аналогично, п² – 2п + 2 > 2 при п² – 2п > 0, или (п – 2)п > 0. Так как п > 1, то п – 2 ≥ 0 и неравенство (п – 2)п ≥ 0 выполняется тождественно.

Итак, число п⁴ + 4 представимо в виде произведения двух множителей, каждый из которых есть натуральное число, большее или равное 2. Следовательно, число п⁴ + 4 составное и теорема доказана.

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

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

Доказательство проведем методом математической индукции по числу множителей. Сначала рассмотрим произведение двух множителей a₁ и a₂. Пусть . Здесь возможны два случая: или . Если , то утверждение доказано. Если a₁ не делится на р, то НОД(a₁;р) = 1, поскольку простое число взаимно просто со всеми не делящимися на него числами. Но если и (a₁;p) = 1, то, по теореме 12, .

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

.

Но для двух множителей теорема доказана, и значит, одно из чисел – m или a_k – должно делиться на р. Если , то теорема доказана. Если, то, по предположению индукции, хотя бы одно из чиселделится нар. Все условия метода математической индукции выполнены, и теорема полностью доказана.

Теорема 22. (Основная теорема арифметики) Всякое натуральное число п > 1 является либо простым, либо разлагается в произведение простых чисел, причем единственным образом с точностью до порядка следования множителей.

Доказательство. Докажем сначала существование разложения. Доказательство проведем методом математической индукции.

Очевидно, что для п = 2 разложение на простые множители существует, поскольку 2 есть простое число.

Предположим, что разложение на простые множители существует для всех натуральных чисел п < k, где k – некоторое произвольно выбранное натуральное число. Докажем, что и для числа n = k существует такое разложение.

Если k – простое число, то для него существование разложения можно считать доказанным. Если же k – число составное, то его можно представить в виде произведения:

k = а · b, где a < k и b < k. (11)

По предположению индукции, для чисел а и b разложение существует, то есть

и , (12)

где – простые числа. Подставляя разложения (12) в равенство (11), получим разложение числаk в произведение простых множителей:

. (13)

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

Докажем единственность разложения.

Для простого числа п = 2 указанное представление единственно.

Предположим, что для всех натуральных чисел п < k разложение на простые множители единственно. Докажем единственность разложения для числа n = k.

Пусть наряду с разложением (13) имеется второе разложение числа k:

, (14)

где – простые числа.

Из равенств (13) и (14) получаем равенство

. (15)

Левая часть равенства (15) делится на простое число р₁. Следовательно, и правая часть тоже делится на р₁. Согласно теореме 21, хотя бы один из множителей произведения должен делиться нар₁. Общность рассуждений не нарушится, если будем считать, что . Так какq₁ – простое число и р₁ > 1, то q₁ = р₁.

Далее, на основании ассоциативного закона умножения из равенства (15) следует равенство

. (16)

Так как числа именьше, чемk, то, по предположению индукции, из равенства (16) следует, что р₂ = q₂, , р₃ = q₃, …, p_s = q_t, s = t. Таким образом, в равенстве (15)

p₁ = q₁, р₂ = q₂, …, p_s = q_t, (s = t),

а значит, разложение числа k на простые множители единственно. Основная теорема арифметики доказана.

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

, (17)

Определение 8. Представление составного числа п в виде (17), где простые числа расположены в порядке возрастания , называетсяканоническим разложением, или канонической формой записи числа п.

На практике каноническое разложение числа п находится следующим образом. Проверяем, делится ли число п на различные простые числа: 2, 3, 5, 7,... в порядке их возрастания. Как только встретится первое простое число р_i, являющееся делителем числа п, то п следует разделить на р_i, а частное снова испытывать на делимость простыми числами, причем испытания следует начинать с числа р_i и т.д. Если при испытании окажется, что п не имеет простых делителей , то, согласно теореме Фибоначчи (теорема 19), п – простое число.

Пример. Найти каноническое разложение числа 9702.

Процесс разложения числа на простые множители записывают обычно следующим образом:

Ответ: 9702 = 2 · 3² · 7² · 11.

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

, ,

в которых некоторые из чисел и могут быть нулями.

Несложно заметить, что

НОД(а; b) = , (18)

HOК(а; b) = . (19)

Справедливость этих равенств вытекает из теорем 7 и 14, соответственно. Формулы (18) и (19) легко обобщаются на случай п чисел. Если даны числа , имеющие канонические разложения:

(20)

то НОД и НОК этих чисел представляются выражениями:

НОД,

НОК.