Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
If $am=an$ then $a(m-n)=0$ but $(a,N)=1$ so $m=n$. – Gerry Myerson Aug 26 '12 at 11:32
up vote 1 down vote accepted

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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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