Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
add comment

1 Answer

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|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
add comment

Your Answer

 
discard

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.