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
    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_2$ is periodic with length 2 but $\left< \left_7 \right>_2$ is be periodic with length 7.2012-09-04
  • 0
    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$.2012-09-05
  • 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