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
[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].

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

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>