# Proof for length of period in simple modulo $N$ sequence.

I am looking for a concise proof that the length of the smallest period of the sequence $$f[n] = a n \pmod N$$ is $N$ if $(a,N) = 1$. From the Pigeonhole Principle, it is not hard to show that $f[n]$ is periodic with $N$, but how do I know that it is not periodic with a number $M < N$. Is a proof by contradiction the way to go?

I found a lemma in the proof of Fermat's Theorem here, that takes me most of the way by arguing that of $1a, 2a, 3a, \ldots, (N-1)a$ are not congruent modulo $N$ if $(a,N)=1$. This question seems so trivial and is used in discussions of the periodicity of sequences so I thought there might be several ways to show it to be true.

-
If $am=an$ then $a(m-n)=0$ but $(a,N)=1$ so $m=n$. –  Gerry Myerson Aug 26 '12 at 11:32

If $an=f[n]=f[0]=0\pmod N$ for some period $n$, then $N$ divides $an$. Since $a$ is coprime to $N$, $N$ divides $n$.