О. ОРЕ - Приглашение в теорию чисел
Рис 13.
Если мы проведем n радиусов, соединяющих центр окружности с вершинами, то получим n центральных углов величиной
1/n 360°
каждый. Если можно построить угол, имеющий эту величину, то можно построить и этот n-угольник.
Древние греки очень хотели найти методы построения правильных многоугольников с помощью циркуля и линейки. Разумеется, они умели строить простейшие из них — равносторонний треугольник и квадрат. С помощью повторного деления пополам центрального угла они могли также построить правильные многоугольники с
4, 8, 16, 32…,
3, 6, 12, 24…
вершинами. Кроме того, они умели строить правильный пятиугольник, и следовательно, также правильные многоугольники с
5, 10, 20, 40…
вершинами. Был также получен еще один тип правильного многоугольника. Центральный угол в правильном 15-угольнике равен
1/15 360° = 24°,
и он может быть получен с помощью утла в 72°, соответствующего правильному пятиугольнику, и угла в 120°, соответствующего правильному треугольнику, если удвоить первый угол и вычесть из него второй. Следовательно, мы можем построить правильные многоугольники с 15, 30, 60, 120… сторонами.
В таком состоянии проблема оставалась до 1801 года, когда вышла работа по теории чисел молодого немецкого математика К. Ф. Гаусса (1777–1855) «Арифметические исследования». Она открыла новую эпоху в математике. Гаусс превзошел греческих геометров не только в том, что указал метод построения циркулем и линейкой правильного 17-угольника, но и пошел гораздо дальше. Для всех чисел n он определил, какие n-угольники могут быть построены таким образом, а какие нет. Сейчас мы опишем результаты, полученные Гауссом.
Выше мы отмечали, что из правильного n-угольника можно получить правильный 2n-угольник, деля каждый центральный угол пополам. С другой стороны, из 2n-угольника можно получить n-угольник, используя лишь каждую вторую вершину. Это показывает, что достаточно провести поиск правильных многоугольников, которые могут быть построены с помощью циркуля и линейки, только среди многоугольников с нечетным числом вершин. Гаусс доказал, что правильный n-угольник с нечетным числом вершин может быть построен с помощью циркуля и линейки тогда, и только тогда, если число n является простым числом Ферма или произведением нескольких различных простых чисел Ферма.
Что это нам дает для небольших значений n? Очевидно, что 3-угольник и 5-угольник могут быть построены, в то время как 7-угольник не может, так как 7 не является простым числом Ферма. Не может быть построен и 9-угольник, так как 9 = 3 • 3 является произведением двух равных простых чисел Ферма.
Открытие Гаусса, естественно, возродило интерес к числам Ферма (2.3.1). За последнее столетие были предприняты поистине героические поиски, вручную, без помощи машин, новых простых чисел Ферма. В настоящее время эти вычисления продолжаются со все возрастающей скоростью с помощью ЭВМ. Однако до сих пор результаты были отрицательными. Ни одного нового простого числа Ферма не было найдено и сейчас многие математики склонны считать, что их больше нет.
Система задач 2.3.
1. Найдите все нечетные числа n < 100, для которых можно построить правильный n-угольник.
2. Как построить правильный 51-угольник, имея правильный 17-угольник?
3. Если не существует простых чисел Ферма, кроме выше указанных пяти, то сколько существует правильных n-угольников (n нечетно), которые могут быть построены циркулем и линейкой? Каково то наибольшее нечетное n, для которого может быть построен правильный n-угольник?
§ 4. Решето Эратосфена
Как мы уже говорили, существуют таблицы простых чисел, простирающиеся до очень больших чисел. Как можно было бы подступиться к составлению такой таблицы? Эта задача была, в известном смысле, решена (около 200 г. до н. э.) Эратосфеном, математиком из Александрии. Его схема состоит в следующем: напишем последовательность всех целых чисел от 1 до числа, которым мы хотим закончить таблицу:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
2 2 2 3 2 2 2 3
Начнем с простого числа 2. Будем выбрасывать каждое второе число, начиная с 2 (кроме самого числа 2), т. е. чётные числа 4, 6, 8, 10 и т. д., подчеркивая каждое из них. После этой операции первым неподчёркнутым числом будет число 3. Оно простое, так как не делится на 2. Оставив число 3 неподчёркнутым, будем подчеркивать каждое третье число после него, т. е. числа 6, 9, 12, 15…; некоторые из них уже были подчеркнуты, поскольку они являются чётными. На следующем шаге первым неподчёркнутым числом окажется число 5; оно простое, так как не делится ни на 2, ни на 3. Оставим число 5 неподчёркнутым, но подчеркнем каждое пятое число после него, т. е. числа 10, 15, 20, 25…; как и раньше, часть из них уже оказалась подчёркнутой. Теперь — наименьшим неподчёркнутым числом окажется число 7. Оно простое, так как не делится ни на одно из меньших его простых чисел 2, 3, 5. Повторяя этот процесс, мы в конце концов получим последовательность неподчёркнутых чисел; все они (кроме числа 1) являются простыми.
Этот метод отсеивания чисел известен как «решето Эратосфена». Любая таблица простых чисел создается по этому принципу решета. В действительности, можно продвинуться гораздо дальше по ряду простых чисел, если использовать для их хранения память ЭВМ. Подобным образом, в Научно-исследовательской лаборатории Лос-Аламоса были получены все простые числа до 100 000 000.
Небольшое изменение метода решета позволит нам получить большую информацию. Предположим, что всякий раз, впервые подчеркивая числа, мы будем подписывать под ним простое число, с помощью которого оно отсеивается. Тогда 15 и 35 были бы записаны как
15, 35
3 5
и т. д., как это показано на последовательности, выписанной выше. Таким образом, мы не только указали простые числа, но и для каждого составного числа привели наименьшее простое число, являющееся его делителем. Такой список чисел называется таблицей делителей. Таблица делителей является более сложной, чем таблица простых чисел. Чтобы немного упростить ее, обычно из нее исключают те составные числа, у которых простые делители малы, например, 2, 3, 5, 7. Самая большая такая таблица была вычислена на ЭВМ Д. X. Лемером и содержит все числа, вплоть до 10 000 000.
Как мы видели, решето Эратосфена может быть использовано для построения таблиц простых чисел и таблиц делителей. Однако оно может быть использовано и для теоретических исследований. Многие важные результаты в современной теории чисел были получены методом решета. Приведем результат, известный еще Евклиду:
Существует бесконечное число простых чисел.
Доказательство. Предположим, что существует только k простых чисел:
2, 3, 5…, рk.
Тогда в решете не оказалось бы неподчёркнутых чисел, больших, чем рk. Но это невозможно, так как произведение этих простых чисел
р = 2 • 3 • 5 • … • рk
будет отсеиваться k раз, по разу для каждого простого числа, поэтому следующее число р + 1 не может быть подчеркнуто ни для одного из них.
Система задач 2.4.
1. Составьте таблицы простых чисел для каждой из сотен: 1—100, 101–200, … 901—1000.
2. Попытайтесь определить количество простых чисел в диапазоне 10001—10100.
ГЛАВА 3
ДЕЛИТЕЛИ ЧИСЕЛ
§ 1. Основная теорема о разложении на множители
Любое составное число с может быть записано в виде произведения с = ab, причем ни один из делителей не равен 1 и каждый из них меньше, чем с; например,
72 = 8 • 9, 150 = 10 • 15.
При разложении числа с на множители один из них, и даже оба (а и b) могут оказаться составными. Если а — составное, то разложение на множители можно продолжить:
а = a1 • a2, с = a1 • a2 • b.
Примерами этого могут служить рассмотренные выше числа
72 = 2 • 4 • 9, 150 = 2 • 5 • 15.
Этот процесс разложения на множители можно продолжить до тех пор, пока он не закончится; это должно произойти, так как делители становятся все меньше и меньше, но не могут стать единицей. Когда ни один из делителей нельзя уже будет разложить на множители, то все делители будут простыми числами.
