MathNet 2016-part-03 — 184 problems (EN–VI) Question 104

Let $M$ be the set of the natural numbers $k$ for which there exists $n \in \mathbb{N}$ such that the remainder of $3^n$ when divided by $n$ is $k$. Show that $M$ is infinite.