Belarus — Selection and Training Session

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$.)