Задача
NT-B2-M12-P013 Многочлен не всегда даёт простые
#13
★★★★☆ Уровень 4 из 5
Пусть \(f\in\mathbb Z[x]\) — непостоянный многочлен. Докажите, что невозможно, чтобы все числа \(f(1),f(2),f(3),\ldots\) были простыми положительными числами.
Возьмите одно простое значение \(p=f(a)\) и рассмотрите \(f(a+pt)\).
Пусть \(p=f(a)\) — простое положительное число. Для любого целого \(t\) имеем \(a+pt\equiv a\pmod p\), значит \(f(a+pt)\equiv f(a)\equiv0\pmod p\). Так как \(f\) непостоянен, значения \(|f(a+pt)|\) неограниченно растут при больших \(t\). Для достаточно большого \(t\) получим положительное значение, большее \(p\), но делящееся на \(p\). Оно составно. Противоречие.
Олимпиадный ход: зафиксировать одно простое значение и породить кратные ему новые значения.