С чего начинается математика? Конечно, со счета: один, два, три, четыре, пять..., или 1, 2, 3, 4, 5…, n.
При счете мы получаем ряд чисел, каждое последующее из которых образуется путем прибавления к предыдущему единицы. Математики называют такие числа натуральными, а их ряд – множеством натуральных чисел. Обозначается оно латинской буквой «N».
Множество натуральных чисел бесконечно. Оно имеет начало – «1», но не имеет конца, поскольку нет такого числа, к которому нельзя было бы прибавить единицу и не получить при этом большее число.
Большинство натуральных чисел отличается «примерным» поведением. Каждое второе число – четное, каждое третье – кратно трем, каждое четвертое делится на четыре и т.д. Но время от времени в этом стройном ряду появляются числа-«хулиганы»:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, …
От всех прочих они отличаются тем, что делятся только на себя и единицу. Такие числа называются простыми. Натуральные числа, имеющие больше двух делителей, называют составными. Исключением является «единица». Число «1» делится только на себя и не относится ни к простым, ни к составным.
Основная теорема арифметики
Основная теорема арифметики сформулирована более 2 тыс. лет назад Евклидом и звучит так:
«Любое натуральное число может быть представлено единственным образом в виде произведения простых множителей»
Что это значит? Как мы уже убедились, любое натуральное число имеет делители, а это значит, что его можно записать в виде произведения этих делителей. Например, 18 делится без остатка на 2 и 9. 9, в свою очередь, можно представить в виде произведения двух троек. То есть, 18 = 2 х 9 = 2 х 3 х 3.
Мы разложили число 18 на простые множители. Основная теорема арифметики утверждает, что в виде произведения простых множителей можно представить любое сложное число из множества натуральных чисел.
Простые числа, таким образом, являются теми «кирпичами», из которых строится здание математики. Все сложные числа являются произведением простых.
Проблема неупорядоченности
Простые числа в отличие от составных в ряду натуральных чисел появляются совершенно неожиданно. В 3-ем веке до н.э. александрийский математик Евклид доказал, что множество простых чисел бесконечно, и самого большого простого числа не существует. Таким образом, составить для них исчерпывающий список или таблицу невозможно. Понятно только, что все они, кроме двойки, будут нечетными, поскольку четные имеют больше двух делителей.
При бесконечности множества простых чисел его неупорядоченность стала серьезной научной проблемой. Решить её пытались Евклид, Ферма, Эйлер, Гаусс, Риман и не только они, но до сих пор никто из математиков в этом не преуспел. Тот, кому удастся это сделать, гарантировано получит Абелевскую премию.
Решето Эратосфена
Поиск простых чисел также оказался сложной, все-таки разрешимой задачей. Один из самых популярных методов обнаружения таких чисел носит название «решето» Эратосфена, древнегреческого математика, астронома и географа из Кирены, жившего в третьем веке до н.э. в Александрии Египетской.
Продемонстрируем метод на промежутке натуральных чисел от 1 до 100. Нам понадобится соответствующая таблица. Сразу вычеркиваем не относящуюся к составным числам «единицу». Далее последовательно проверяем каждое оставшееся число на предмет делимости на простые натуральные числа, начиная с двойки, – «просеиваем» их через решето с разной величиной ячеек, вначале 2, потом 3, 5, 7… Найденные составные числа при этом вычеркиваем.
Из таблицы сразу удаляются все четные числа, далее числа, кратные трем, пяти, семи…
В нашей таблице остались только простые числа. Заметим, для их выявления нам не понадобилось проверять кратность чисел всем числам в промежутке от 1 до 100. Мы остановились на числе 7, последнем простом числе из первого десятка чисел нашего множества.
Число 10 равно квадратному корню из 100. Отсюда правило «решета»: чтобы найти все простые числа, меньшие заданного числа N, нужно «просеять» все числа, которые меньше или равны квадратному корню из N.
Что это значит? Увеличим наш промежуток на 100 единиц, т.е. до двухсот (1 – 200). Для нахождения простых чисел в нем достаточно будет "решета" с ячейками от 2 до 14-ти, поскольку квадратный корень из двухсот приблизительно равен 14-ти.