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.

What is the length of the smallest period of the following sequence $$f[n] = \left< \left< n \right>_N \right>_M$$ where $\left<n\right>_N$ represents $n \pmod N$. Is there a special term for performing nested modulo operations?

For $N$ even (say 8) and $M = 2$, it appears that the sequence is periodic with length 2. But for $N$ odd, it seems the least period length is $N$. So this leads me to believe that if $N$ is coprime to $M$ then the least period length is $N$.

  1. How do I go about showing this to be the case if it is indeed true?
  2. How do I, in general, calculate the least period for $f[n]$ for arbitrary cases of $N$ and $M$?
share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

Presumably, by $\langle n\rangle_N$ you mean the remainder on dividing $n$ by $N$, so, for example, $\langle 5\rangle_6=5$, $\langle 7\rangle_6=1$, $\langle 6\rangle_6=0$ (or maybe you want $\langle 6\rangle_6=6$, but it won't make any difference in what follows). Then the sequence $\langle n\rangle_N$ is $0,1,2,3,\dots,N-2,N-1,0,1,2,\dots$ and has period $N$. It follows that $\langle\langle n\rangle_N\rangle_M$ has period at most $N$. It has period less than $N$ if, and only if, $M$ is a proper divisor of $N$, since that breaks the $0,1,2,\dots,N-1$ up into repeating pieces of length $M$. So the answer is, the period is $M$ if $M$ is a factor of $N$, otherwise, $N$.

share|improve this answer
    
Could you elaborate on the "breaking up" process? I agree that this is the case, it is just fascinating to me only a few weeks into elementary number theory that $\left<n\right>_2$ is periodic with length 2 but $\left< \left<n\right>_7 \right>_2$ is be periodic with length 7. –  dcdo Sep 4 '12 at 22:43
    
Easier to show an example than to put it into words. Take $\langle\langle n\rangle_8\rangle_2$. From $\langle n\rangle_8$ we get $0,1,2,3,4,5,6,7,0,1,2,3\dots$. Viewing this modulo 2, the period $0,1,2,3,4,5,6,7$ breaks up into $0,1$ then $2,3$ then $4,5$ then $6,7$ which is $0,1,0,1,0,1,0,1$. –  Gerry Myerson Sep 5 '12 at 2:55
    
Thanks for the answer. I will work out a few other examples on paper now with numbers other than 2 just to be sure that I understand. –  dcdo Sep 6 '12 at 0:01
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.