Is this translated correctly?

Very interesting problem for #4. 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.

ABCDE wrote: Is this translated correctly? I think it's correct, the same as the Chinese version.

Hm, one version someone sent me had this instead. Perhaps it is a typo.

Attachments:

Let $p^2 \mid k-1$ and let $d = \frac{k-1}{p}$. Consider the number \[ \alpha = N + 0.\overline{ddd\dots}_k \]in base $k$. We claim it works for suitable integer $N$. Indeed, we have \[ \left\lfloor \alpha k^n \right\rfloor = k^n N + d \cdot \frac{k^n-1}{k-1} = \left( N + \frac 1p \right) k^n - \frac 1p. \]If we pick $N$ such that $p \nmid N$, then the middle-hand side expression is not divisible by $p$ (since $d$ is divisible by $p$). Moreover, we can select $N$ such that $q \mid N + p^{-1}$ for every prime $q \mid M$ other than $p$. Thus the Chinese remainder theorem completes the problem.

angiland wrote: Very interesting problem for #4. 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. if k-1|M it seems wrong

Is $M-\epsilon$ not considered a real number? (This would generate $k^n*M-1$ which is comprime to M)

Suppose $k-1$ = $p^2.d$ for $p$ a prime , Take $A$ = $0.ddd...$ [in base k] = $ 1/p^2$ $N$ will be chosen later , now take $\alpha$ = $N+A$ so $\lfloor \alpha.k^n \rfloor$ = $\frac{k^n(p^2.N+1) -1}{p^2}$ . By CRT pick $N$ such that all prime divisors of $M$ divides $p^2.N +1$ , from this the gcd condition follows ! EDIT : O. K. I see that my Sol. is almost same as v_enhance,( differ on choice of $d$ ) But anyways !!

Suppose that $k=p^2r+1$ where $p$ is a prime. Note that it's not necessary that $\gcd(p,r)=1$. Write $M=abc$ where $a=\gcd(M,k)$, $b=\gcd(M,k-1)$, and $c=\frac{M}{ab}$. Since $\gcd(k,k-1)=1$, we have that $a,b,c$ are pairwise relatively prime, as well as $\gcd(c,k)=\gcd(c,k-1)=\gcd(a,k-1)=\gcd(b,k)=1$. Let $\alpha=\frac{1}{p}+\beta$, where $\beta\equiv-1/p\pmod{c}$ and $\gcd(\beta,k-1)=1$, which exists since $\gcd(k-1,c)=1$ (CRT). We claim that this works. Note that \[X:=\lfloor\alpha\cdot k^n\rfloor=\beta\cdot k^n+\frac{k^n-1}{p}=\beta\cdot k^n+pr(1+k+\cdots+k^{n-1}).\]We see that $X\equiv pr\pmod{k}$, and $pr\mid k-1$, so $\gcd(pr,k)=1$. Thus, $\gcd(X,k)=1$, so $\gcd(X,a)=1$. Now, $X$ is relatively prime to $k-1=p^2r$ if and only if it is relatively prime to $pr$. We see that $X\equiv \beta k^n\equiv \beta\pmod{pr}$, so $\gcd(X,pr)=1$, so $\gcd(X,b)=1$. Finally, we see that \[X\equiv -\frac{1}{p}k^n+\frac{k^n-1}{p}\equiv -1/p\pmod{c},\]so $\gcd(X,c)=1$. Thus, $1=\gcd(X,abc)=\gcd(X,M)$, as desired.

A really neat problem. I'll try to outline my motivation but this is really messy. The first thing that directly came into mind is that why must there be the condition of $k - 1$ is not squarefree. We'll see later as we approach this problem. Handling some quantity like $\lfloor \alpha \cdot k^n \rfloor$ is quite difficult as $n$ could vary really large, so if it is possible I want to keep track in a constant value and something that is divisible by $\text{rad}(M)$ (so that we could just focus on the constant term), something like $\lfloor \alpha \rfloor$. This motivates us to take $\alpha$ such that $\alpha (k^n - 1) \in \mathbb{N}$ for all $n \in \mathbb{N}$. This motivates us to take $\alpha = \frac{a}{k - 1}$ for some $a \in \mathbb{N}$. This is because \[ \lfloor \alpha \cdot k^n \rfloor = \left \lfloor \frac{a}{k - 1} \cdot k^n \right \rfloor = \left \lfloor a \cdot \frac{k^n - 1}{k - 1} + \frac{a}{k - 1} \right \rfloor = a \cdot \frac{k^n - 1}{k - 1} + \left \lfloor \frac{a}{k - 1} \right \rfloor = a \cdot \frac{k^n - 1}{k - 1} + \lfloor \alpha \rfloor \]Since we want $\gcd( \lfloor \alpha \cdot k^n \rfloor , M) = 1$, we can take $a$ such that $\text{rad}(M) \mid a$. Therefore, it suffices to have $\gcd(\lfloor \alpha \rfloor, M) = 1$. Now, let $a = \text{rad}(M) \cdot i$ for some $i \in \mathbb{N}$. Therefore, we need to take $i$ such that $\gcd \left( \left \lfloor \frac{\text{rad}(M) i}{k - 1} \right \rfloor, M \right) = 1$. Now, here we will finally use the first condition. We claim that $\frac{\text{rad}(M)}{k - 1} \not \in \mathbb{N}$. Suppose otherwise, by the condition, there exists prime $p$ such that $p^2 \mid k - 1 \mid \text{rad}(M)$, contradicts the fact that $\text{rad}(M)$ is squarefree. Now, suppose that $q^2 \mid k - 1$ for some prime $q$. WLOG $q \mid \text{rad}(M)$. Take $i = \frac{k - 1}{q^2} \cdot i'$ and let $N = \frac{\text{rad}(M)}{q}$. \[ \left \lfloor \frac{\text{rad}(M)i}{k - 1} \right \rfloor = \left \lfloor \frac{N i'}{q} \right \rfloor \]Now take $i'$ to be the inverse of $N$ mod $q$ which is possible since $\gcd \left( \frac{\text{rad}(M)}{q}, q \right) = 1$. Now, it suffices to prove that with such choice of $i'$, then \[ \gcd \left( \left \lfloor \frac{Ni'}{q} \right \rfloor, qN \right) = 1 \]By our choice of $i'$ and taking $i$ such that $Ni' -1 \not \equiv 0 \ (\text{mod} \ q^2)$ which is possible by shifting $i' \mapsto i' + q$ and $\gcd(q,N) = 1$, we then have \[ \left( \frac{Ni' - 1}{q}, qN \right) = \left( \frac{Ni' - 1}{q}, q \right) = 1 \]Done.

We will restrict $\alpha$ to be rational, say $\frac ab$ for $a$ and $b$ to be determined. Let $p_1, p_2, \dots, p_\ell$ be the prime factors of $M$. The result is equivalent to $$\gcd\left(\frac{ak^n - ak^n \bmod b}b, M\right) = 1.$$ Fix $p_1p_2 \cdots p_\ell \mid a$. If there exists a $p \not \in \{p_1, p_2, \dots, p_\ell\}$ such that $p \mid k-1$, pick $b = p$ and $a \equiv -1 \pmod p$, such that $$\frac{ak^n - ak^n \bmod b}b \equiv \frac 1p \pmod {p_1p_2 \cdots p_\ell}$$for all $n$; this yields the condition. If such a $p$ does not exist, then we may invoke $k - 1$ not squarefree to contend that $p_i^2 \mid k-1$ for some $1 \leq i \leq \ell$. In this case, pick $b = p_i^2$ and $a = cp_1p_2 \cdots p_k$ such that $a \equiv p_i \pmod p_i^2$. Then $$\frac{ak^n-ak^n \bmod b}b \equiv \frac{p_i(ck^n \cdot p_1p_2\cdots p_{i-1}p_{i+1} \cdots p_\ell -1)}{p_i^2} \pmod {p_1p_2 \cdots p_\ell}$$which is also relatively prime to $M$.