Олимпиада имени Леонарда Эйлера 2024-2025 учебный год, II тур заключительного этапа

Дано натуральное число $n$. Докажите, что при некотором натуральном $m$ у числа $m^3+m$ ровно один или ровно два различных простых делителя, больших $n$. ( А. Кузнецов )

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

Пусть m - наименьшее простое число большее чем n.

Тогда остаётся доказать что m(m^2+1) ровно 1 или ровно 2 простых делителя больших n,мы уже знаем что m простое и больше чем n => нужно доказать что m^2+1 имеет меньше двух простых делителей больших чем n ,так как m^2+1 = 1(mod m)=>m^2+1 не делится на m=>доказать что m^2+1 не имеет 2 простых делителей больших m

Докажем от противного :Пусть m^2+1 имеет 2 делителя больших чем m тогда

m^2+1=(m+k)(m+r)x,но (m+k)(m+r)x=(m^2+mr+mk+kr)x>m^2+1 противоречие.=>

m^2+1 имеет 0 или 1 простых делителя больших m,пример для 0 :m=3

Пример для 1 :m=2 Доказано.

возьмем $p$ как наименьшее простое число , которое больше $n$

Ответ: $m = p$

Доказательство: $m^{3} + m = p^{3}+p = p(p^{2}+1)$ это число уже делится на $p$, и $p^{2}+1$ взаимно просто с $p$ . Тогда если $p^{2}+1$ делится на такие $q_{1} , q_{2}$ , которые $>p$ и являются простыми , то число $m^3+m$ делится на три простых больших $n$ . т.к. $q_{1} , q_{2}$ взаимнопростые , то число $p^{2}+1$ можно разложить как $q_{1} \cdot q_{2} \cdot g$, где $g \in \mathbb{N}$. Так как

$q_{1} , q_{2}\geq p+1 => q_{1} \cdot q_{2} > (p+1)^{2} > p^{2} + 1$, значит $p^{2} + 1$ может делится только на одно простое число большее $p$ , значит число $p^{3}+p$ делится только на одно простое число большее $n$ либо на два простых числа большее $n$

Здесь не доказано что p^2+1 вообще может делится на 1,0 простое число большее n,для доказательства этого достаточно привести пример этого

это и не нужно доказывать. в задаче просится доказать что $m^{3}+m$ будет делится на ровно один либо ровно два простых числа. я сказал что m = p>n, то есть наше выражение уже как минимум делится на одно простое число, позже доказал что оно не может делится на еще два других простых числа больших n, то есть если $p^{2}+1$ не будет делится на другие простые числа то наше выражение все равно делится на одно простое, а если делится на одно простое большее n, то оно делится на ровно два простых числа больших n.