Доказательство того, что наибольшего простого числа не существует.

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

Логическая головоломка

Вы находитесь в 106-этажном здании. Этажи пронумерованы от 0 до 105 (так же, как и в большинстве стран мира, за исключением США). Вы хотите проверить, с какого самого высокого этажа можно безопасно сбросить яйцо в большую коробку с перьями, стоящую на полу. Вы знаете, что яйцо, сброшенное с крыши, разобьется, а яйцо, сброшенное с нулевого этажа, останется целым. У вас есть два яйца для эксперимента. Какое наименьшее количество падений вам понадобится в худшем случае?

Ответ и решение приведены в конце колонки.

Доказательство того, что наибольшего простого числа не существует.

Я докажу от противного, что наибольшего простого числа не существует. Другими словами, я опровергну противоположное утверждение — что наибольшего простого числа не существует.

Назовём наибольшее простое число p _n , то есть это n-е простое число. Обозначим все простые числа в порядке убывания следующим образом:

p ₁ = 2, p ₂ = 3, p ₃ = 5, p ₄ = 7, … p _n =?

Рассмотрим число N следующего вида:

N = p ₁ × p ₂ × p ₃ × p ₄ × … × p _n +1.

Если N — простое число, то никакое меньшее простое число не должно делиться на него без остатка. Однако, если мы разделим на него любое простое число до p _n , то получим остаток 1.Это можно объяснить только двумя возможными способами:

1. Само число N является простым, то есть оно должно быть больше p _n .
2. Существует некоторое простое число больше p _n , которое делится на N без остатка.

В любом случае, мы показали, что существует некоторое простое число больше p _n .

Давайте рассмотрим, например, небольшое простое число. Посмотрим, что произойдет, если предположить, что 31 — наибольшее простое число. В этом случае:

N = 2×3×5×7×11×13×17×19×23×29×31 + 1 = 1 805 044 411 171

Используя калькулятор простых множителей, мы получаем 1 805 044 411 171 = 1 061 729 x 1 700 099. Таким образом, мы нашли два простых числа, больших, чем 31: 1 061 729 и 1 700 099.

В качестве другого примера предположим, что 7 — наибольшее простое число. Тогда N = 2×3×5×7 + 1 = 211. Проведя тест на разложение на простые множители для числа 211, мы обнаружим, что 211 — простое число. Таким образом, мы нашли простое число, большее, чем 7.

Независимо от того, какое простое число мы считаем наибольшим, этот метод найдет большее.

Ответ на логическую головоломку

14

Вот как найти самый высокий безопасный этаж, где не более 14 падений.

1. Первое яйцо нужно сбросить с 14-го этажа. Если оно разобьется, проверяйте этажи с 1 по 13 по очереди. Максимальное количество бросков, необходимых при разбитии яйца, равно 14 (1 с первым яйцом и 13 со вторым). В противном случае переходите к шагу 2.
2. Поднимитесь на 13 этажей, сбросив первое яйцо с 27-го этажа. Если оно разобьется, проверяйте этажи с 15 по 26 по очереди. Максимальное количество падений, необходимое при разбитии яйца, равно 14 (2 с первым яйцом и до 12 со вторым). В противном случае переходите к шагу 3.
3. Поднимитесь на 12 этажей, сбросив первое яйцо с 39-го этажа. Если оно разобьется, проверяйте этажи с 28 по 38 по очереди. Максимальное количество падений, необходимое при разбитии яйца, равно 14 (3 с первым яйцом и до 11 со вторым). В противном случае переходите к шагу 4.
4. Поднимитесь на 11 этажей, сбросив первое яйцо с 50-го этажа. Если оно разобьется, проверяйте этажи с 40-го по 49-й по очереди. Максимальное количество яиц, необходимых при разбитии, = 14 (4 с первым яйцом и до 10 со вторым). В противном случае переходите к шагу 5.
5. Поднимитесь на 10 этажей, сбросив первое яйцо с 60-го этажа. Если оно разобьется, проверяйте этажи с 51 по 59 по очереди.Максимальное количество падений, необходимое при поломке яйца, составляет 14 (5 с первым яйцом и до 9 со вторым). В противном случае перейдите к шагу 6.
6. Поднимитесь на 9 этажей, сбросив первое яйцо с 69-го этажа. Если оно разобьется, проверяйте этажи с 61 по 68 по очереди. Максимальное количество падений, необходимое при разбитии яйца, равно 14 (6 с первым яйцом и до 8 со вторым). В противном случае переходите к шагу 7.
7. Поднимитесь на 8 этажей, сбросив первое яйцо с 77-го этажа. Если оно разобьется, проверяйте этажи с 70 по 76 по очереди. Максимальное количество яиц, необходимых при разбитии, равно 14 (7 с первым яйцом и до 7 со вторым). В противном случае переходите к шагу 8.
8. Поднимитесь на 7 этажей, сбросив первое яйцо с 84-го этажа. Если оно разобьется, проверяйте этажи с 78 по 83 по очереди. Максимальное количество падений, необходимое при разбитии яйца, равно 14 (8 с первым яйцом и до 6 со вторым). В противном случае переходите к шагу 9.
9. Поднимитесь на 6 этажей, сбросив первое яйцо с 90-го этажа. Если оно разобьется, проверяйте этажи с 85 по 89 по очереди. Максимальное количество падений, необходимое при разбитии яйца, равно 14 (9 с первым яйцом и до 5 со вторым). В противном случае переходите к шагу 10.
10. Поднимитесь на 5 этажей, сбросив первое яйцо с 95-го этажа. Если оно разобьется, проверяйте этажи с 91 по 94 по очереди. Максимальное количество падений, необходимое при разбитии яйца, равно 14 (10 с первым яйцом и до 4 со вторым). В противном случае переходите к шагу 11.
11. Поднимитесь на 4 этажа, сбросив первое яйцо с 99-го этажа. Если оно разобьется, проверяйте этажи с 96 по 98 по очереди. Максимальное количество падений, необходимое при разбитии яйца, равно 14 (11 с первым яйцом и до 3 со вторым). В противном случае переходите к шагу 12.
12. Поднимитесь на 3 этажа, сбросив первое яйцо со 102-го этажа. Если оно разобьется, проверьте этажи 100 и 101 по очереди. Максимальное количество падений, необходимое при разбитии яйца, равно 14 (12 с первым яйцом и до 2 со вторым). В противном случае перейдите к шагу 13.
13. Поднимитесь на 2 этажа, сбросив первое яйцо с 104-го этажа. Если оно разобьется, проверьте 103-й этаж. Максимальное количество яиц, необходимых при разбитии, равно 14 (13 с первым яйцом и 1 со вторым). В противном случае перейдите к шагу 14.
14. Поднимитесь на 1 этаж выше, сбросив первое яйцо с 105-го этажа. Если оно разобьется, самый верхний безопасный этаж — 104. Если оно выживет, самый верхний безопасный этаж — 105.

Общая стратегия для n-этажного здания заключается в поиске оптимального этажа для первого падения. Если первый тест пройден успешно, вы поднимаетесь на такое же количество этажей минус 1. Если второй тест пройден успешно, то вы поднимаетесь на один этаж меньше, чем в прошлый раз. Продолжайте повторять это, поднимаясь на один этаж меньше, чем при предыдущем увеличении между тестами. Если тест с первым яйцом не пройден, то используйте второе яйцо, чтобы систематически проверять каждый этаж между двумя последними тестами, начиная с самого нижнего этажа в этом диапазоне.

Обратите внимание, что количество этажей увеличивается на n, n-1, n-2, ... 1. Сумма всех этих скачков равна n(n+1)/2. Ключевой момент — найти наименьшее возможное целое значение n, при котором сумма последовательности равна или больше количества этажей в здании.

Например, рассмотрим 500-этажное здание (не считая безопасного первого этажа) и решим уравнение:

n(n+1)/2 = 500

n(n+1) = 1000

^n² + n - 1000 = 0

6; font-family: 'Open Sans', sans-serif; color: #313131 !important; ">Используя формулу Пифагора:

n = (-1 +/- √4001 )/2 ≈ 31,13

Однако этажи имеют целочисленные значения. Поэтому мы округляем до n=32. Таким образом, в случае 500-этажного здания (или 501-этажного, если считать безопасный первый этаж) мы проводим первый тест, начиная с 32-го этажа.