Симпсоны и их математические секреты - стр. 8
Большинство людей посчитали бы, что Рейсс слишком строг к себе, восьмилетнему, потому что ответ далеко не так очевиден. Его вопрос основан на факте, что у каждого целого числа есть делители – числа, на которые оно делится без остатка. Простое число примечательно тем, что у него только два делителя – 1 и само число (так называемые тривиальные делители). Таким образом, 13 – это простое число, потому что у него нет нетривиальных делителей, а 14 – нет, поскольку его можно разделить на 2 и 7. Все числа являются либо простыми (например 101), либо их можно разделить на простые делители (например 102 = 2 × 3 × 17). Между числами 0–100 существует 25 простых чисел, между 100–200 – 21 простое число, а между 200–300 – всего 16 простых чисел, стало быть, количество простых чисел уменьшается. Тем не менее закончатся ли они со временем или их список бесконечен?
Гарднер с удовольствием рассказал Рейссу о доказательстве древнегреческого ученого Эвклида, который работал в Александрии около 300 года до нашей эры[6]. Эвклид был первым математиком, доказавшим существование бесконечного множества простых чисел. Как ни странно, он получил этот результат, выдвинув прямо противоположную гипотезу и применив к ней метод, известный как доказательство от противного. Один из способов объяснить подход Эвклида – начать со следующего смелого утверждения:
Предположим, что количество простых чисел конечно и все они собраны в список: p>1, p>2, p>3, … p>n.
Мы можем изучить следствия, вытекающие из этого утверждения, перемножив все простые числа в этом списке и прибавив 1, что создает новое число: N = p>1 × p>2 × p>3 × … × p>n + 1. Это новое число N является либо простым, либо нет, но в любом случае оно противоречит исходному утверждению Эвклида.
• Если N – простое число, тогда оно отсутствует в первоначальном списке. Таким образом, утверждение о том, что это полный список, ошибочно.
• Если N – не простое число, тогда оно должно иметь простые делители, которые должны быть новыми простыми числами, поскольку деление простых чисел в исходном списке на N даст в остатке 1. Стало быть, утверждение о том, что это полный список, тоже ошибочно.
Следовательно, исходное утверждение Эвклида ложно: его конечный список не содержит всех простых чисел. Более того, любая попытка опровергнуть это утверждение, включив в список новые простые числа, обречена на неудачу, так как приведенные выше аргументы можно снова использовать для доказательства того, что список по-прежнему неполный, а значит, должно существовать бесконечное количество простых чисел.