If $n$ is odd, then we can pick any prime $p$ dividing $n$, and selecting $k=p^m$ for sufficiently large integers $m$. Suppose $n$ is even now. Then by Kobayashi's Theorem, there exist infinitely many primes $p$ dividing some number of the form \[ n^{n^r-1} - 1. \] for some integer $r$. Let $p > n$ be such a prime, with corresponding integer $r$. It then follows that \[ n^{n^rp} \equiv n^r \pmod{n^rp} \] since this is clearly correct mod $n^r$, and also correct modulo $p$. If we select $k = n^rp > r$, so that $n^k \equiv n^r \pmod k$, we have \[ \left\lfloor \frac{n^k}{k} \right\rfloor = \frac{n^k - n^r}{n^rp} \] which is odd.

Hey can you give me some source for Kobayashi's Theorem.........this was also asked in the Indian TST..

https://projecteuclid.org/euclid.tjm/1270215162 Although I think you don't really need it, you can just take $r$ large.

Indeed, take $s = (q-1)^2$ for some prime $q\geq 3$ and $\left ( q,n \right ) = 1$. By Zsigmondy there is a prime divisor $p$ of $n^q - 1$ that does not divide $n - 1$. So, $q$ is the order of $n$ modulo $p$. Select $k = n^sp$. Then $n^sp - s \equiv n^s - s = n^{(q-1)^2} - (q-1)^2 \equiv 1 - 1\equiv 0 (mod q)$. So, $n^{n^sp}\equiv n^s (mod p)$. This implies $\left \lfloor \frac{n^k}{k} \right \rfloor = \left \lfloor \frac{n^{n^sp - s}}{p} \right \rfloor = \frac{n^{n^sp - s} - 1}{p}$ which is clearly odd.

Instead of some advanced NT, let's do something a bit more obvious... If $n$ is odd just choose $n^u$ for $u > 1$. It is easy to see that this produces odd integers. If $n-1$ is odd and $n-1 \neq 1$, consider a prime factor $p$ of $n-1$. Now consider $p^l$, where $l > 1$, \[\ \lfloor\frac{n^{p^l}}{p^l}\rfloor = \frac{n^{p^l}-1}{p^l} \] This is an integer because $v_p(n^{p^l}-1) = v_p(p^l) + v_p(n-1) \ge l$ by LTE, and it is obviously odd. Now consider $n = 2$. In this case, I claim $k = 3 \cdot 2^{2j}$, for arbitrary $j \neq 0$ works. Indeed \[\ \lfloor\frac{2^{3(2^{2j})}}{3(2^{2j})} \rfloor = \lfloor \frac{2^{3(2^{2j})-2j}}{3} \rfloor \]. Observe that $3(2^{2j})-2j$ is always even, so then this quotient becomes \[ \frac{2^{3(2^{2j})-2j}-1}{3} \], which is clearly odd, so we are done.

Alternatively, For $n$ odd take $k=n^t$ for some integer $t>1$. For $n$ even take $k=n^{2b}(n^2-1)$ for some positive integer $b>4$. We know that $n^2-1|n^{n^{2b}(n^2-1)-2b}-1$, and it follows that $\lfloor\frac{n^{n^{2b}(n^2-1)}}{n^{2b}(n^2-1)}\rfloor=\frac{n^{n^{2b}(n^2-1)-2b}-1}{n^2-1}$ which is odd.

I use For $n$ odd take $k = n^{mn}$ for some positive integer $m$ For $n$ even take $k = n^{nm}(n + 1)$ for some positive integer $m$. I was lucky when I tried for $n = 2$ and I got $k = 12$ and then I guess $n^n(n + 1)$. The proof is an easy application of CRT. Just consider (for the even case) $n^k$ mod $2n + 2$.

Another solution: Consider two cases: 1) $n\equiv 1\pmod{2}$. Then choose a prime $p$ such that $p\mid n$ then it's easy to see that $\frac{n^{p^k}}{p^k}\in \mathbb{N}$ which is odd. 2) $n\equiv 0\pmod{2}$ and $n> 2$ from zigmondy's theorem $n^{n-1}-1$ has an odd prime divisor $p$ that $p\nmid n-1$ so $(p,n-1)=1\Longrightarrow \frac{n^{n-1}-1}{p(n-1)}\in \mathbb{N}$(1) hence from LTE lemma and (1) we have $\frac{n^{(n-1)p^s-1}}{(n-1)p^s}\in \mathbb{N}$ for every $s$ now notice that for large value of $s$ we have $\lfloor\frac{n^{(n-1)p^s}}{p^s}\rfloor=\frac{n^{(n-1) p^s}-1}{(n-1)p^s}\in \mathbb{N}$ which is odd. 3) $n=2$ then if $k\mid 2^k-1$ then $2^k-1\mid2^{2^k-1}-1$ so we can find infinitely odd $k$ such that $k\mid 2^k-1$ now if $k$ is sufficiently large enough then $\lfloor\frac{2^k}{k}\rfloor=\frac{2^k-1}{k}\in \mathbb{N}$ which is odd. Q.E.D

Alternatively, for $n=2$ we can take $k=2 \cdot 9^a$ for any positive integer $a$, because $A=2^{2 \cdot 9^a}-9^a-1 $ is divisble by $2 \cdot 9^a$, but not by 4, and hence the quotient $\lfloor \frac{2^{2 \cdot 9^a}}{2 \cdot 9^a} \rfloor$ is odd.

We will construct a distinct $k$ for any $\alpha \in \mathbb{N}$, which will clearly yield infinitely many $k.$ If $n$ is odd, set $k = n^{\alpha}$ so that $\tfrac{n^k}{k} = n^{n^{\alpha} - \alpha}$, which is odd. If $n = 2m$ is even, choose a prime divisor $p$ of $2^{2^{\alpha} - \alpha}m^{2^{\alpha}} - 1.$ From the equality \[n^{2^{\alpha}} - 2^{\alpha} = 2^{\alpha}\left(2^{2^{\alpha} - \alpha}m^{2^{\alpha}} - 1\right),\]it follows that $n^{2^{\alpha}} \equiv 2^{\alpha} \pmod{p}.$ Moreover, $p \nmid n$, since $p \mid n$ would force $p \mid 2^{\alpha}$, i.e. $p = 2$, absurd. Now, set $k = p \cdot 2^{\alpha}.$ By considering $v_2(k)$, it is clear that each $\alpha$ gives rise to a distinct $k.$ Moreover, $k \nmid n^k$ since $p \nmid n^k.$ Hence, we can write \[0 < n^k - \left\lfloor \frac{n^k}{k} \right\rfloor k < k.\]If $\left\lfloor \tfrac{n^k}{k} \right\rfloor$ is odd, we're done. Thus, suppose that $\left\lfloor \tfrac{n^k}{k} \right\rfloor$ is even, and note that $2^{\alpha + 1}$ divides $n^k - \left\lfloor \tfrac{n^k}{k} \right\rfloor k$ because $2^{\alpha + 1}$ divides both terms. Therefore, we can strengthen the above inequality as \[2^{\alpha + 1} \le n^k - \left\lfloor \frac{n^k}{k} \right\rfloor k < k \implies 2 \le \frac{n^k}{2^{\alpha}} - \left\lfloor \frac{n^k}{k} \right\rfloor p < p. \quad (\star)\]But Fermat's Little Theorem implies that \[\frac{n^k}{2^{\alpha}} = \frac{\left(n^p\right)^{2^{\alpha}}}{2^{\alpha}} \equiv \frac{n^{2^{\alpha}}}{2^{\alpha}} \equiv 1 \pmod{p}.\]Thus, when reducing $(\star)$ modulo $p$, we obtain a contradiction. This completes the proof. $\square$

Does this work? $n=2$: Proved above. $n=3$: $k = 3^i$. $n \geq 4$: By Bertrand's Postulate, there exists an odd prime $p$ such that $n/2 < p \leq n$. Take $k = p$. By Fermat's Little Theorem, $n^p \equiv n \equiv n-p \pmod p$. Since $0 \leq n-p < p$, $\left\lfloor\frac{n^p}{p}\right\rfloor = \frac{n^p-(n-p)}{p} = odd$, since $n^p-n$ is even and $p$ is odd.

MathPanda1 wrote: Does this work? $n=2$: Proved above. $n=3$: $k = 3^i$. $n \geq 4$: By Bertrand's Postulate, there exists an odd prime $p$ such that $n/2 < p \leq n$. Take $k = p$. By Fermat's Little Theorem, $n^p \equiv n \equiv n-p \pmod p$. Since $0 \leq n-p < p$, $\left\lfloor\frac{n^p}{p}\right\rfloor = \frac{n^p-(n-p)}{p} = odd$, since $n^p-n$ is even and $p$ is odd. You showed $ p $, not infinitely many for $n \geq 4$.

Oh shoot, sorry, forgot the infinite part Thanks!

I think I got a simpler solution, but no one has posted it yet. If $n$ is odd, then we're obviously done by choosing $k=n^c$. Else, choose an odd $p|n-1$. We claim $k=p\cdot n^c$ works for all $c$. We have $\lfloor \frac{n^{p\cdot n^c}}{p\cdot n^c} \rfloor= \lfloor \frac{n^{p\cdot n^c-c}}{p} \rfloor$. However since $p|n-1$ we have $n^{p\cdot n^c-c} \equiv 1 (mod p)$. So $\lfloor \frac{n^{p\cdot n^c-c}}{p} \rfloor= \frac{n^{p\cdot n^c-c}-1}{p}$ which is obviously odd, since $n$ is even and $p$ is odd. For $n=2$ we find that $k=3\cdot 4^c$ works in a similar fashion.

For the $n>2$ even case, we can just take $k=n^b(n-1)$ for $b\in \mathbb{Z}^{+}$ instead (same proof as gradysocool).

hajimbrak wrote: Let $n > 1$ be a given integer. Prove that infinitely many terms of the sequence $(a_k )_{k\ge 1}$, defined by \[a_k=\left\lfloor\frac{n^k}{k}\right\rfloor,\]are odd. (For a real number $x$, $\lfloor x\rfloor$ denotes the largest integer not exceeding $x$.) Proposed by Hong Kong For each $n$, we present an infinite number of $k$ that allow $\left\lfloor\frac{n^k}{k}\right\rfloor \equiv 1 \pmod{2}.$ If $n$ is odd, let $k=n^s$ for any $s \ge 1$. If $n>2$ is even, let $k=n^s(n-1)$ for any $s \ge 1$. If $n=2$, let $k=2^s(2^r-1)$ where $s>1$ is any odd number and $r \mid 2^s-s$ is an odd prime. Now to show they all work. For (1), obviously, $n^{n^s-s}$ is odd. For (2), we see $$\frac{n^k}{k}-1<\frac{n^k-n^s}{n^s(n-1)}<\frac{n^k}{k}$$so $\left\lfloor\frac{n^k}{k}\right\rfloor=\frac{n^{k-s}-1}{n-1}$ which is again odd. Finally, for (3), we see $$\frac{2^k}{k}-1<\frac{2^k-2^s}{2^s(2^r-1)}<\frac{2^k}{k}$$so $\left\lfloor\frac{n^k}{k}\right\rfloor=\frac{2^{2^s(2^r-1)-s}-1}{2^r-1}$; again odd. (It is an integer because $r \mid 2^s-s$ and $2^r \equiv 2 \pmod{r}$ so $r \mid 2^s(2^r-1)-s$.)

hajimbrak wrote: Let $n > 1$ be a given integer. Prove that infinitely many terms of the sequence $(a_k )_{k\ge 1}$, defined by \[a_k=\left\lfloor\frac{n^k}{k}\right\rfloor,\]are odd. (For a real number $x$, $\lfloor x\rfloor$ denotes the largest integer not exceeding $x$.) Proposed by Hong Kong We have 3 cases. $\boxed{Claim-1}$ If $n\equiv 1(mod2)$ $k=p^b$ where $p|n$ and p is a prime,proves that $a_k$ is odd . $\boxed{Proof}$: This is obvious as $$\left\lfloor\frac{(pa)^{p^b}}{p^b}\right\rfloor\equiv 1(mod2)$$.$\square$ $\boxed{Claim-2}$ If $n\equiv 0(mod2)$ $n=2^lm$,then if we choose $k=p^a$ such that $p|2^lm-1$ where p is a prime ,then $a_k$ is odd. $\boxed{Proof}$: Applying L.T.E $$v_p{((2^lm)^{p^a}-1)}=v_p{(2^lm-1)}+a$$$$\implies p^a|(2^lm)^{p^a}-1$$Thus we infer $\left\lfloor\frac{n^{p^a}}{p^a}\right\rfloor=\left\lfloor\frac{n^{p^a}-1}{p^a}\right\rfloor\equiv 1(mod2)$.$\square$ $\boxed{Claim-3}$ If $n=2$,$k=2^{4^a}.5$ where $a\geq1$ suffices.

Thus all claims are proved.$\blacksquare$

Andria's proof for $n = 2$ generalizes for all even $n > 2$. I think there is a mistake in his proof: he does prove that if there exists one $k > 1$ such that $k \mid 2^k - 1$, then there exist infinitely many, but it is folklore that the only solution to $k \mid 2^k - 1$ is $k = 1$ (easy by considering the smallest prime divisor $q$ of $k$, and inspecting mod $q$. Assume $n$ is even. We will find infinitely many $k$ such that $k \mid n^k - 1$, which will prove the claim, as $n^k - 1$ is odd. First, we see that there exists at least one such $k$: just pick any prime divisor of $n-1$ (here we need $n > 2$). Now, from $k$ we can generate a new number $k' = n^k - 1$. This works, as we have the lemma $a \mid b \implies n^a - 1 \mid n^b - 1$, so for $a = k$, $b = n^k - 1$ we have $n^k - 1 \mid n^{n^k - 1} - 1$. $n$ equals $2$ has been covered by previous solutions.

Here is a solution I found : Case $1:$ $n$ is odd then let $p$ be a prime divisor of $n $ and note that $a_{p^m}$ satisfies the condition of the problem $\forall m\in N$. Case $2:$ n is even then note that $(n-1)^m|n^{(n-1)^m}-1 \forall k\in N $ so$ n^{(n-1)^m}=q(n-1)^m+1$ where q is odd hence $a_{(n-1)^m}$ satisfies the condition of the problem $\forall m\in N$ .

If $n$ is odd, pick $k=n^x$ to get \[\left\lfloor\frac{n^{n^{x}}}{n^x}\right\rfloor=n^{n^x-x}\]which is odd. If $n$ is even, pick $k=n^{2m}(n+1)$ to get \[\left\lfloor\frac{n^{n^{2m}(n+1)-2n}}{n+1}\right\rfloor\]Since $x^{2m}(x+1)-2m$ is even, $n^{n^{x^{2m}(x+1)-2m}}\equiv 1\pmod {n+1}$. Thus, \[\left\lfloor\frac{n^{n^{2m}(n+1)-2n}}{n+1}\right\rfloor=\frac{n^{n^{2m}(n+1)-2n}-1}{n+1}\]which is odd.

For odd $n$, set $k$ to be any power of $n$. For even $n$, let an odd prime $p$ divide $n^n - 1$ (which exists by Zsigmondy) and take $k = p^r\cdot n^{n\cdot p^r}$ for integers $r > 1434$ so that $$\left\lfloor \frac{n^k}{k}\right\rfloor = \frac{n^{p^r\cdot n^{n\cdot p^r}} - n^{n\cdot p^r}}{p^r\cdot n^{n\cdot p^r}}$$ is odd.

Talk about ad-hoc constructions For odd $n$, just let $k$ be any power of $n$. For even $n$, we essentially force $n^k \equiv 2^{\nu_2(k)} \pmod k$. Because the LHS is obviously greater, it suffices to have $k \mid n^k - 2^{\nu_2(k)}$. In particular, let $k = 2^r \cdot p$ for prime $p$. Then it suffices to have $$k \mid n^{2^r \cdot p} - 2^r \iff 2^r \equiv n^{2^r} \pmod p.$$We can construct infinitely many $k$ by fixing a $d$ and $p \mid n^{2^d} - 1$; then, for any $r > d$ with $p-1 \mid r$, it follows that $$2^r \equiv 1 \equiv n^{2^d} \equiv n^{2^r}.$$As there are infinitely many $r$, there are also infinitely many $k$.

For an odd $n$, take $k = p^{\ell}$ for any $\ell \ge 0$ where $p \mid n$. So assume $n$ even and let $r$ be the remainder when $n^k$ is divided by $k$. To deal with $n = 2$, take $k = 4^{\ell} \cdot 3$ for any $\ell \ge 1$. Now fix $v_2(k) = v$. Claim: If $n^k \equiv 2^v \pmod k$, then $k$ works. Proof: We know that \[\left\lfloor \frac{n^k}{k} \right\rfloor = \frac{n^k-2^v}{k}\]Note that $v_2(n^k-2^v) = 2^v$ since $v_2(n^k) > v$ since $k > v$ for any positive integer $k$. Thus the fraction must be odd. $\square$ Let $k = 2^v \cdot p$ for some prime odd $p$. It suffices, by Chinese Remainder Theorem, to find infinite pairs $(v,p)$ such that \[n^{v \cdot p} \equiv 2^v \pmod p \iff n^v \equiv 2^v \pmod p\]Thus to finish just take any odd prime $p \mid n^v-2^v$. Such a $p$ must exist for sufficiently large $v$ by the following reason. If $v_2(n) > 1$, then $v_2(n^v)>v_2(2^v)$, so $n^v-2^v$ factors into $2^v$ times an odd number greater than $1$. On the other hand, if $v_2(n) = 1$, then $n^v-2^v = 2^v(m^v-1)$, and the second term can't also be a power of $2$ (for $v \ge 3$) by Catalan's conjecture. Thus we're done.

First off, if $n$ is odd, take $k$ as $n^x$, where $x$ is a natural number, so we have: \[ a_k = \left\lfloor \frac{n^{n^x}}{{n^x}} \right\rfloor = n^{n^x - x} \]$n^{n^x - x}$ is clearly odd since $n$ is odd, so we are done for this case. If $n$ is even, take $k$ as $(n - 1)^x$, notice that $(n - 1)^x \mid n^{(n - 1)^x} - 1$ since $n^{(n - 1)^x} = ((n - 1) + 1)^{(n - 1)^x}$, and the last term is $1$ (all others have a factor of $(n - 1)^x$), therefore, $n^{(n - 1)^x} = p(n - 1)^x + 1$, since $(n - 1)^x$ is odd, and $p(n - 1)^x$ must be odd, $p$ is odd as well. Therefore $a_k = p$, so we are done. However, if $n = 2$, $(n - 1)^x$ yields a finite result ($1$), so pick $k = 3\cdot2^{2x}$. Notice that $3 \mid 2^{3\cdot2^{2x}} - 2^{2x}$, $2^{2x} \mid 2^{3\cdot2^{2x}} - 2^{2x}$. \[ a_k = \left\lfloor \frac{2^{3\cdot2^{2x}}}{3\cdot2^{2x}} \right\rfloor = \frac{2^{3\cdot2^{2x}} - 2^{2x}}{3\cdot2^{2x}} = \frac{2^{3\cdot2^{2x} - 2x} - 1}{3} \]Since the numerator is odd, and the denominator is odd, we are done.

If $n$ is odd just pick $k=r^\theta$ where $p\mid n$ So now assume $n$ is even We are going to construct our $k$, let $k=2^m\cdot p$ with $p$ prime It suffices to prove there exists some $k$ such that $n^k\equiv 2^m \pmod k$, for this is enough to have $n^k\equiv 2^m\pmod p$, which is equivalent to $n^{2^m}\equiv 2^m\pmod p$, now we consider a prime $p$ dividing $n^{2}-1$ thus $n^{2^m}\equiv 1\pmod p$ and moreover take the desired $m$ such that $p-1\mid m$, in this way we have both $n^{2^m}$ and $2^m$ are $\equiv 1\pmod p$ so now we only vary $m$ over multiples of $p-1$ and we find infinitely many $k$

We use casework on the possibilities for $n$: $n$ odd: Simply let $k$ be any power of $n$. $n$ even greater than 2: Let $p$ be an odd prime factor of $n-1$, and suppose $k = 2^{(p-1)a} \cdot p$ for a positive integer $a$. Notice \[n^k \equiv \begin{cases} 0 & \pmod{2^{(p-1)a}} \\ 1 & \pmod p \end{cases} \implies n^k \equiv 2^{(p-1)a} \pmod k\] by CRT, so our expression can be written as \[\left\lfloor\frac{n^k}{k}\right\rfloor = \frac{n^k - 2^{(p-1)a}}{2^{(p-1)a} \cdot p} = \frac{\frac{n^k}{2^{(p-1)a}}-1}{p} = \frac{\text{odd}}{\text{odd}} = \text{odd}.\] $n=2$: Use the same process with $k = 2^{2a} \cdot 3$. $\blacksquare$

If $n$ is odd then $k = n^a$ for any $a$ suffices. Suppose $n = 2$. We pick $k = 2^{2a} \cdot 3$ for arbitrary $a.$ Indeed this works because, $$\left\lfloor\frac{2^{3 \cdot 4^a-2a}}{3}\right\rfloor=\frac{2^{3 \cdot 4^a-2a}-1}{3},$$ which is clearly an odd integer. If $n > 2$ is an even integer, we take $k = (n-1)^m$ for an arbitrary $m.$ By division algorithm, we write $n^{(n-1)^m} = (n-1)^mq + r$, for $0 < r < (n-1)^m.$ Now is sufficient to show that $q$ is odd. If $q$ is even then, we see that $r$ is even too. Now, as, \[\min(\nu_2(q), \nu_2(r)) \geq\nu_2((n-1)^mq + r) = \nu_2(n^{(n-1)^m}) \geq (n-1)^m.\] This means, $\nu_2(r) \geq (n-1)^m \implies 2^{(n-1)^m} \mid r.$ But this means $(n-1)^m > r \geq 2^{(n-1)^m}$, a contradiction. Hence, $q$ is odd as needed.

Thanks to Chus for hints. For $n$ odd, choose $k=n^m$. Then $a_k= \left\lfloor \frac{n^{n^m}}{n^m} \right\rfloor = n^{n^m-m}$, which is clearly odd. For $n$ even and $n>2$, choose $k=(n-1)^m$. Let the prime factorisation of $n-1$ be $n-1=p_1^{\alpha_1} \cdots p_x^{\alpha_x}$, and note that all $p_i$ are odd. By LTE lemma, $\nu_{p_i}(n^{(n-1)^m}-1) = \nu_{p_i}(n-1) + \nu_{p_i}((n-1)^m) = (m+1)\alpha_i \geq m\alpha_i$ for all $i$, so $(n-1)^m \mid n^{(n-1)^m}-1$. It follows that $\left\lfloor \frac{n^{(n-1)^m}}{(n-1)^m} \right\rfloor = \frac{n^{(n-1)^m}-1}{(n-1)^m}$, which is odd, since $n$ is even. For $n=2$, choose $k=3 \cdot 4^m$. We claim that $3 \cdot 4^m \mid 2^{3 \cdot 4^m} - 4^m$. It is trivial that $4^m \mid 2^{3 \cdot 4^m} - 4^m$. Also, $2^{3 \cdot 4^m} = 4^{3 \cdot 2^{2m-1}} \equiv 1 \equiv 4^m$ (mod $3$). Thus, $\left\lfloor \frac{2^{3 \cdot 4^m}}{3 \cdot 4^m} \right\rfloor = \frac{2^{3 \cdot 4^m}-4^m}{3 \cdot 4^m} = \frac{2^{3 \cdot 4^m - 2m}-1}{3}$, which is odd. Hence proved. $\square$

first take n odd, and take $k=p^m $ where p is a prime factor of n and m is a suitably good number. then we are done. after that take n even. now take a odd prime $q$. now let $p$ be the zisgmondy prime of $n^{q}-1$ now take $ k= n^{(q-1)^2}p$ now we have $n^{(q-1)^2}p - (q-1)^2 \equiv n^{(q-1)^2} -(q-1)^2 \equiv 1-1 = 0$ $mod q$ here the second thing is due to the order condition that zigmondy brings. so we have $n^{n^sp}\equiv n^s (mod p)$ now we clearly we have that $\left \lfloor \frac{n^k}{k} \right \rfloor = \left \lfloor \frac{n^{n^sp - s}}{p} \right \rfloor = \frac{n^{n^sp - s} - 1}{p}$ which is obviously odd. done PS: this is soo cool.

YAY, my VERY FIRST N4. Cute problem. Construction NT is always so fun. We have three separate cases to investigate, which we shall do in increasing order of difficulty. Case 1 : $n$ is an odd positive integer. This case is very easy. Simply consider $k=n^r$ for each positive integer $r$. Then, \[ \left \lfloor \frac{n^{n^r}}{n^r} \right \rfloor = n^{n^r-r}\]which is clearly an odd positive integer. Case 2 : $n>2$ is an even positive integer. For this case, note that since $n-1 >1$, and is odd, there exists an odd prime factor $p\mid n-1$. Then, consider $k=p^r$ for each positive integer $r$. Note that since $p\mid n-1$ by Lifting the Exponent we have, \[\nu_p(n^{p^r}-1) = \nu_p(n-1)+\nu_p(p^r) > r \]So $p^r \mid n^{p^r}-1$ and $n^{p^r}\equiv 1 \pmod{p}$. Thus, \[n^{p^r} = p^r \left \lfloor \frac{n^{p^r}}{p^r} \right \rfloor +1\]which since $n$ is even implies that $\left \lfloor \frac{n^{p^r} }{p^r} \right \rfloor$ is odd as desired. Case 3 : $n=2$. For this case consider $k=4 \cdot 3^r$ for each odd positive integer $r$. Then clearly $\nu_2(2^k)=k >2$ so $4 \mid 2^k$. Further, \[\nu_3(2^{4\cdot 3^r}-1)= \nu_3(2^4-1) + \nu_3(3^r)> r\]so $3^r \mid 2^{4\cdot 3^r}-1$ and $2^{4\cdot 3^r} \equiv 1 \pmod{3^r}$. By CRT, this implies that $2^{4\cdot 3^r} \equiv 1+3^r \pmod{4 \cdot 3^r}$. Thus as before we can write, \[2^{4\cdot 3^r} = 4\cdot 3^r \left \lfloor \frac{2^{4\cdot 3^r}}{4\cdot 3^r} \right \rfloor + (1+3^r)\]To finish note that by Lifting the Exponent we also have $\nu_2(1+3^r) = \nu_2(1+3)=2$ (since $r$ is odd). Thus, dividing the above equation by 4 we conclude that $\left \lfloor \frac{2^{4\cdot 3^r}}{4\cdot 3^r} \right \rfloor$ must indeed be odd, and we are done.

Haven't written the steps in between coz I solved some part of the problem almost a month ago so I have lost my previous work for $n$ even. If $n$ is odd we take some $p\mid n$ and let $k=p^m$ and it works. Now we look at $n>2$ even, where we consider $k=p^m$ and $p$ odd, so by LTE we get $\frac{n^{p^m}-1}{p^m}\in \mathbb{Z}$, after that it is easy to check that it is indeed the value of $a_k$ and we get $a_k\mid n^{p^m}-1\implies a_k$ is odd. For $n=2$ we just let $k=2^{2m}\cdot 3$ and the rest follows by LTE as $\left \lfloor \frac{n^{2^{2m}\cdot 3}}{{2^{2m}}\cdot 3}\right \rfloor =\frac{2^{2^{2m}\cdot 3}-2^{2m}}{2^{2m}\cdot 3}$ which is odd.

Back in my high school years I was thinking of these problems as "crazy to think of this and that" and now while teaching it... it is just "try simple things like $n$ and $n-1$". Too bad the Cape Town problem (despite being nice in greedy algorithms) was selected instead, the problem here would have been a great example of an IMO number theory. If $n$ odd, pick $k$ to be a power of $n$. If $n$ is even, then as $k=n-1$ works and $k=n^z$ makes the expression an integer, it makes sense to consider $k=n^z(n-1)$. Observe that $n-1$ divides $n^{n^z(n-1) - z} - 1$ and that $n^z(n-1) \geq 2^z > z$, so for $n\geq 4$ the floor is $\frac{n^{A}-1}{n-1} = n^{A-1} + n^{A-2} + \cdots + n + 1$ and is odd for even $n$. Finally, for $n=2$ pick $k=2^{z} \cdot 3$. Note that $3$ divides $n^{2^z \cdot 3 - z} - 1$ if and only if $z$ is even and in that case the ratio $\displaystyle \frac{n^{2^z \cdot 3 - z} - 1}{n-1}$ is odd, since the numerator and denominator are both odd.

v_Enhance wrote: Suppose $n$ is even now. Then by Kobayashi's Theorem, there exist infinitely many primes $p$ dividing some number of the form \[ n^{n^r-1} - 1. \]for some integer $r$. Let $p > n$ be such a prime, with corresponding integer $r$. It then follows that \[ n^{n^rp} \equiv n^r \pmod{n^rp} \]since this is clearly correct mod $n^r$, and also correct modulo $p$. Sorry, can someone please explain why this is correct mod p?