# Method for determing least period length of sequence that is the sum of two modulo sequences.

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\right>_N$ represents $n \pmod N$ and $\left<n\right>_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<n\right>_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 Answer

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