littletush wrote: Given an integer $n\ge 2$, a function $f:\mathbb{Z}\rightarrow \{1,2,\ldots,n\}$ is called good, if for any integer $k,1\le k\le n-1$ there exists an integer $j(k)$ such that for every integer $m$ we have \[f(m+j(k))\equiv f(m+k)-f(m) \pmod{n+1}. \] Find the number of good functions. if $n+1$ is a prime, the number of good function is $n*\phi(n)$, there's no such function otherwise

How did you get the answer?I think that it's connected with primitive roots

littletush wrote: Given an integer $n\ge 2$, a function $f:\mathbb{Z}\rightarrow \{1,2,\ldots,n\}$ is called good, if for any integer $k,1\le k\le n-1$ there exists an integer $j(k)$ such that for every integer $m$ we have \[f(m+j(k))\equiv f(m+k)-f(m) \pmod{n+1}. \] Find the number of good functions. The idea is considering iterations of $j(k)$. Step 1: $f$ is a surjective function and has a (minimum) period $n$. Proof: Let $m \in \mathbb{Z}$ be any integer and assume $\exists k$ such that $1\leq k \leq n-1$ and $f(m+k)=f(m)$. Then $f(m+j(k)) \equiv f(m+k)-f(m) \equiv 0 \pmod{n+1}.$ Contradiction since $f(\mathbb{Z}) \subseteq \{1,2,\ldots,n\}$. Thus $f(m),f(m+1),...,f(m+n-1)$ are all distinct and $\{f(m),f(m+1),...,f(m+n-1)\}= \{1,2,\ldots,n\}.$ So $f$ is surjective. Similarly replacing $m$ with $m+1$ we get $\{f(m+1),f(m+2),...,f(m+n)\}= \{1,2,\ldots,n\} \Longrightarrow f(n+m)=f(m)$ Since $f$ has period $n$ we can assume $0\leq j(k) \leq n-1$ for any $1 \leq k \leq n-1$ Step 2: $j(u) \not= j(v)$ for any $1 \leq u<v \leq n-1$ Proof: Assume $\exists 1 \leq u<v \leq n-1$ such that $j(u)=j(v)$. Then \begin{eqnarray} f(m+u)-f(m) &\equiv & f(m+j(u))\equiv f(m+j(v)) \equiv f(m+v)-f(m) \pmod{n+1} \nonumber \\ &\Longrightarrow& f(m+u) \equiv f(m+v) \pmod{n+1} \nonumber \\ &\Longrightarrow& f(m+u)=f(m+v) \nonumber \end{eqnarray} Contradiction since $1\leq v-u \leq n-2.$ Step 3: For any $1\leq k \leq n-1, \exists l_k \in \mathbb{N}$ such that $j^{l_k}(k)=0$, where $j^l(k)$ means $l$ times iteration. Proof: Suppose $\exists 1\leq k \leq n-1$ such that $j^l(k) \not= 0$ for any $l \in \mathbb{N}.$ Then easy calculation yields \[f(m+j^l(k))\equiv f(m+k)-lf(m) \pmod{n+1}\] Since $\{j(k),j^2(k),...,j^n(k)\} \subseteq \{1,2,...,n-1\}$ there exist $1\leq u <v \leq n$ such that $j^u(k)=j^v(k).$ Then $f(m+k)-uf(m) \equiv f(m+j^u(k))\equiv f(m+j^v(k)) \equiv f(m+k)-vf(m) \pmod{n+1}$ Thus $(n+1)|(v-u)f(m)$ for any $m \in \mathbb{Z}$. But this is a contradiction since $1\leq v-u \leq n-1$ and there is $m$ with $f(m)=1.$ Step 4: There exists such $f$ iff $n+1$ is a prime number. Proof: We know that for each $1\leq k \leq n-1$ there exists (minimum) $l_k \in \mathbb{N}$ such that $j^{l_k}(k)=0.$ Now we have $f(m+j^l(k))\equiv f(m+k)-lf(m) \pmod{n+1}$ for $1 \leq l \leq l_k.$ Thus \[f(m)=f(m+j^{l_k}(k))\equiv f(m+k)-l_kf(m)\Longrightarrow (l_k+1)f(m) \equiv f(m+k)\] So $(l_k+1)^nf(m) \equiv (l_k+1)^{n-1}f(m+k) \equiv ..\equiv f(m+nk) \equiv f(m) \pmod{n+1}$ That's \[(l_k+1)^n \equiv 1 \pmod{n+1} \textnormal{for any} 1\leq k \leq n-1---(\star)\] Obviously $1\leq l_k \leq n$ and for $u \not= v, l_u \not=l_v$. (if $l_u=l_v$ then $f(m+u)\equiv(l_u+1)f(m)\equiv (l_v+1)f(m) \equiv f(m+v) \pmod{n+1}$ and so $u=v.$) Moreover, $l_k \not=n$ since for $l_k=n$ we would have $f(m+k)\equiv(l_k+1)f(m) \equiv 0 \pmod {n+1}.$ Contradiction! Thus $\{l_1,l_2,...,l_{n-1}\}=\{1,2,...,n-1\}$ and so $(\star)$ implies $a^n\equiv 1\pmod{n+1}$ for any $2\leq a \leq n \Longrightarrow n+1$ is prime. Step 5: If $n+1$ is prime, then there are $n \cdot \phi(n)$ functions $f$ satisfying the problem. Proof: From Step 4 there is (minimum) $1 \leq l \leq n$ such that $j^l(1)=0.$ Also $f(m+1) \equiv (l+1)f(m) \pmod{n+1}$ for any $m\in \mathbb{Z}.$ So $f(m) \equiv (l+1)^mf(o).$ Since $f$ is surjective $l+1$ must be a primitive root root $g$ modulo $n+1=p$. Thus any function $f$ is of the form $f(m) \equiv g^mf(o) \pmod{n+1}.$ Morever any such function obeys functional equation with $j(k)=ind(g^k-1)$ (since $1\leq k \leq n-1, g^k \not=0$ and so this index exists). Since there are $\phi(p-1)=\phi(n)$ ways to choose $g$ and $n$ ways to choose $f(0) \in \{1,2,\ldots,n\}$, there are $n \cdot \phi(n)$ functions with desired property.

cefer wrote: Step 4: There exists such $f$ iff $n+1$ is a prime number. Nice solution; again using $f(m+j^\ell(k))\equiv f(m+k)-\ell f(m)\pmod{n+1}$ (if $n\nmid k,j(k),\ldots,j^{\ell-1}(k)$) and the fact that $\{f(m+1),\ldots,f(m+n)\}=\{1,\ldots,n\}$, we can do this step slightly differently. Extend the domain of $j(k)$ to all $n\nmid k$. By translation, WLOG $f(1)=1$; now take $n\nmid s$ such that $f(1+s)=n$. Let $0\le r\le n-1$ be the smallest integer such that $n\mid j^r(s)$ (we know $r>0$ already); then $1=f(1)=f(1+j^r(s))\equiv f(1+s)-rf(1) = n-r\pmod{n+1}$, so $r=n-1$. But then \begin{align*} f(m)=f(m+j^{n-1}(s))&\equiv f(m+s)-(n-1)f(m)\pmod{n+1}\\ \implies f(m+s)&\equiv -f(m)\pmod{n+1}, \end{align*}so $f(m+j^\ell(s))\equiv -(\ell+1)f(m)\pmod{n+1}$ for $1\le\ell\le n-1$, whence $n+1$ must be prime (or else we can make $n+1\mid (\ell+1)f(m)$ for some choice of $\ell,m$).

Step 1: $f(k)=f(l)$ iff $k \equiv l (mod n)$ Step 2: $ j(k) \equiv j(l) (mod n)$ iff $k=l$ Step 3: prove $n+1$ is prime. we have that : {$j(1),j(2),...,j(n-1)$}= {$1,2,...n$}\{x}(*) Note that: $\sum _{k=1}^{n} f(u+k)=nf(u)+\sum_{k=1}^{n-1} f(u+j(k)) (mod n+1)$ then $nf(u)=f(u+x) (mod n+1)$ Let $ f(u)=k$ we have {$1,2,...,n$}={$k.n^{i}$ } (**) with $i=0,1,2,...,n-1$ then $\phi (n+1)=n$ then $n+1$ is prime. Step 4: with (*) we have $\phi n$ number k, and n number $x$ then have $n.\phi n$ function we are done

cefer wrote: Step 5: If $n+1$ is prime, then there are $n \cdot \phi(n)$ functions $f$ satisfying the problem. Proof: From Step 4 there is (minimum) $1 \leq l \leq n$ such that $j^l(1)=0.$ Also $f(m+1) \equiv (l+1)f(m) \pmod{n+1}$ for any $m\in \mathbb{Z}.$ So $f(m) \equiv (l+1)^mf(o).$ Since $f$ is surjective $l+1$ must be a primitive root root $g$ modulo $n+1=p$. Thus any function $f$ is of the form $f(m) \equiv g^mf(o) \pmod{n+1}.$ Morever any such function obeys functional equation with $j(k)=ind(g^k-1)$ (since $1\leq k \leq n-1, g^k \not=0$ and so this index exists). Since there are $\phi(p-1)=\phi(n)$ ways to choose $g$ and $n$ ways to choose $f(0) \in \{1,2,\ldots,n\}$, there are $n \cdot \phi(n)$ functions with desired property. How did you learn about primitive roots and indexes and all the theorems about them? By the way, wonderful solution!

Here is a solution that doesn't involve $j^k(l)$ The answer is $n\varphi(n)$ if $n+1$ is a prime, and $0$ otherwise. Lemma $\{ f(1),\cdots,f(n)\}=\{1,\cdots,n\}$ and $f(i)=f(i+n)$ To show this lemma, we will just show $\{ f(i+1),\cdots,f(i+n)\}=\{1,\cdots,n\}$ Assume $f(i+x)=f(i+y)$ where $x<y$. Then $P(i+x,y-x)$ gives a contradiction to the range of $f$. Note if $f(x)$ works, then $cf(x) (\bmod\; n+1)$ also works with the same sequence of $j$. Hence we may assume $f(0)=1$. We then only need to multiply the answer by $n$. Suppose $f(x)=2$. Then $P(0,x)$ yields $j(x)=0$, and $f(m+x)\equiv 2f(m) (\bmod\; n+1)$ for all $0\le m<n$. This motivates a root of unity/generator solution. Suppose $f(a_i)=i$ for $i\ge 2$. Then $P(0,a_i)$ yields $f(j(a_i))=i-1,$ so $j(a_i)=a_{i-1}$. This means we can use what we already know to fill in more stuff. For example, $f(ca_2)\equiv 2^c(\bmod\; n+1)$. Claim: $f(x+y)\equiv f(x)f(y)(\bmod\; n+1)$ Proof. I will show $f(a_i+a_j)\equiv f(a_i)f(a_j)(\bmod\; n+1)$ for all $i,j$. Fix $i$ and induct on $j$. The base case, $j=1$, has $f(a_i)\equiv f(a_i+a_1)\equiv f(a_i)f(a_1)(\bmod\; n+1)$ because $f(a_1)\equiv 1(\bmod\; n+1)$ and $a_1=0$ as $f(0)=1$. Inductive Step: Assume $f(a_x+a_{j-1})\equiv f(a_x)(j-1)(\bmod\; n+1)$, then $$f(a_x+a_j)\equiv f(a_x)+f(a_x+j(a_j))=f(a_x)+f(a_x+a_{j-1})\equiv f(a_x)(1+j-1)\equiv f(a_x)j\equiv f(a_x)f(a_j)(\bmod\; n+1)$$ Therefore, $f(a_i+a_j)\equiv f(a_i)f(a_j)(\bmod\; n+1)$, and since $f$ is a bijection and $a=f^{-1}$, $a$ is also a bijection, so $f(x+y)\equiv f(x)f(y)(\bmod\; n+1)$ is an identity. If $n+1$ is prime, this forces $f(1)$ to be a generator. They all work; here $f(i)=g^i$. $f(m+k)-f(m)\equiv g^m(g^k-1)\equiv g^{m+j(k)}$, so we just need $g^{j(k)}\equiv g^k-1(\bmod\; n+1)$. Now we've shown these are the only functions. So there are only $n\varphi(n)$ such functions. If $n+1$ is composite I claim there is no such $f$. Since for all $x,y$, $f(x+y)=f(x)f(y)$, so $f(x)\equiv f(1)^x(\bmod\; n+1)$. We have two cases: if $\gcd(f(1),n+1)>1$, then $1=f(0)\equiv f(n)\equiv f(1)^n(\bmod\; n+1)$ which is false as $\gcd(f(1)^n, n+1) > 1$. If $\gcd(f(1),n+1)=1$, then $f(x)\equiv f(1)^x(\bmod\; n+1)$, so $\gcd(f(x),n+1)=1$ for all $x$. Let $p$ be a prime divisor of $n+1$, then there doesn't exist $f(x)=p$, false.