# Proving that smallest period divides every other period

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.

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$$.
Hint: the periods set $$P$$ is nonempty & closed under subtraction $$>0\,$$ $$(k>\bar k\in P\Rightarrow k\!-\!\bar k\in P),\,$$ so the least period divides every period by a fundamental Lemma (which has a one-line proof).