При каком меньшем естественном 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 lt; 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 lt; 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.