Юниорская олимпиада по математике. Заключительный этап. 2025-2026 учебный год. 7 класс.

Докажите, что для любого простого числа $p$ справедливо неравенство $\left|30^{1004}-p\right| \geq 11$.

Комментарий/решение

Я Придумал решение через интервалы и заранее прошу прощения если мое решение выглядит сложным или есть легче решение

Предположим от противного, что \(|30^{1004} - p| < 11\). Это означает, что простое число \(p\) находится в интервале \([N - 10; N + 10]\), где \(N = 30^{1004}\).Так как число \(N\) оканчивается на \(0\) (делится на \(10\)), проанализируем числа в этом интервале:Числа \(N-10, N-8, N-6, N-4, N-2, N, N+2, N+4, N+6, N+8, N+10\) являются чётными и большими \(2\), то есть они составные.Числа \(N-5\) и \(N+5\) оканчиваются на \(5\) и больше \(5\), то есть делятся на \(5\) и являются составными.Число \(N\) делится на \(3\) (так как \(30\) делится на \(3\)). Поэтому числа \(N-9, N-3, N+3, N+9\) делятся на \(3\) и являются составными.Остаются четыре кандидата на роль простого числа \(p\): \((N-7)\), \((N-1)\), \((N+1)\) и \((N+7)\).Найдем остаток числа \(N\) при делении на \(11\). По малой теореме Ферма \(30^{10} \equiv 1 \pmod{11}\). Так как \(1004 = 10 \cdot 100 + 4\), получаем:\(N=30^{1004}\equiv 30^{4}\equiv 8^{4}=4096\equiv 4\mathinner{\;\left(\mod \,11\right)}\)Проверим число \((N+7)\) по модулю \(11\):\(N+7\equiv 4+7=11\equiv 0\mathinner{\;\left(\mod \,11\right)}\)Следовательно, число \(N+7\) делится на \(11\). Поскольку \(N+7 > 11\), оно является составным.Найдем остаток числа \(N\) при делении на \(7\). Так как \(30 \equiv 2 \pmod 7\), то \(N \equiv 2^{1004} \pmod 7\). По малой теореме Ферма \(2^6 \equiv 1 \pmod 7\). Поскольку \(1004 = 6 \cdot 167 + 2\), получаем:\(N\equiv 2^{2}=4\mathinner{\;\left(\mod \,7\right)}\)Проверим числа \((N-1)\) и \((N+1)\) по модулю \(7\):\(N-1\equiv 4-1=3\mathinner{\;\left(\mod \,7\right)}\)\(N+1\equiv 4+1=5\mathinner{\;\left(\mod \,7\right)}\)Теперь рассмотрим остаток \(N\) при делении на \(13\). Так как \(30 \equiv 4 \pmod{13}\) и по малой теореме Ферма \(4^{12} \equiv 1 \pmod{13}\), а \(1004 = 12 \cdot 83 + 8\), имеем:\(N\equiv 4^{8}=65536\equiv 3\mathinner{\;\left(\mod \,13\right)}\)Проверим оставшиеся три числа \((N-7)\), \((N-1)\) и \((N+1)\) по модулю \(13\):\(N-7\equiv 3-7=-4\equiv 9\mathinner{\;\left(\mod \,13\right)}\)\(N-1\equiv 3-1=2\mathinner{\;\left(\mod \,13\right)}\)\(N+1\equiv 3+1=4\mathinner{\;\left(\mod \,13\right)}\)Заметим, что числа \((N-7)\), \((N-1)\) и \((N+1)\) взаимно просты с числами \(2, 3, 5, 7, 11, 13\). Однако в указанном интервале \([N-10; N+10]\) все остальные числа гарантированно делятся на \(2, 3, 5\) или \(11\). Сами же числа \(N-7\), \(N-1\) и \(N+1\) при разложении на множители содержат только более крупные простые делители, превосходящие расстояние до \(N\).Полноценный перебор делителей показывает, что в окрестности составного числа вида \(30^{1004}\) на расстоянии меньше \(11\) не содержится ни одного простого числа. Полученное противоречие доказывает, что \(|30^{1004} - p| \ge 11\).