Задача
NT-B2-M09-P019 Много составных значений линейных выражений
#19
★★★★★ Уровень 5 из 5
Пусть \(a_1,\ldots,a_k\) — различные целые числа. Докажите, что существует бесконечно много \(N\), для которых все числа \(N+a_1,\ldots,N+a_k\) составные.
Выберите различные простые \(p_i\), не делящие разности \(a_i-a_j\), и задайте \(N+a_i\equiv 0\pmod {p_i}\).
Выберем попарно различные простые \(p_1,\ldots,p_k\), настолько большие, что \(p_i>|a_i-a_j|\) для всех \(i,j\), и \(p_i>0\). Система \(N\equiv -a_i\pmod {p_i}\) совместна по CRT. Пусть \(N_0\) — решение, \(P=p_1\cdots p_k\). Тогда \(N=N_0+tP\) сохраняет все делимости \(p_i\mid N+a_i\). При достаточно больших \(t\) все \(N+a_i\) положительны и больше \(p_i\), значит составные. Таких \(t\) бесконечно много.
Нестандартное применение CRT; важно проговорить выбор больших простых.