1
$\begingroup$

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.

  • 0
    If $am=an$ then $a(m-n)=0$ but $(a,N)=1$ so $m=n$.2012-08-26

1 Answers 1

1

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$.

  • 0
    Thanks again for the help. This is much simpler than what I originally wrote down last night while thinking about the problem.2012-08-26