3
$\begingroup$

My question is motivated by the following fact (for a couple of proofs see my answer at MSE 1926967; note that this fact also answers the $\ell = 1$ case of MO 265513):

Fact. The set of triangular numbers modulo $n$ yields $\mathbb{Z}/n\mathbb{Z}$ iff $n$ is a power of $2$.

My specific question is whether there is a straightforward way to describe this set given, for example, the prime factorization of $n$. But I also have the broader question:

What else can be said about the set of triangular numbers modulo $n$ as a function of $n$?

For example, when $n$ is odd, we might expect the set to have cardinality around $(n+1)/2$. To illustrate this by way of example, consider $n = 11$, and the first $11$ counting numbers each reduced modulo $11$:

$$1, 2, 3, 4, 5, -5, -4, -3, -2, -1, 0$$

However many distinct elements we have after the first $(n+1)/2$ triangular numbers will be the final total, since (as suggested by the negative notation above) the elements reverse course thereafter, and wend their way back to $0$ at which point they reset as they have formed a cycle.

But I am not only interested in an estimate of the cardinality based on $n$'s parity; I am hoping for the whole shebang! In that spirit:

Q. How can we describe the set of triangular numbers modulo $n$ given $n$'s prime factorization?

$\endgroup$
2
$\begingroup$

Fix $n=p_1^{\alpha_1}\ldots p_k^{\alpha_k}$. We want to know for which $b$ the equation $$ a(a+1)/2=b $$ has a solution modulo $n$. By the Chinese remainder theorem, this happens iff it has a solution mod $p_i^{\alpha_i}$ for each $i$. Consider one of these prime powers. If $p_i=2$ then there is always a solution, as mentioned in your question. Suppose $p_i\neq2$. The equation is equivalent to $$ (2a+1)^2=8b+1. $$ Let $8b+1=x_ip_i^{\beta_i}$ where $p_i\not\mid x_i$. If $\beta_i\geq\alpha_i$ we can take $2a+1=p^{\alpha_i}$. Otherwise $\beta_i$ must be even, and in this case by Hensel's lemma, there is a solution iff $x_i$ is a quadratic residue mod $p_i$. Therefore the residues of triangular numbers mod $n$ are exactly $$ \left\{b\,\left|\,\left(\frac{x_i}{p_i}\right)=1\text{ and }\beta_i\text{ is even for each }i\text{ with }\beta_i<\alpha_i\text{ and }p_i\neq2\right.\right\} $$ where $\left(\frac{x}{p}\right)$ is the Legendre symbol. I don't think there is a closed form expression for the Legendre symbol, but quadratic reciprocity gives an algorithm for calculating it.

$\endgroup$
  • $\begingroup$ Awesome. Three questions: (a) What happens in the case of $n$ even but not a power of $2$? (b) Does the re-framing of these residues using the Legendre symbol speed anything up computationally in generating this set (as compared to, e.g., directly computing them as sums modulo $n$)? (c) For a sample consideration such as the one initially posted -- expected cardinality of the set for some given $n$ and its prime factorization -- is there a way to carry out this estimate using the methods you outline here? $\endgroup$ – Benjamin Dickman Sep 27 '16 at 0:33
  • 1
    $\begingroup$ (a) The last equation is still valid when $p_1=2$, there is just no condition imposed by $p_1$. That is, $b$ is a triangular number mod $n$ iff it is triangular mod $n'$ where $n'$ is the odd part of $n$. (b) My guess is computing sums modulo $n$ is faster if you want all the residues, while the above would be better for testing a particular number $b$. (c) It should be possible to calculate using these methods (there are $(p+1)/2$ quadratic residues mod $p$ including $0$, when $p$ is an odd prime). $\endgroup$ – stewbasic Sep 27 '16 at 23:58
  • $\begingroup$ Actually, the equation is equivalent to $(2a+1)^2=8b+1 \pmod{p_i^{\alpha_i}}$. If $8b+1$ is a quadratic residue, then we can always solve for $a$, since $(8, p_i^{\alpha_i})=1$ $\endgroup$ – steven gregory Aug 17 '17 at 14:52
  • $\begingroup$ @stevengregory Yes, I think this is implicit in my answer; the condition "$\beta_i\geq\alpha_i$ or ($\left(\frac{x_i}{p_i}\right)=1$ and $\beta_i$ is even)" is equivalent to $8b+1$ being a quadratic residue mod $p_i^{\alpha_i}$. $\endgroup$ – stewbasic Aug 17 '17 at 22:10

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.