2
$\begingroup$

How does one determine the length of the smallest period of the following sequence: $f[n] = \left< n \right>_N - \left< n \right>_M$ where $\left_N$ represents $n \pmod N$ and $\left_M$ represents $n \pmod M$. It is clear that $N$ is the period length of the sequence generated by $\left< n \right>_N$ and $M$ is the period length of the sequence generated by $\left_M$. It would not be too difficult to show that $f[n]$ is periodic with $NM$, but this may not be the smallest period.

My initial reaction is that the period length of $f[n]$ is the least common multiple of $N$ and $M$, but how does one go about showing this?

1 Answers 1

2

You're right: $f$ is periodic of period $L=\mbox{lcm}(N,M)$. To prove this:

  • First establish that $L$ is a period for $f$: prove that $f(n+L)=f(n)$ for all $n$.

  • Next establish that no number less than $L$ is a period for $f$: find all $n$ for which $f(n)=f(0)=0$.