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 \pmod{2^j p}$, because $2\varphi(2^j p) = 2^j(p-1)$. Hence $3^{2^j p} \equiv 3^{2^j} \pmod{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}^*$, 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 \neq 0$, $r_n \equiv 0 \pmod{3^j}$, so $r_n \ge 3^j$ (in fact $r_n = 3^j$). Therefore, $M$ contains arbitrarily large numbers, so it is infinite.