# 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.

## 1 Answer

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 Jun 26 '17 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 Jun 26 '17 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 Jun 26 '17 at 11:05