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=\lfloor \frac{n^k}{k}\rfloor ,$$ are odd. (For a real number $x$, $\lfloor x\rfloor$ denotes the largest integer not exceeding $x$.)