# Triangular numbers modulo powers of 2 and its generalizations

Someone discussed with me an interesting problem that he was working on with his students. They found that the congruence
$\frac{1}{2}X(X+1) \equiv a \pmod{n}$
has a solution for every $0 \le a < n$ if and only if $n =2^k$.

My first instinct of course was to complete the squares for triangular numbers and reduce the problem to $X^2 \equiv a \pmod{n}$.
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:
$\{ \frac{x(x-1)}{2} \pmod{2^k} \} = \{0, 1, \ldots, 2^k-1 \}$

Knuth gave a slick proof which can be easily adapted and generalized to the following:
For a prime $p, 1 \le m < p, k \ge 1,$
$\{ px^2+mx \pmod{p^k} \} = \{0, 1, \ldots, p^k-1 \}$

Proof: Suppose
$px^2+mx \equiv py^2+my \pmod{p^k}$
$(x-y) ( p(x+y)+m) \equiv 0 \pmod{p^k}$
Since $p \nmid p(x+y)+m$ we can conclude that
$x \equiv y \pmod{p^k}$.

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

This entry was posted in Number Theory, Quotes/People. Bookmark the permalink.