Let $(f_1, f_2, \ldots, f_n)$ be an $n$-tuple of functions mapping non-negative integers to non-negative integers. Let $m$ be a positive integer.Suppose there exists a function $f$ apping non-negative integers to non-negative integers such that:
$$[f_1(a_1) + f_2(a_2) + \cdots + f_n(a_n)] \bmod{m}= f[(a_1 + a_2 + \cdots + a_n) \bmod{m}].$$
Mod here is used as a function. Can one find or describe all such $n$-tuples with the following characteristics?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
You can view $f$ and all the $f_i$ as functions $\mathbb{N}\cup\{0\}\to\mathbb{Z}/m$. Do so. For $n=1$ every $f_1$ will do. I am assuming now $n\geq 2$.
Note that replacing each $f_i$ by $f_i-f_i(0)$ and $f$ by $f-\sum f_i(0)$ will not change the desired property, so assume $f_i(0)=0$.
Choosing $a_i=x$, $a_j=0$ for $j\neq i$ we see that $f(x)=f_i(x)$. Thus all the $f_i$ are the same and equal $f$. I will drop the index $i$ of the $f$'s. Fix $a_i=0$ for $i\geq 3$. Get $f(x)+f(y)=f(x+y)$. Denote $a=f(1)$ and prove by induction that $f(x)=xa$.
Conclude: as functions $\mathbb{N}\cup\{0\}\to\mathbb{Z}/n$ all the $f_i$ are given by "affine maps" $x\mapsto xa+b_i$ for some $a,b_i\in\mathbb{Z}/m$ (same $a$ and $b_i=f_i(0)$).
Finally, observe that every $a,b_i\in \mathbb{Z}/m$ will result in a good definition of $f_i(x)=xa+b_i$, $f=xa+\sum b_i$, so the answer is complete.
