Given are positive integers $a, b, m, k$ with $k \geq 2$. Prove that there exist infinitely many $n$, such that $\gcd (\varphi_m(n), \lfloor \sqrt[k] {an+b} \rfloor)=1$, where $\varphi_m(n)$ is the $m$-th iteration of $\varphi(n)$.
Problem
Source: Kazakhstan National Olympiad (10-11).5
Tags: number theory
VicKmath7
06.10.2023 16:01
We will find infinitely many $n$, such that $\lfloor \sqrt[k] {an+b} \rfloor$ is a prime, say $p$, and $n$ satisfies $\nu_p(n)=1$ and $p$ is the greatest prime factor of $n$. Notice that then $p \nmid \varphi_m(n)$ for any positive integer $m$, so this way we will have ensured the coprimity holds.
We have that $\lfloor \sqrt[k] {an+b} \rfloor=p \iff p^k \leq an+b <(p+1)^k$. We are searching for $n=pM$ for some $(M, p)=1$ with prime factors less than $p$ such that $M>p^{k-1}$, which guarantees the lower bound holds. For the upper bound, we need $an+b<(p+1)^k \iff p+\frac{b} {aM}<\frac{(p+1)^k}{aM}$. Since $M>p^{k-1}$, for sufficiently large $p$ we have $b<aM$, so we need $\frac{(p+1)^k}{aM} \geq p+1$, hence choosing $aM=(p+1)^{k-1}$ will suffice, as this will also mean that the largest prime factor of $n$ is $p$. It's only left to find infinitely many primes $p$ such that $a \mid p+1$, which is possible by Dirichlet. Hence, this construction works and we are done.