Someone discussed with me an interesting problem that he was working on with his students. They found that the congruence

[tex] \frac{1}{2}X(X+1) \equiv a \pmod{n} [/tex]

has a solution for every [tex] 0 \le a < n [/tex] if and only if [tex] n =2^k[/tex].

My first instinct of course was to complete the squares for triangular numbers and reduce the problem to [tex] X^2 \equiv a \pmod{n} [/tex].

This turn out to work well for odd modulus and the solutions for triangular numbers and squares correspond. But when the modulus was a power of 2, completing the square would not work. A simple search found a few websites where the phenomenon was recorded and it seems a (perhaps original?) source is Knuth’s the Art of Computer Programming Volume 3, Section 6.4, Exercise 20. Knuth was talking about hashing but essentially the exercise is the above problem. I prefer to rephrase it as for every positive integer k, these two sets are identical:

[tex] \{ \frac{x(x-1)}{2} \pmod{2^k} \} = \{0, 1, \ldots, 2^k-1 \} [/tex]

Knuth gave a slick proof which can be easily adapted and generalized to the following:

For a prime [tex] p, 1 \le m < p, k \ge 1,[/tex]

[tex] \{ px^2+mx \pmod{p^k} \} = \{0, 1, \ldots, p^k-1 \} [/tex]

Proof: Suppose

[tex] px^2+mx \equiv py^2+my \pmod{p^k} [/tex]

[tex] (x-y) ( p(x+y)+m) \equiv 0 \pmod{p^k}[/tex]

Since [tex] p \nmid p(x+y)+m [/tex] we can conclude that

[tex] x \equiv y \pmod{p^k}[/tex].

So each of [tex]x = 0, 1, \ldots p^k-1 [/tex] gives rise to a different value of [tex] px^2+mx \pmod{p^k}[/tex].