Show that a set $ S_m $ is equal to $ \mathbb{Z_m} $

Question

Problem:

Let $$ {S_m} = \left\{ \left[ \frac{k(k+1)}{2} \right]_{\pmod{m}} \mid k \in \mathbb{N} \right\}.$$ Show that $ S_m = \mathbb{Z}_m $ if and only if $ m = 2^s $ for some $ s \in \mathbb{N}.$

Attempted solution:

First we observe that for each prime $ p > 2 $ there exists a $ b \in \mathbb{Z_p} $ such that $ x^2 = b \pmod{p}$ has no solutions.

So $m$ can't be a prime, which is excluded if $ m = 2^s $. Now I'm stuck, I don't know how to approach this problem. Any hints?

Muchos gracias!

Answer 1

You can easily show that if $S_m=\mathbb Z_m$ and $n\mid m$ then $S_n=\mathbb Z_n.$

Now, if $n$ is odd, then $8$ is invertible modulo $n$ and $$8^{-1}\left((2k+1)^2-1\right)\equiv \frac{k(k+1)}2\pmod n$$

The squares modulo $n$ take at most $(n+1)/2$ distinct values, and thus $\frac{k(k+1)}2$ modulo $n$ can take at most $(n+1)/2$ distinct values. Thus, when $n>1$ is odd, though can’t have $S_n=\mathbb Z_n.$

Now, if $m$ has an odd prime factor, we again get that $S_m\neq \mathbb Z_m.$

So if $\mathbb S_m=\mathbb Z_m$ we must have that $m$ is a power of $2.$

I’ll leave the other direction to you. Hint: do it by induction on $s.$