Охота на контрпример
Утверждения вида «при любом n число простое» выглядят правдой на первых проверках — и ломаются дальше. Найдите наименьшее n, при котором утверждение неверно.
Как решать
Чтобы доказать утверждение «при любом $n$», нужно рассуждение. А чтобы опровергнуть — достаточно одного примера, где оно неверно. Такой пример называют контрпримером. Здесь его нужно найти, причём самый маленький.
По шагам
- Подставляйте $n$ по порядку: $1, 2, 3, \dots$ (или с того числа, с которого начинается утверждение).
- Для каждого значения проверьте, выполняется ли утверждение. Чтобы проверить, простое ли число, делите его на простые $2, 3, 5, 7, \dots$, пока квадрат делителя не превысит число.
- Ищите короткий путь: если выражение при каком-то $n$ раскладывается на множители, это и есть контрпример. Например, $n^2 + n + 41$ при $n = 41$ делится на $41$.
- Первое $n$, при котором утверждение неверно, — ответ.
Где ошибаются
- Проверяют несколько первых значений и решают, что утверждение верно. Формула $n^2 + n + 41$ даёт простые числа для всех $n$ от $0$ до $39$ — и ломается только при $n = 40$.
- Пропускают значения и находят контрпример, но не наименьший.
- Считают простым число, которое делится на большой простой: $221 = 13 \cdot 17$, $1001 = 7 \cdot 11 \cdot 13$. Делители нужно перебрать до корня из числа.
- Забывают, что $1$ — не простое число.