This question was left as homework by my instructor and he didn't discussed it.
An arithmetical function f is called periodic mod k if k>0 and f(m) =f(n) whenever m$\equiv$ n (mod k). The integer k is called a period of f.
(i) If f is periodic mod k, prove that f has a smallest positive period $k_{0}$ and $k_{0}$ |k.
Attempt : by well ordering principle there exists a smallest period $k_{0}$ .
Now, m$\equiv$ n (mod k) => f(m) =f(n) => m$\equiv$ n (mod $k_{0}$ => m-n = $k_{0}$ x,$ m-n =k_{1} y$ , which implies $k_{0} x = k_{1} y$ and $k_0 < k_{1}$ implies that x>y , but I am still not getting that y divides x to prove what is asked.
Can you please help in deducing that ?
Best Answer
One could perhaps try a proof by contradiction. Assume that $k_0 \nmid k_1$. Then there are integers $q,r$ with $0 < r < k_0$ such that $k_1 = qk_0 + r$.
Given any positive integer $x$, there are integers $q',r'$ with $0 \leq r' < r$ such that $x = q'r + r'$. Therefore $$ f(x) = f(q'r + r') = f(q'(k_1-qk_0) + r') = f(q'k_1 - q'qk_0 + r'). $$
Since both $k_0$ and $k_1$ are periods of $f$, $f(q'k_1 - q'qk_0 + r') = f(r')$. Thus for any positive integer $x$, $f(x) = f(r')$, where $x \equiv r'~(mod~r)$. This means that $r$ is a period of $f$ that is smaller than $k_0$, contradicting the choice of $k_0$.