2
$\begingroup$

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$?
$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – dcdo Sep 4 '12 at 22:43
  • $\begingroup$ 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$. $\endgroup$ – Gerry Myerson Sep 5 '12 at 2:55
  • $\begingroup$ 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. $\endgroup$ – dcdo Sep 6 '12 at 0:01

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.