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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

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.