67th NMO Selection Tests for JBMO

Let $j$ be a fixed positive integer and $p>2$ a prime so that $2^{j}p>3^{2^j}$. Then $3^{2^j}(3^{2^j(p-1)}-1)\equiv 0(\mathrm{mod}{2}^{j}p)$, because $2\phi (2^{j}p)=2^j(p-1)$. Hence $3^{2^{j}p}\equiv 3^{2^j}(\mathrm{mod}{2}^{j}p)$, so, for $n=2^{j}p$, one has $r_n=3^{2^j}$. It follows that $3^{2^j}\in M$, for all $j\in {\mathbb{N}}^{\ast }$, so $M$ is an infinite set.

Alternative Solution: Choosing $n=2\cdot 3^j$, the remainder $r_n$ of $3^n$ when divided by $n$ verifies $r_n\ne 0$, $r_n\equiv 0(\mathrm{mod}{3}^j)$, so $r_n\ge 3^j$ (in fact $r_n=3^j$). Therefore, $M$ contains arbitrarily large numbers, so it is infinite.