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

$a,b,m$ және $k\ge 2$ натурал сандары берілген. $$\text{ЕҮОБ} \left( \varphi_m(n), \left [\sqrt[k]{an+b} \right] \right ) = 1 $$ болатындай шексіз көп натурал $n$ сандарының табылатынын дәлелдеңіз. (Бұл жерде $\varphi_1(n) = \varphi(n)$ — Эйлер функциясы, ол 1-ден $n$-ге дейін неше сан $n$ санымен өзара жай екенін көрсетеді, ал барлық $i\ge 1$ үшін $\varphi_{i+1}(n) = \varphi(\varphi_i(n))$. $[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$, что возможно Дирихле. Следовательно, эта конструкция работает, и мы закончили.