Задача
NT-B2-M09-P017 Назначенные большие простые
Докажите, что для любого \(k\) существуют \(k\) последовательных положительных чисел, каждое из которых делится на простой делитель, больший \(k\), причём эти простые делители можно выбрать попарно различными.
Выберите \(k\) различных простых \(p_1,\ldots,p_k>k\) и задайте \(N+i\equiv 0\pmod {p_i}\).
Выберем различные простые \(p_1,\ldots,p_k>k\). Рассмотрим систему \(N+i\equiv 0\pmod {p_i}\) для \(i=1,\ldots,k\), то есть \(N\equiv -i\pmod {p_i}\). Модули попарно взаимно просты, поэтому по CRT есть решение \(N_0\) по модулю \(P=p_1\cdots p_k\). Все числа \(N=N_0+tP\) также подходят. При достаточно большом \(t\) имеем \(N+i>p_i\), значит каждое \(N+i\) составное и имеет назначенный простой делитель \(p_i>k\).
Это сильнее факториального блока и лучше показывает гибкость CRT.