Республиканская олимпиада по математике, 2023 год, 11 класс

Даны натуральные числа $a,b,m$ и $k$, где $k\ge 2$. Докажите, что существует бесконечно много натуральных $n$ такие, что $$\text{НОД} \left( \varphi_m(n), \left [\sqrt[k]{an+b} \right] \right ) = 1 $$ ($\varphi_1(n) = \varphi(n)$ — функция Эйлера, т.е. количество целых чисел от 1 до $n$, которые взаимно просты с $n$, $\varphi_{i+1}(n) = \varphi(\varphi_i(n))$ при всех $i\ge 1$, а $[ x]$ — целая часть числа $x$, т.е. наибольшее целое число, не превосходящее $x$.) ( Сатылханов К. )

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

Берем большие простые вида $p = at-1.$ Тогда $n = \frac{p\cdot (p+1)^{k-1}}{a}$ подходят. (Теорему Дирихле нельзя использовать в Казахстане.)

Мы найдем бесконечно много $n$, таких что $\lfloor \sqrt[k] {an+b} \rfloor$ является простым числом, скажем $p$, и $n$ удовлетворяет условию $\nu_p(n)=1$ а $p$ — наибольший простой делитель числа $n$. Обратите внимание, что тогда $p \nmid \varphi_m(n)$ для любого положительного целого числа $m$, так что таким образом мы обеспечим взаимную простоту.

У нас есть $\lfloor \sqrt[k] {an+b} \rfloor=p \iff p^k \leq an+b <(p+1)^k$. Мы ищем $n=pM$ для некоторого $(M, p)=1$ с простыми делителями меньше $p$, такого что $M>p^{k-1}$, что гарантирует выполнение нижней оценки. Для верхней границы нам понадобится $an+b<(p+1)^k \iff p+\frac{b} {aM}<\frac{(p+1)^k}{aM}$. Так как $M>p^{k-1}$, то для достаточно больших $p$ имеем $b<aM$, поэтому нам нужен $\frac{(p+1)^k}{aM} \geq p+1 $, следовательно, выбора $aM=(p+1)^{k-1}$ будет достаточно, так как это также будет означать, что наибольший простой делитель числа $n$ равен $p$. Осталось найти бесконечно много простых чисел $p$ таких, что $a \mid p+1$, что возможно Дирихле. Следовательно, эта конструкция работает, и мы закончили.