2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ See also oeis.org/A014664 and mathoverflow.net/questions/60441/…. $\endgroup$ – lhf Jun 26 '17 at 10:47
  • $\begingroup$ 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. $\endgroup$ – M_B Jun 26 '17 at 10:56
  • 1
    $\begingroup$ @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. $\endgroup$ – lhf Jun 26 '17 at 11:05

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.