0
$\begingroup$

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 ?

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ This is essentially a special case of the 2nd proof of the basic Lemma linked in my answer. It's best to encapsulate these basic properties in Lemmas, Theorems etc for convenient reuse, not to repeat their proofs inline every time we need to invoke them - that's what abstraction is all about (in the language of abstract algebra it bolls down to Euclidean domains are PIDs, but one doesn't need to know that to understand the very simple linked proofs - including a one line proof). $\endgroup$ Oct 22 '20 at 7:58
0
$\begingroup$

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

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