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!

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

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

  • $\begingroup$ 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 $? $\endgroup$
    – Oskar
    Feb 9, 2021 at 12:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.