Олимпиада имени Леонарда Эйлера 2017-2018 учебный год, II тур регионального этапа

Докажите, что существует натуральное число $n$, большее $10^{100},$ такое, что сумма всех простых чисел, меньших $n,$ взаимно проста с $n.$ ( Р. Салимов )

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

Комментарии от администратора Комментарии от администратора №1.     Решение. Обозначим через $S(n)$ сумму всех простых чисел, меньших $n.$ Заметим, что $$S(n) < 1+2+\ldots +(n-1) = n(n-1)/2 < n(n-1). \quad(*)$$ Рассмотрим два последовательных простых числа $q > p > 10^{100}.$ Допустим, $S(p)$ не взаимно просто с $p,$ а $S(q)$ не взаимно просто с $q.$ Тогда $S(p)$ делится на $p,$ а $S(q)$ делится на $q.$ Пусть $S(p) = kp.$ Из неравенства $(*)$ вытекает, что $k < p-1.$ Тогда, так как $S(q) = S(p)+p = p(k+1),$ и $S(q)$ делится на $q,$ имеем $k+1 \ge q.$ Но $k < p-1 < q-1.$ Противоречие.