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.

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

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.