Fibonacci Numbers and Binomial Coefficients Mod n

Eric Rowland
Rutgers University

In some sense, one can measure the complexity of a sequence {a[n]} of integers by examining the sequence {Mod[a[n],n]} obtained by reducing the nth term modulo n. When a[n] is a polynomial, the sequence {Mod[a[n],n]} is quite simple—it is constant for sufficiently large n. But even slightly less pedestrian sequences give rise to complex behavior. The familiar Fibonacci numbers and the binomial coefficients both result in tantalizing sequences when reduced termwise modulo n. I will discuss the patterns that can be seen in these sequences and how they suggest (as yet unknown) computationally reduced formulas for Mod[Fibonacci[n],n] and Mod[Binomial[n,m],n].

Created by Mathematica  (April 20, 2004)