Простые числа и основная теорема арифметики

Краткое содержание

Этот урок изучает простые числа, атомы умножения натуральных чисел. Он доказывает, что всякое натуральное число, большее $1$ , имеет простой делитель, излагает решето Эратосфена и объясняет, почему просеивать достаточно до квадратного корня, а также вслед за Евклидом доказывает, что простых чисел бесконечно много. Затем он доказывает лемму Евклида, согласно которой простое число, делящее произведение, делит один из его множителей, а с её помощью и основную теорему арифметики: всякое натуральное число, большее $1$ , записывается в виде произведения простых чисел единственным образом. Из разложения на простые множители выводятся число делителей натурального числа, характеристика полных квадратов и иррациональность квадратного корня из всякого натурального числа, не являющегося полным квадратом.

Цели обучения

Отличать простые числа от составных и доказывать, что всякое натуральное число, большее $1$ , имеет простой делитель.
Применять решето Эратосфена и обосновывать, почему достаточно вычёркивать кратные простых чисел, не превосходящих квадратного корня из верхней границы.
Доказывать бесконечность множества простых чисел, лемму Евклида, а также существование и единственность разложения на простые множители.
Использовать разложение на простые множители, чтобы подсчитывать и перечислять делители, распознавать полные квадраты и доказывать иррациональность квадратных корней.

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

В уроке о делимости и делении с остатком мы видели, что всякое натуральное число $n$ делится на $1$ и на само себя. Некоторые натуральные числа не имеют других делителей, кроме этих двух; это те детали, из которых умножением составляются все остальные.

Определение (простое число). Натуральное число $p$ называется простым, если $p > 1$ и его единственными делителями являются $1$ и $p$ . Натуральное число $n > 1$ , не являющееся простым, называется составным: оно записывается в виде $n = ab$ , где $1 < a < n$ и $1 < b < n$ . Число $1$ не является ни простым, ни составным.

Простых чисел, меньших $50$ , пятнадцать:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

Число $2$ является единственным чётным простым числом, поскольку всякое другое чётное число имеет делитель $2$ , отличный от $1$ и от самого этого числа. Исключение числа $1$ не является прихотью определения: если бы $1$ было простым, разложение на простые множители перестало бы быть единственным, поскольку $6 = 2 \cdot 3 = 1 \cdot 2 \cdot 3$ , и центральную теорему этого урока пришлось бы формулировать с исключением.

Принцип вполне упорядоченности

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

Всякое натуральное число, большее 1, имеет простой делитель

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

УтверждениеНаименьший делитель, больший 1, является простым

Всякое натуральное число $n > 1$ имеет простой делитель: наименьший делитель числа $n$ , больший $1$ , является простым. Если, кроме того, $n$ составное, то его наименьший простой делитель $p$ удовлетворяет неравенству $p^2 \leq n$ . Рисунок отмечает на прямой делители числа $n = 91 = 7 \cdot 13$ .

Доказательство

$\dato{D}{D = \{ d \in \mathbb{N} : d \mid n \wedge d > 1 \}}, \quad n \in D, \quad m = \min D$
Множество делителей числа $n$ , больших $1$ , не пусто, поскольку содержит само $n$ ; по принципу вполне упорядоченности оно имеет наименьший элемент $m$ .
$a \mid m \wedge m \mid n \rightarrow \resaltar{a \in D}, \quad \resaltar{a < m}$
Если бы $m$ было составным, $m = ab$ , где $1 < a < m$ , то множитель $a$ делил бы $m$ и, по транзитивности делимости, $n$ : он был бы элементом $D$ , меньшим $m$ , вопреки выбору $m$ . Следовательно, $m$ простое.
$\dato{k}{n = pk, \quad k \in D}$
Пусть теперь $n$ составное, и пусть $p$ есть его наименьший простой делитель, то есть наименьший элемент $D$ . Запишем $n = pk$ ; поскольку $n$ не простое, $k \neq 1$ , и $k$ также делит $n$ .
$p^2 = p \cdot p \leq \resaltar{p \cdot k} = n$
В силу минимальности $p$ имеем $k \geq p$ , и по монотонности умножения получаем оценку.

Следовательно, чтобы выяснить, является ли натуральное число $n$ простым, достаточно испробовать простые числа $p$ , для которых $p^2 \leq n$ : если ни одно из них его не делит, то $n$ простое. Например, для $221$ достаточно испробовать простые числа до $13$ , поскольку $17^2 = 289 > 221$ : оно не делится ни на $2$ , ни на $3$ , ни на $5$ , ни на $7$ , ни на $11$ , но делится на $13$ , и $221 = 13 \cdot 17$ . Напротив, $211$ не делится ни на одно из простых чисел $2$ , $3$ , $5$ , $7$ , $11$ и $13$ , а поскольку $17^2 = 289 > 211$ , число $211$ простое.

Далее в этом уроке

Решето Эратосфена
Простых чисел бесконечно много
Лемма Евклида
Основная теорема арифметики
Следствия разложения на простые множители
Делители натурального числа
Полные квадраты
Иррациональные квадратные корни
Решённые задачи
Слабый криптографический ключ
Наименьшее натуральное число с двенадцатью делителями
Сто подряд идущих составных чисел
Бесконечно много простых чисел, дающих остаток 3 при делении на 4
Совершенные числа Евклида
Задачи для самостоятельного решения
Простые числа вида $n^4 + 4$
Двери в коридоре
Общий делитель квадратов простых чисел
Удвоенное число есть квадрат, утроенное есть куб
Простые числа Мерсенна