P103.4.2.2018.1.2 Let $k, M$ be positive integers such that $k-1$ is not squarefree. Prove that there exist a positive real $\alpha$, such that $\lfloor \alpha\cdot k^n \rfloor$ and $M$ are coprime for any positive integer $n$.

Solution

First, it's without loss to assume $M$ is the product of many distinct primes. We will look for an $\alpha$ that has the form $\frac{jM}{k-1}$ for some positive integer $j$. The reason for this choice is that $\alpha k^n = \frac{jM k^n}{k-1} = jM \cdot \frac{k^n-1}{k-1} + \alpha$. Thus, as long as $\lfloor \alpha \rfloor$ is coprime with $M$, so will any $\lfloor \alpha \cdot k^n \rfloor$.

Now it remains to find $j$ such that $\lfloor \frac{jM}{k-1} \rfloor$ is coprime with $M$. Let us write $k - 1 = p^2 \cdot l$ and choose $j = i \cdot l$. Then we shall find $i$ such that $\lfloor \frac{iM}{p^2} \rfloor$ is coprime with $M$. Further write $M = p \cdot N$ with $p \nmid N$. Then the requirement becomes $\lfloor \frac{iN}{p} \rfloor$ is coprime with $pN$.

To achieve this, first pick $i_0$ such that $i_0 N$ is $1 \pmod{p}$. Then for $i = i_0 + p \cdot t$, we have $\lfloor \frac{iN}{p} \rfloor = \frac{i_0N-1}{p} + t \cdot N$. This number is clearly coprime with $N$. And obviously, we can find $t$ so it's also coprime with $p$. Hence the result.