# 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

## 1 Answer

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

• Thanks again for the help. This is much simpler than what I originally wrote down last night while thinking about the problem. – dcdo Aug 26 '12 at 13:17