ISL 2014 N4

Let $n>1$ be a given integer. Prove that infinitely many terms of the sequence $\left(a_{k}\right)_{k \geqslant 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$.) (Hong Kong)