2

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.

M_B
  • 475
  • 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$. – mr_e_man Jan 04 '23 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. – mr_e_man Jan 04 '23 at 20:13

2 Answers2

3

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
  • 216,483
  • See also https://oeis.org/A014664 and https://mathoverflow.net/questions/60441/the-multiplicative-order-of-2-modulo-primes. – 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
  • 1
    @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
1

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.

mr_e_man
  • 5,364