# Why are there infinitely many positive $k$ such that $\lfloor \frac{n^k}{k}\rfloor$ is odd?

Give the postive integer $n>1$, there exist infinite positive integer $k$ such that $\lfloor \dfrac{n^k}{k}\rfloor$ is odd

Maybe we can Use Euler's theorem,$$n^{\phi{(k)}}\equiv 1\pmod k$$ let $$n^{\phi{(k)}}=rk+1\Longrightarrow n^k=\left(kr+1\right)^{\frac{k}{\phi{(k)}}}\Longrightarrow \dfrac{n^k}{k}=\dfrac{\left(kr+1\right)^{\frac{k}{\phi{(k)}}}}{k}$$I don't think this last part is relevant to understanding the exercise as stated, but I may be wrong.

• A nice question, +1 – k1.M May 5 '15 at 9:17
• This question was proposed to the 2014 International Mathematical Olympiad. See imo-official.org/problems/IMO2014SL.pdf, question N4. (In fact, as such it was confidential until July 2015.) – user133281 Aug 29 '16 at 8:55

If $n$ is odd, take $k=n^s$ ($s=1,2,3,\dots$).

If $n$ is even and $n>2$, choose any prime divisor $p$ of $n-1$ and take $k=p^s$ (the trick is that $n^{p^s}-1$ is divisible by $p^s$, which is easy to show by induction).

Finally, consider the case $n=2$. Here I do not know a really nice proof but the following argument works. Take $k=2^sp$ where $p$ is an odd prime. Then $2^k-2^{2^s}$ is divisible by $2^sp$ and the quotient is even if $s$ is not too small, so we just want to make $[2^{2^s-s}/p]$ odd, which can be achieved by taking for $p$ any prime divisor of $2^{2^s-s}-1$.

It seems the following.

If $n$ is odd, then we have an infinite sequence $\{n, n^n, n^{n^n}, \dots\}$ of suitable $k$’s.

For every odd prime number $p>n$ we have $$\frac{n^p-n}p\in\mathbb Z$$ Hence $$[\frac{n^p}p]=[\frac{(n^p-n)+n}p]=[\frac{n^p-n}p]+[\frac np]=[\frac{n^p-n}p]=\frac{n^p-n}p$$ Now observe that the number $\frac{n^p-n}p$ is even, because $n^p-n$ is even and $p$ is odd.

• Nice answer,But My problem is prove is odd? – user237685 May 5 '15 at 10:54
• Oh, I didn't read the question correctly....execuse me... – k1.M May 5 '15 at 10:57