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

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!

• @carlo Isn’t it $\sum_n n?$ Feb 8, 2021 at 19:03
• Just a thought: it might be useful to write $\frac{k(k + 1)} 2 = \sum_{n = 0}^k n.$ Feb 8, 2021 at 19:07

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.$$

• How do you conclude that the squares modulo $n$ takes at most $(n+1)/2$ distinct values and how do you draw the conlusion that if $m$ has an odd prime factor, we get $S_m \neq \mathbb{Z}_m$? Feb 9, 2021 at 12:53