Как доказать что число составное без перебора делителей
Простые и составные числа, определения, примеры, таблица простых чисел, решето Эратосфена
В статье рассматриваются понятия простых и составных чисел. Даются определения таких чисел с примерами. Приводим доказательство того, что количество простых чисел неограниченно и произведем запись в таблицу простых чисел при помощи метода Эратосфена. Будут приведены доказательства того, является ли число простым или составным.
Простые и составные числа – определения и примеры
Простые и составные числа относят к целым положительным. Они обязательно должны быть больше единицы. Делители также подразделяют на простые и составные. Чтобы понимать понятие составных чисел, необходимо предварительно изучить понятия делителей и кратных.
Составными числами называют целые числа, которые больше единицы и имеют хотя бы три положительных делителя.
Единица не является ни простым ни составным числом. Она имеет только один положительный делитель, поэтому отличается от всех других положительных чисел. Все целые положительные числа называют натуральными, то есть используемые при счете.
Простые числа – это натуральные числа, имеющие только два положительных делителя.
Составное число – это натуральное число, имеющее более двух положительных делителей.
Натуральные числа, которые не являются простыми, называют составными.
Таблица простых чисел
Для того, чтобы было проще использовать простые числа, необходимо использовать таблицу:
Рассмотрим теорему, которая объясняет последнее утверждение.
Наименьший положительный и отличный от 1 делитель натурального числа, большего единицы, является простым числом.
Простых чисел бесконечно много.
Видно, что может быть найдено любое простое число среди любого количества заданных простых чисел. Отсюда следует, что простых чисел бесконечно много.
Решето Эратосфена
Данный способ неудобный и долгий. Таблицу составить можно, но придется потратить большое количество времени. Необходимо использовать признаки делимости, которые ускорят процесс нахождения делителей.
Перейдем к формулировке теоремы.
Данное число простое или составное?
Перед решением необходимо выяснять, является ли число простым или составным. Зачастую используются признаки делимости. Рассмотрим это на ниже приведенных примере.
Доказать что число 898989898989898989 является составным.
Ответ: 11723 является составным числом.
Как определить простое число или нет
Простые числа – это числа, которые делятся только на себя и на 1; все остальные числа называются составными числами. Существует множество способов определения того, является ли число простым. Некоторые способы являются относительно простыми, но они не подходят для больших чисел. Другие способы, применимые для больших чисел, фактически представляют собой вероятностные алгоритмы, которые иногда ошибочно характеризуют число как простое или составное.
Метод 1 Перебор делителей
Перебор делителей – самый легкий способ определить простоту числа. В случае малых чисел это, пожалуй, также и самый быстрый способ. Он основан на определении простого числа: число является простым, если оно не имеет делителей кроме самого себя и единицы.
Метод 2 Тест Ферма
В 1640 году французский математик Пьер Ферма впервые сформулировал теорему (малая теорема Ферма), которая используется при определении простоты числа. Фактически, тест Ферма служит для определения составных чисел, а не простых. Этот тест с уверенностью определяет, является ли число составным, или определяет, что число «скорее всего» простое. Тест Ферма полезен в случаях, когда перебор делителей непрактичен и когда доступен список чисел, являющихся исключениями из теоремы.
Метод 3 Тест Миллера-Рабина
Тест Миллера-Рабина эффективно определяет, является ли число составным (и лучше обрабатывает исключения, такие как числа Кармайкла).
Условие задачи 2.30
Задача 2.30
Дан одномерный массив А, состоящий из натуральных чисел. Вывести на экран количество простых чисел в массиве.
Для начала напомню, что такое простые числа.
Простое число — это натуральное число, которое имеет ровно два различных натуральных делителя — единицу и самого себя.
То есть если число делится без остатка только на 1 и на самого себя, то такое число является простым.
Например, простыми числами являются 2, 3, 5 и т.п.
А вот 4 уже не является простым, так как делится без остатка не только на 1 и 4, но ещё и на 2.
Если вы подзабыли, что такое натуральное число, то см. здесь.
А теперь перейдём к задаче. По сути нам нужна программа, определяющая простые числа. А уж перебрать элементы массива в цикле и проверить их значения — это дело техники. Заодно мы можем не только подсчитать, но и вывести на экран простые числа массива.
Как определить простое число в Паскале
Алгоритм решения с подробным разбором приведу на Паскале. Решение на С++ можете посмотреть в примере программы на С++.
ВАЖНО!
На этом многие могут ошибиться. В определении сказано, что простое число имеет ровно два различных делителя. Следовательно, число 1 не является простым (также не является простым, так как ноль можно делить на любые числа).
Проверять, является ли число простым, будем с помощью функции, которую сами и создадим. Эта функция будет возвращать TRUE, если число простое.
В функции сначала будем проверять, не является ли число меньше двух. Если да, то это уже не простое число. Если же число равно 2 или 3, то оно является однозначно простым и делать какие-то дополнительные проверки не требуется.
А вот если число N будет больше трёх, то в этом случае в цикле будем перебирать все возможные делители, начиная от 2 до (N-1). Если на какой-то делитель число N делится без остатка, значит, это тоже не простое число. В этом случае мы прерываем цикл (потому что проверять дальше нет смысла), а функция возвращает FALSE.
Проверять, делится ли число на самоё себя нет смысла (поэтому цикл длится только до N-1).
Саму функцию здесь приводить не буду — посмотрите её в примерах программ.
В статье рассматриваются понятия простых и составных чисел. Даются определения таких чисел с примерами. Приводим доказательство того, что количество простых чисел неограниченно и произведем запись в таблицу простых чисел при помощи метода Эратосфена. Будут приведены доказательства того, является ли число простым или составным.
Простые и составные числа – определения и примеры
Простые и составные числа относят к целым положительным. Они обязательно должны быть больше единицы. Делители также подразделяют на простые и составные. Чтобы понимать понятие составных чисел, необходимо предварительно изучить понятия делителей и кратных.
Составными числами называют целые числа, которые больше единицы и имеют хотя бы три положительных делителя.
Единица не является ни простым ни составным числом. Она имеет только один положительный делитель, поэтому отличается от всех других положительных чисел. Все целые положительные числа называют натуральными, то есть используемые при счете.
Простые числа – это натуральные числа, имеющие только два положительных делителя.
Составное число – это натуральное число, имеющее более двух положительных делителей.
Натуральные числа, которые не являются простыми, называют составными.
Таблица простых чисел
Для того, чтобы было проще использовать простые числа, необходимо использовать таблицу:
Рассмотрим теорему, которая объясняет последнее утверждение.
Наименьший положительный и отличный от 1 делитель натурального числа, большего единицы, является простым числом.
Простых чисел бесконечно много.
Видно, что может быть найдено любое простое число среди любого количества заданных простых чисел. Отсюда следует, что простых чисел бесконечно много.
Решето Эратосфена
Данный способ неудобный и долгий. Таблицу составить можно, но придется потратить большое количество времени. Необходимо использовать признаки делимости, которые ускорят процесс нахождения делителей.
Перейдем к формулировке теоремы.
Данное число простое или составное?
Перед решением необходимо выяснять, является ли число простым или составным. Зачастую используются признаки делимости. Рассмотрим это на ниже приведенных примере.
Доказать что число 898989898989898989 является составным.
Ответ: 11723 является составным числом.
math4school.ru
Простые и составные числа
Немного теории
Простое число – это натуральное число, имеющее ровно два различных натуральных делителя: единицу и само себя. Все остальные натуральные числа, кроме единицы, называются составными. Таким образом, все натуральные числа больше единицы разбиваются на простые и составные. Изучением свойств простых чисел занимается теория чисел.
Приведём некоторые свойства простых чисел.
Основная теорема арифметики. Каждое натуральное число, большее единицы, представимо в виде произведения простых чисел, причём единственным способом с точностью до порядка следования сомножителей.
Простых чисел бесконечно много.
Если p – простое, и p делит a·b, то p делит a или b.
Mалая теорема Ферма. Если p – простое, a – натуральное, то a p – a делится на p.
Теорема Вильсона. Натуральное p > 1 является простым тогда и только тогда, когда (p – 1)! + 1 делится на p.
Постулат Бертрана. Если n > 1 – натуральное, то существует простое p, такое, что n 1 – целые взаимно простые числа, содержит бесконечно много простых чисел.
Теорема Ферма. Каждое простое число вида 4k + 1 есть сумма двух квадратов натуральных чисел.
Всякое простое число, большее 3, представимо в виде 6k + 1 или 6k – 1, где k – некоторое натуральное число.
Число, следующее за простым, не может быть квадратом или более высокой степенью с основанием, большим 2.
Число, предшествующее простому, не может быть кубом или более высокой нечётной степенью с основанием, большим 1.
Задачи с решениями
1. Три простых числа, каждое из которых больше 10, образуют арифметическую прогрессию. Докажите, что разность прогрессии делится на 6.
Все данные простые числа нечётные, поэтому их разность делится на 2. Покажем, что она делится и на 3. Пусть данные числа a, a + d, a + 2d. Ни одно из них не делится на 3, поэтому при делении на 3 даёт остаток или 1, или 2. Следовательно, по крайней мере, два из этих чисел дают при делении на 3 одинаковые остатки. Разность этих чисел, равная d или 2d, делится на 3. Поскольку 2 на 3 не делится, то d делится на 3. Итак, разность прогрессии, которая делится на взаимно простые числа 2 и 3, делится на 6, что и требовалось доказать.
2. Докажите, что для произвольного натурального числа n найдётся натуральное m такое, что nm + 1 – составное число.
Можно выбрать m = n + 2, тогда
nm + 1 = n(n + 2) + 1 = n 2 + 2n + 1 = (n + 1) 2
является составным числом.
3. Найдите все целые числа n, для которых модуль значения трёхчлена n 2 – 7n + 10 будет простым числом.
|n 2 – 7n + 10| = |n –2| · |n – 5|,
то следует искать такие n при которых один из множителей последнего произведения равен 1, а второй является простым числом. Этому требованию удовлетворяют n = 3 и n = 4.
4. Докажите, что если числа
а) m и m 2 + 2 простые, то число m 3 + 2 тоже простое;
б) р, р – 10, р + 10 простые, то число р – 2 тоже простое.
а) Любое простое число m, отличное от 3, можно представить в виде 3n+1 или в виде 3n–1, где n – некоторое натуральное число. В первом случае можно записать
m 2 + 2 = 9n 2 + 6n +3,
m 2 + 2 = 9n 2 – 6n +3,
Так как m > 2, то в любом случае число m 2 +2 больше 3 и делится на 3, а значит является составным. Следовательно, число m 2 +2 может быть простым, только если m = 3. В этом случае m 2 +2 = 11 – простое число, m 3 +2 = 29 – тоже простое число, что и требовалось доказать.
б) Так как р – 10 = (р – 1) – 9 и р + 10 = (р + 1) + 9, то числа р – 10 и р – 1 при делении на 3 имеют одинаковые остатки, и числа р + 10 и р + 1 при делении на 3 имеют одинаковые остатки.
Из трёх последовательных чисел р – 1, р, р + 1 одно и только одно делится на 3. С учётом выше сказанного, то же утверждение верно для чисел р – 10, р, р + 10. Так как эти числа простые, то р – 10 = 3 и р = 13, поэтому р – 2 = 11 – простое число, что и требовалось доказать.
5. Сколько раз входит двойка в разложение на простые множители произведения
Ответ на поставленный вопрос получим из следующих преобразований:
6. Найдите все простые p такие, что число p 2 + 11 имеет ровно 6 различных делителей (включая единицу и само число).
Если p > 5 и простое, то числа p – 1 и p + 1 оба четные, и одно из них кратно трем. Поэтому произведение (p – 1)(p + 1) делится на 12, следовательно, p 2 + 11 также делится на 12, а значит, имеет не менее семи делителей (6 делителей числа 12 и само число p 2 + 11 > 12 ). Осталось проверить p = 2 и p = 3.
Если p = 2, то p 2 + 11 = 2 2 + 11 = 15 имеет 4 делителя (1, 3, 5, 15).
Если p = 3, то p 2 + 11 = 3 2 + 11 = 20 имеет 6 делителей (1, 2, 4, 5, 10, 20).
7. Найти все натуральные числа n, для которых каждое из шести чисел
n + 1, n + 3, n + 7, n + 9, n + 13 и n + 15
Рассмотрим варианты. Для n = 1 число n + 3 = 4 составное.
Для n = 2 число n + 7 = 9 составное.
Для n = 3 число n + 1 = 4 составное.
Для n > 4 все наши числа больше 5 и по крайней мере одно из них делится на 5, так как числа 1, 3, 7, 9, 13 и 15 при делении на 5 дают соответственно остатки 1, 3, 2, 4, 3 и 0, то есть все возможные остатки, откуда следует, что и числа
n + 1, n + 3, n + 7, n + 9, n + 13 и n + 15
при делении на 5 дают все возможные остатки и, следовательно, хотя бы одно из них делится на 5 и как число, большее пяти (так как n > 4), является составным.
Но для n = 4 мы получаем простые числа 5, 7, 11, 13, 17 и 19.
8. Доказать, что каждое простое число вида 4k + 1 является длиной гипотенузы прямоугольного треугольника, стороны которого выражаются натуральными числами.
9. Сколькими способами можно раскрасить круг, разбитый на р равных секторов с помощью n красок, если р – простое число и каждый сектор раскрашиваем одной краской? Две раскраски, совпадающие при повороте круга, считаем одинаковыми.
Каждый сектор можно раскрасить в любой из n цветов, поэтому для круга с р секторами получим n p раскрасок, среди которых (n p – n) не одноцветных. Каждая из этих раскрасок поворотами переходит в (р – 1) одинаковую с ней, значит, существенно различных не одноцветных раскрасок будет (n p – n)/p, откуда общее число раскрасок равно n + (n p – n)/p.
10. Доказать, что для любого простого числа p > 5 уравнение х 4 + 4 x = p в целых числах не имеет решений.
Докажем, что если для некоторого целого значения х число
является целым, то это число либо не превосходит пяти, либо является составным.
Действительно, если х 4 + 4 0 4 + 4 1 = 5.
Если x = 2k (k – натуральное число), то число
f(x) = 2 4 k 4 + 4 2k = 2 4 ( k 4 + 4 2(k–1) )
Наконец, если x = 2k + 1 (k – натуральное число), то число
f(x) = x 4 + 4·4 2k = (x 4 + 4x 2 (2 k ) 2 + 4(2 k ) 4 ) – 4x 2 (2 k ) 2 =
= (x 2 + 2(2 k ) 2 ) 2 – (2·x·2 k ) 2 =
= (x 2 + 2·x·2 k + 2(2 k ) 2 )·( x 2 – 2·x·2 k + 2(2 k ) 2 ) =
= ((x + 2 k ) 2 + 2 2k )·((x – 2 k ) 2 + 2 2k )
так же является составным, поскольку каждый из двух сомножителей последнего произведения больше 1 (ибо 2 2k > 1 при k > 0).
Таким образом, если число p > 5 простое, то равенство х 4 + 4 x = p не выполняется ни при каких целых значениях х.
Задачи без решений
1. Известно, что р, р + 10, р + 14 – простые числа. Найдите число р.
2. Докажите, что число
3. Найдите все простые р для которых число р 2 + 14 так же будет простым числом.
4. Докажите, что уравнение х 2 + х + 1 = р·у имеет решение в целых числах (х, у) для бесконечного числа простых р.
5. Введём обозначение для суммы первых n простых чисел через Sn:
Докажите, что между числами Sn и Sn+1 всегда существует число, являющееся полным квадратом.
Лекция 8. 22.04.20.ПРОСТЫЕ И СОСТАВНЫЕ ЧИСЛА
Лекция 8. Простые и составные числа. Их свойства
Определение. Натуральное число, большее единицы, называется простым, если оно делится только на себя и на 1 (т. е. имеет ровно два разных делителя). Натуральное число называется составным, если оно имеет более 2 разных делителей.
Например, числа 2, 3, 5, 7, 11 – простые, а число 18 – составное (1, 2, 3, 6, 9, 18 – его делители). Число 1 имеет только один делитель и не является ни простым, ни составным.
Таким образом, множество целых неотрицательных чисел N0 можно разделить на четыре непересекающихся подмножества:
1) <0>– множество, состоящее из одного элемента, числа 0:;
2) <1>– множество, состоящее из одного элемента, числа 1;
1) Если простое число p делится на натуральное число q ≠ 1, то q совпадает с числом p (q = p).
Доказательство. Действительно, если бы число p делилось на q и не совпадало с числом q, то оно имело бы три делителя: 1, p, q, что противоречит определению простого числа. Поэтому p = q.
2) Если p и q – разные простые числа, то p не делится на q.
Доказательство. Поскольку p – простое число, то оно делится только на 1 и p. По условию p ≠ q и q – простое число, значит, q ≠ 1. Отсюда следует, что p не делится на q.
3) Всякое натуральное число a>1 имеет хотя бы один простой делитель, причем этот делитель наименьший.
Доказательство. Если число а – простое, то таким делителем числа а является само это число.
Последнее неравенство противоречит условию, что d – наименьший делитель числа а. Значит, допущение о том, что число d – составное, ошибочно.
Таким образом, наименьший делитель натурального числа а – всегда простое число.
Доказательство. Пусть число а – составное и d – его наименьший простой делитель (он существует на основании свойства 3).
Число 381 – составное, поскольку делится на 3 по признаку делимости.
Решето Эратосфена
Эратосфен – древний греческий ученый математик и астроном, который жил в III в. до н. э. Считают, что он первый составил таблицу простых чисел. В древности греки писали палочками на восковых досках. Записав некоторую последовательность натуральных чисел, Эратосфен прокалывал дырку, где стояли составные числа. Составные числа как бы «просеивались», а оставались только простые. Дощечка выглядела подобно решету. Отсюда, возможно, и название метода Эратосфена отсеивать составные числа.
Решение. Запишем последовательность натуральных чисел от 2 до 40.
Как доказать что число составное без перебора делителей
§ 1. Основная теорема о разложении на множители
Любое составное число с может быть записано в виде произведения с = ab, причем ни один из делителей не равен 1 и каждый из них меньше, чем с; например,
72 = 8 • 9, 150 = 10 • 15.
При разложении числа с на множители один из них, и даже оба (а и b) могут оказаться составными. Если а — составное, то разложение на множители можно продолжить:
Примерами этого могут служить рассмотренные выше числа
72 = 2 • 4 • 9, 150 = 2 • 5 • 15.
Этот процесс разложения на множители можно продолжить до тех пор, пока он не закончится; это должно произойти, так как делители становятся все меньше и меньше, но не могут стать единицей. Когда ни один из делителей нельзя уже будет разложить на множители, то все делители будут простыми числами.
Таким образом мы показали, что
Каждое целое число, большее 1, является простым числом или произведением простых чисел.
Последовательное разложение числа на множители может быть выполнено многими способами. При этом можно использовать таблицу делителей. Сначала найдем наименьшее простое число р1, делящее число с, так что с = р1с1. Если с1 — составное число, то по таблице делителей найдем наименьшее простое число р2, делящее с1, так что
Затем найдем наименьший простой делитель числа с2 и т. д.
Но главное здесь то, что независимо от способа разложения числа на простые множители результат всегда будет одним и тем же, различаясь лишь порядком их записи, т. е. любые два разложения числа на простые множители содержат одни и те же простые числа; при этом каждое простое число содержится одинаковое число раз в обоих разложениях.
Этот результат мы можем кратко выразить следующим образом:
разложение числа на простые множители единственно.
Возможно, что вы так часто слышали об этой так называемой «основной теореме арифметики» и пользовались ею, что она представляется вам очевидной, но это совсем не так. Эта теорема может быть доказана несколькими различными способами, однако ни один из них не тривиален. Здесь мы приведём доказательство, используя способ «от противного», который часто называют его латинским названием reductio ad absurdum (приведением к абсурду). Этот способ заключается в следующем: предположив ложность теоремы, которую нужно доказать, показывают, что это предположение приводит к противоречию.
Доказательство. Предположим, что наша теорема о единственности разложения на множители неверна. Тогда должны существовать числа, имеющие по крайней мере два различных разложения на простые множители. Выберем из них наименьшее и обозначим его через с0. Для небольших чисел, скажем, меньших 10, истинность теоремы можно установить прямой проверкой. Число с0 имеет наименьший простой множитель р0, и мы можем записать:
Вообще при разложении числа n на множители аналогично можно собирать одинаковые простые множители в виде степеней и записывать
Если мы знаем вид (3.2.1) для числа, то мы сможем тотчас же ответить на некоторые вопросы об этом числе.
Например, если мы захотим, то можем узнать, какие числа делят число n. Возьмем для примера рассмотренное выше число 3600. Предположим, что число d является одним из его делителей, т. е.
Приведенное разложение на простые множители показывает, что единственными числами среди множителей числа d будут лишь 2, 3, 5. Кроме того, число 2 может содержаться не более 4 раз, а числа 3 и 5 не более, чем по 2 раза каждое. Итак, мы видим, что возможными делителями числа 3600 будут числа вида
при этом показатели степени могут принимать значения:
Так как эти значения могут сочетаться всеми возможными способами, то число делителей равно
(4 + 1)•(2 + 1)•(2 + 1) = 5 • 3 • 3 = 45.
Для любого числа n, разложение которого на простые множители дается формулой (3.2.1), положение точно такое же. Если число d является делителем числа n, т. е.
то единственными простыми числами, на которые может делиться число d, будут только те, которые делят число n, а именно: p1…, рr. Таким образом, мы можем записать разложение числа d на простые множители в виде
Простое число p1 может содержаться не более α1 раз, как и в самом числе n; аналогично — для p2 и других простых чисел. Это значение для числа δ1 мы можем выбрать α1 + 1 способом:
аналогично и для других простых чисел. Так как каждое из α1 + 1 значений, которые может принимать число δ1, может сочетаться с любым из α2 + 1 возможных значений числа δ2 и т. д., то мы видим, что общее число делителей числа n задается формулой
2. Найдите количество делителей у следующих чисел: 60, 366, 1970, вашего почтового индекса.
3. Какое натуральное число (или числа), не превосходящее 100, имеет наибольшее количество делителей
§ 3. Несколько задач о делителях
Существует единственное число n = 1, которое имеет только один делитель. Числами с ровно двумя делителями являются простые числа n = р: они делятся на 1 и на р. Наименьшим числом, имеющим два делителя, является, таким образом, р = 2.
Исследуем числа, имеющие ровно 3 делителя. В соответствии с (3.2.3) имеем
Так как 3 — простое число, то справа может существовать лишь один множитель, не равный 1. Отсюда r = 1, a α1 = 2. Таким образом,
Наименьшим числом с 3 делителями является n = 2 2 = 4. Это соображение, примененное к общему случаю, когда число делителей q является простым числом, позволяет получить, что
наименьшим из таких чисел является
Рассмотрим следующий случай, когда существует ровно 4 делителя. Тогда соотношение
возможно только тогда, когда
Это приводит к двум возможностям:
наименьшее число с 4 делителями — это n = 6.
В том случае, когда имеется 6 делителей, должно выполняться соотношение
что возможно лишь тогда, когда
Это дает две возможности:
при этом наименьшее значение имеет место в последнем случае, когда
Этот метод можно использовать для вычисления наименьших натуральных чисел, имеющих любое заданное количество делителей.
Существуют таблицы, указывающие количество делителей для различных чисел. Они начинаются следующим образом:
Вы легко можете ее самостоятельно продолжить.
Будем говорить, что натуральное число n является сверхсоставным, если количество делителей у каждого числа, меньшего n, меньше, чем количество делителей у числа n. Глядя на нашу небольшую таблицу, мы видим, что
являются первыми пятью сверхсоставными числами. О свойствах этих чисел известно еще очень мало.
1. Взвод из 12 солдат может маршировать 6-ю различными способами: 12 × 1, 6 × 2, 4 × 3, 3 × 4, 2 × 6, 1 × 12. Какую наименьшую численность должны иметь группы людей, которые могут маршировать 8, 10, 12 и 72 способами?
2. Найдите наименьшие натуральные числа, имеющие: а) 14 делителей, б) 18 делителей ив) 100 делителей.
3. Найдите два первых сверхсоставных числа, следующих за числом 12.
4. Охарактеризуйте все натуральные числа, количество делителей которых является произведением двух простых чисел.
§ 4. Совершенные числа
Нумерология (или гематрия, как ее иногда еще называют) была распространенным увлечением у древних греков. Естественным объяснением этому является то, что числа в Древней Греции изображались буквами греческого алфавита, и поэтому каждому написанному слову, каждому имени соответствовало некоторое число. Люди могли сравнивать свойства чисел, соответствующих их именам.
Делители или аликвотные части[6] чисел играли важную роль в нумерологии. В этом смысле идеальными, или, как их называют, совершенными числами являлись такие числа, которые составлялись из своих аликвотиых частей, т. е. равнялись сумме своих делителей. Здесь следует отметить, что древние греки не включали само число в состав его делителей.
Наименьшим совершенным числом является 6:
За ним следует число 28:
28 = 1 + 2 + 4 + 7 + 14,
496 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248.
Часто математик, увлеченный решением какой-либо проблемы и имеющий одно или несколько частных решений этой задачи, пытается найти закономерности, которые смогли бы дать ключ к нахождению общего решения. Указанные нами совершенные числа могут быть записаны в виде
28 = 2 2 7 = 2 2 (2 3 — 1),
496 = 24 31 = 2 4 (2 5 — 1).
Это наталкивает нас на гипотезу:
Число является совершенным, если оно представляется в виде
является простым числом Мерсенна.
Этот результат, известный еще грекам, несложно доказать. Делителями числа Р, включая само число Р, очевидно, являются следующие числа:
Запишем сумму этих делителей
(1 + 2 +… + 2 р-1 )(q + 1) = (1 + 2 +… + 2 р-1 ) 2 р
Если вы не помните формулы для суммы членов геометрической прогрессии,
то умножьте эту сумму на 2:
а затем, вычтя S, получите
Таким образом, сумма всех делителей числа Р есть
а сумма всех делителей, кроме самого числа Р = 2 p-1 q, равна
Итак, наше число является совершенным.
Из этого результата следует, что каждое простое число Мерсенна порождает совершенное число. В § 2 второй главы говорилось, что известно всего 23 простых числа Мерсенна, следовательно, мы знаем также и 23 совершенных числа. Существуют ли другие виды совершенных чисел? Все совершенные числа вида (3.4.1) являются четными, можно доказать, что любое четное совершенное число имеет вид (3.4.1). Остается вопрос: существуют ли нечетные совершенные числа? В настоящее время мы не знаем ни одного такого числа, и вопрос о существовании нечетных совершенных чисел является одной из самых знаменитых проблем теории чисел. Если бы удалось обнаружить такое число, то это было бы крупным достижением. Вы можете поддаться соблазну найти такое число, перебирая различные нечетные числа. Но мы не советуем этого делать, так как по последним сообщениям Брайена Такхермана из IBM[7] (1968), нечетное совершенное число должно иметь по крайней мере 36 знаков.
1. Используя список простых чисел Мерсенна, найдите четвертое и пятое совершенные числа.
§ 5. Дружественные числа
Дружественные числа также входят в наследство, доставшееся нам от греческой нумерологии. Если у двух людей имена были таковы, что их числовые значения удовлетворяли следующему условию: сумма частей (делителей) одного из них равнялась второму числу, и наоборот, то считалось, что это свидетельствует об их духовной близости. В действительности греки знали всего лишь одну пару таких чисел, а именно:
220 = 2 2 • 5 • 11, 284 = 2 2 • 71.
Суммами их делителей являются соответственно
1 + 2 + 4 + 5 +10 + 20 + 11 + 22 + 44 + 55 + 110 = 284,
1 + 2 + 4 + 71 + 142 = 220.
Эта пара дружественных чисел оставалась единственной известной до тех пор, пока Пьеру Ферма не удалось найти следующую пару:
17 296 = 2 4 • 23 • 47, 18 416 = 2 4 • 1151.
Поиски пар дружественных чисел чрезвычайно удобно вести с помощью ЭВМ. Для каждого числа n при помощи машины определяются все делители этого числа (≠ n) и их сумма m. После этого производится такая же операция с числом m. Если при этом вновь получается первоначальное число n, то пара чисел (n, m) оказывается дружественной. Недавно этим способом в Йельском университете на ЭВМ IBM 7094 были проверены все числа до одного миллиона. В результате была получена коллекция из 42 пар дружественных чисел; некоторые из них оказались ранее неизвестными. Все пары дружественных чисел до 100 000 приведены в табл. 2. При помощи этого метода, как нетрудно видеть, одновременно «вылавливаются» и совершенные числа. Если возникает желание продолжать поиски дальше, то, конечно, это можно сделать, но придется затратить большое количество машинного времени.
Дружественные числа до 100 000
В действительности мы очень мало знаем о свойствах пар дружественных чисел, однако, можно на основе наших таблиц высказать несколько предположений. Например, отношение одного из них к другому, по-видимому, должно все больше и больше приближаться к 1 по мере того, как они увеличиваются. Из таблицы видно, что эти числа бывают либо оба четными, либо оба нечетными, но не было найдено случая, когда одно число четно, а другое нечетно, хотя поиски дружественных чисел такого вида были проведены среди всех чисел n ≤ 1 3 000 000 000.
Примечания:
Аликвотные дроби — дроби вида 1/n; в древности было принято всякую дробь представлять в виде суммы аликвотных дробей. Например, 5/12 = 1/12 + 1/3. (Прим. перев.)
Американская фирма, выпускающая вычислительное оборудование. (Прим. перев.)