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

1 Answers 1

2

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

  • 0
    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.2012-09-06