# Finding the periods of a sequence of integers reduced mod m

I'm interested to know if there is a standard method to prove that a given sequence of integers has period $p_m\in \mathbb{Z}$ when reduced modulo $m\in\mathbb{Z}$.

For example, let $t_n=\dfrac{n(n+1)}{2}$ be the sequence of triangular numbers. Then by examination it appears that the period $p_m$ is given by $m$ when $m$ is odd and $2m$ when $m$ is even.

I suppose that a proof using divisibility arguments is possible, but I'm not sure how to start. References for books or articles that discuss this topic would be greatly appreciated.

To prove that $t_n$ is periodic when reduced modulo $m$, we can use the recurrence relation $t_n=t_{n-1}+n$, or a bootstrapping argument, but I don't see how either method can give the actual lengths of the periods.

• Noting that $t_n=\binom{n+1}2$ (binomial coefficient), we have $\binom{n+p}2=\binom n2+np+\binom p2$, and we want this to be $\binom n2$, modulo $m$, for all $n$. Setting $n=0$, we find that $\binom p2$ must be a multiple of $m$; then setting $n=1$, we find that $p$ must be a multiple of $m$; and these two conditions are clearly sufficient as well as necessary. So we want to find the smallest $p$ such that both $p$ and $\binom p2$ are multiples of $m$. Commented Jan 4, 2023 at 20:12
• If $m=2k$ is even, then $p=m$ doesn't work, because $\binom m2/m=(2k-1)/2$ which is not an integer; and $p=2m$ does work, because $\binom{2m}2/m=4k-1$ which is an integer. If $m=2k+1$ is odd, then $p=m$ does work, because $\binom m2/m=k$ which is an integer. Commented Jan 4, 2023 at 20:13

There is no simple general method.

Consider the sequence $t_n = a^n$ where $\gcd(a,m)=1$. The period of this sequence mod $m$ is the order of $a$ mod $m$ and there is no known formula for that, not even for $a=2$ and $m$ prime.

• – lhf
Commented Jun 26, 2017 at 10:47
• Wow it's very interesting to see the relation to primitive roots and Artin's conjecture, thank you for the references. I wonder still about examples like the triangular numbers, whose periods seem to follow a simple pattern, and how to prove that it always holds.
– M_B
Commented Jun 26, 2017 at 10:56
• @M_B, I don't think there is a simple general formula for the period mod $m$ of the values of a polynomial with integer coefficients. I'd love to see one, though.
– lhf
Commented Jun 26, 2017 at 11:05

Let's consider sequences defined by integer-valued polynomials. These have the form

$$n\mapsto\sum_ka_k\binom nk$$

with integer coefficients $$a_k$$. So a good start would be to find the periods of binomial coefficients $$\binom nk$$ modulo $$m$$.

We'll use a formula similar to the binomial formula itself, $$(n+p)^k=\sum_j\binom kjn^{k-j}p^j$$:

$$\binom{n+p}{k}=\sum_j\binom n{k-j}\binom pj$$ $$=\binom nk+\binom n{k-1}p+\binom n{k-2}\binom p2+\binom n{k-3}\binom p3+\cdots \\ +\binom n3\binom p{k-3}+\binom n2\binom p{k-2}+n\binom p{k-1}+\binom pk$$

For $$p$$ to be a period of the sequence, we need $$\binom{n+p}k$$ to be congruent to $$\binom nk$$ for all $$n$$. Set $$n=0$$ to eliminate most of the terms in the above expansion, and find that $$\binom pk$$ must be congruent to $$0$$ (i.e. must be a multiple of $$m$$). Then set $$n=1$$ to eliminate a different set of terms, and find that $$\binom p{k-1}$$ must be congruent to $$0$$. Proceed in this way, up to $$n=k-1$$, and find that $$p$$ must be congruent to $$0$$. So these congruences are both necessary and sufficient for $$p$$ to be a period of $$\binom nk$$:

$$p\equiv\binom p2\equiv\binom p3\equiv\cdots\equiv\binom p{k-1}\equiv\binom pk\equiv 0$$

Note that $$p=k!m$$ is one valid period. And it's clear from these congruences that a period of $$\binom n{k+1}$$ is also a period of $$\binom nk$$.

But we want the smallest period. Here's a table of that (with $$k$$ on the left and $$m$$ on the top):

$$\begin{array}{c|c c c c c c c c c} & 1&2&3&4&5&6&7&8&9 \\\hline 0 & 1&1&1&1&1&1&1&1&1 \\ 1 & 1&2&3&4&5&6&7&8&9 \\ 2 & 1&4&3&8&5&12&7&16&9 \\ 3 & 1&4&9&8&5&36&7&16&27 \\ 4 & 1&8&9&16&5&72&7&32&27 \\ 5 & 1&8&9&16&25&72&7&32&27 \\ 6 & 1&8&9&16&25&72&7&32&27 \\ 7 & 1&8&9&16&25&72&49&32&27 \\ 8 & 1&16&9&32&25&144&49&64&27 \\ 9 & 1&16&27&32&25&432&49&64&81\end{array}$$

The row $$k=2$$ was established in comments, and the column $$m=2$$ in this post. A pattern is evident in the table: Going down, $$p$$ gets multiplied by a prime factor of $$m$$ when $$k$$ reaches a power of the same prime. But I haven't proven this.