Pascal's triangle modulo 2002: periodic, not merely eventually periodic

soup%any·Jan 29, 2025(edited)

A finite-state argument should give eventual periodicity of the binomial sequence. Is there a reason it is periodic from the very first term rather than after a transient? Problem: Show that the sequence

\left(\begin{array}{l} 2002 \\ 2002 \end{array}\right),\left(\begin{array}{c} 2003 \\ 2002 \end{array}\right),\left(\begin{array}{l} 2004 \\ 2002 \end{array}\right), \ldots

considered modulo

2002

, is periodic. Source: Baltic Way 2002 mathematical team contest · MNET-012G

Open MNET-012G in the question bank →

4 replies

eevee.zip·Jan 29, 2025

Track the vector

(\binom n0,\binom n1,\dots,\binom n{2002})

modulo 2002. Pascal updates each coordinate by adding the previous coordinate, simultaneously.

soup%any·Jan 30, 2025

The update matrix is lower triangular with diagonal entries 1. So it is invertible even modulo a composite number?

eevee.zip·Jan 30, 2025

Yes: recover coordinates in increasing order by subtraction. It is a permutation of a finite state space, so every orbit is a cycle from the outset. Project onto the last coordinate and start at n=2002.

parry_this·Jan 30, 2025

This avoids dividing by 2002!, which is not invertible modulo 2002. The state argument proves existence of a period without claiming it is the smallest one.

Join the discussion

A hint, a different approach, or a thoughtful question can help.

Loading discussion…