Tag Archives: Dynamical systems

Generalizations of Fermat’s Little Theorem and combinatorial zeta functions

Everyone who studies elementary number theory learns two different versions of Fermat’s Little Theorem:

Fermat’s Little Theorem, Version 1: If p is prime and a is an integer not divisible by p, then a^{p-1} \equiv 1 \pmod{p}.

Fermat’s Little Theorem, Version 2: If p is prime and a is any integer, then a^{p} \equiv a \pmod{p}.

as well as the following extension of Version 1 of Fermat’s Little Theorem to arbitrary positive integers n:

Euler’s Theorem: If n is a positive integer and (a,n)=1, then a^{\phi(n)} \equiv 1 \pmod{n}, where \phi is Euler’s totient function.

My first goal in this post is to explain a generalization of Version 2 of Fermat’s Little Theorem to arbitrary n. I’ll then explain an extension of this result to m \times m integer matrices, along with a slick proof of all of these results (and more) via “combinatorial zeta functions”.

Continue reading →