При каком наименьшем натуральном n число n^2+n+41 является составным? С доказательством, что при меньших n число n^2+n+41 простое

1. Пусть:

f (n) = n^2 + n + 41; f (n) = n (n + 1) + 41.

Тогда для простого числа p, меньше 41, справедливы (не) сравнения:

f (p - 1) ≢ 0 (mod p); (1) f (p) ≢ 0 (mod p). (2)

2. Следовательно, если для значений n от 1 до p - 2 верно сравнение:

f (n) ≢ 0 (mod p),

то оно верно для любого значения n.

3. Для n от 1 до 5 получим простые числа:

f (1) = 1 * 2 + 41 = 2 + 41 = 43; f (2) = 2 * 3 + 41 = 6 + 41 = 47; f (3) = 3 * 4 + 41 = 12 + 41 = 53; f (4) = 4 * 5 + 41 = 20 + 41 = 61; f (5) = 5 * 6 + 41 = 30 + 41 = 71.

4. Из утверждения 2 следует:

f (n) ≢ 0 (mod 2); f (n) ≢ 0 (mod 3); f (n) ≢ 0 (mod 5); f (n) ≢ 0 (mod 7).

5. Далее:

f (8) = 8 * 9 + 41 = 72 + 41 = 113 < 11^2.

Значит, числа f (6), f (7) и f (8) простые.

f (9) = 9 * 10 + 41 = 90 + 41 = 131 - простое. f (n) ≢ 0 (mod 11).

6. Далее:

f (10) = 10 * 11 + 41 = 110 + 41 = 151 - простое; f (11) = 11 * 12 + 41 = 132 + 41 = 173 - простое; f (n) ≢ 0 (mod 13).

7. Далее (этот случай рассмотрен для ясности):

f (15) = 15 * 16 + 41 = 240 + 41 = 281 < 17^2; f (n) ≢ 0 (mod 17).

8. Далее, для числа p имеем:

f (p - 2) - p^2 = (p - 2) (p - 1) + 41 - p^2 = 43 - 3p = 3 (43/3 - p) = 3 (14 1/3 - p).

При p ≥ 17 получим отрицательное число. Следовательно:

f (n) ≢ 0 (mod 17); f (n) ≢ 0 (mod 19); f (n) ≢ 0 (mod 23); f (n) ≢ 0 (mod 29); f (n) ≢ 0 (mod 31); f (n) ≢ 0 (mod 37).

9. Наименьшее значение n, при котором f (n) - составное число:

n = 40; f (n) = 40 * 41 + 41 = 41 (40 + 1) = 41^2.

Ответ: 40.