Let $p$ be a prime, $n$ be a positive integer, and let $\mathbb{Z}_{p^n}$ denote the set of congruence classes modulo $p^n.$ Determine the number of functions $f: \mathbb{Z}_{p^n} \to \mathbb{Z}_{p^n}$ satisfying the condition \[ f(a)+f(b) \equiv f(a+b+pab) \pmod{p^n} \] for all $a,b \in \mathbb{Z}_{p^n}.$
Problem
Source: Turkish TST 2011 Problem 9
Tags: function, modular arithmetic, induction, number theory proposed, number theory
06.08.2011 17:26
There're only $p^n$ possible function. $P_n=\{ 1;2;...;p^n\} $ Lemma:$\forall n \in P_n $ there is a number $ a_n \in P_n $ such that :$ n \equiv \frac{(p+1)^{a_n}-1}{p} (mod p^n )$ Proof: $ord_{p^{n+1} }(p+1)=p^n $ hence :$ S=\{\frac{ (p+1)^i-1}{p} \pmod_{p^n}| i \in P_n\} $ contains $p^n$ different values .Done Back to the main problem , According to the above modulo equation , we have: ${{ f( \frac{ (p+1)^x-1}{p}}+f( \frac{ (p+1)^y-1}{p}} \equiv f( \frac{ (p+1)^{x+y}-1}{p}) \pmod_{p^n}$ And this equation leads us to :${f( \frac{ (p+1)^x-1}{p}} \equiv x. f( \frac{ (p+1)^1-1}{p}) \pmod_{p^n}$ ${\Rightarrow f( \frac{ (p+1)^x-1}{p}} )\equiv xf(1) \pmod_{p^n}$ $\Rightarrow f(n) = f( \frac{ (p+1)^{a_n}-1}{p} )=a_nf(1) \pmod_{p^n}$ Ofcourse, this equation sastifies the first modulo equation . And $f(1)$ can have $p^n$ different possible values . $\Rightarrow $ There're only $p^n$ possible function.
09.08.2011 17:52
to Funfun: But in the case p=2, your Lemma doesn't work. So you have to look also the case p=2 specially, altough also for p=2 we have 2^n different functions.
10.09.2011 15:40
Here is the official solution: We shall show that the answer is $p^n.$ Let $a_i=\frac{(1+p)^i-1}{p}$ for $i \geq 0.$ By induction we obtain $f(a_i) \equiv i \cdot f(1) \pmod {p^n}$ for all $i \geq 0.$ If $p>2$ or $p=2$ and $n=1,$ then \[ a_i \equiv a_j \pmod {p^n} \: \Longrightarrow \: (1+p)^{j-i} \equiv 1 \pmod {p^{n+1}} \: \Longrightarrow \: i \equiv j \pmod {p^n}. \] Since $a_i+a_j+pa_ia_j=a_{i+j}$ for all $i,j \geq 0,$ the function defined by $f(a_i) \equiv ic \pmod {p^n}, \: (0 \leq i<p^n),$ satisfies the condition of the question for any choice of $c \in \mathbb{Z}_{p^n}.$ If $p=2$ and $n>1,$ then \[ a_i \equiv a_j \pmod {2^n} \: \Longrightarrow \: 3^{j-i} \equiv 1 \pmod {2^{n+1}} \: \Longrightarrow \: i \equiv j \pmod {2^{n-1}}. \] and $\mathbb{Z}_{p^n} = \{a_i \: : 0 \leq i<2^{n-1}\} \cup \{-a_i-1 \: : 0 \leq i<2^{n-1}\}.$ We also have $2f(-1) \equiv f(-1)+f(-1) \equiv f((-1)+(-1)+2(-1)(-1)) \equiv f(0) \equiv 0 \pmod {2^n}.$ Since $a_i+a_j+2a_ia_j=a_{i+j}, \: a_i+(-a_j-1)+2a_i(-a_j-1)=-a_{i+j}-1,$ and $(-a_i-1)+(-a_j-1)+2(-a_i-1)(-a_j-1)=a_{i+j}$ for all $i,j \geq 0,$ the function defined by $f(a_i) \equiv ic \pmod {2^n}$ and $f(-a_i-1) \equiv ic+d \pmod {2^n}, \: (0\leq i<2^{n-1}),$ satisfies the condition of the question for any choice of $c \in 2\mathbb{Z}_{2^n}$ and $d \in 2^{n-1}\mathbb{Z}_{2^n}$ as $f(a)+f(-1) \equiv f(-a-1) \pmod {2^n}$ for all $a \in \mathbb{Z}_{2^n}.$
22.07.2016 22:36
Here's my Solution. Also i wonder how much points will be given by mr. Kadan to this solution. $\text{Step 1:}$ Without loss of generality we assume that $a^+\rightarrow b^+$. In this solution $\psi$ denotes coefficient of polynomial. Let rewrite the equivalence. $$2\sum_{i\le n} \psi_{i}a^i \equiv \sum_{i\le n}\psi_{i}(2a+a^2p) \pmod{p^n}\Longleftrightarrow \sum_{i\le n}\psi_{i} \left( 2a^{i}-(2a+a^2p)^i\right) \equiv \sum_{i\le n}\psi_{i} (a^i+(a^i-(2a+a^2p)^i)$$Let $a=x$ and $y=2a+a^p$ then; $$\Rightarrow \sum_{1\le n}\psi_i(a^i-(a+a^2p))\left( \sum_{k=0}^{i}x^{(i-1)-k}y^{k}\right)\equiv 0 \pmod{p^n }\Longleftrightarrow \sum_{1\le n}\psi_i(a^i\left( \sum_{k=0}^{i}x^{(i-1)-k}y^{k}\right)-(a^2p+a)\left( \sum_{k=0}^{i}x^{(i-1)-k}y^{k}\right) \equiv 0 \pmod{p^n} \Rightarrow \sum_{i\le n}(\psi_i a^i\left( \sum_{k=0}^{i}x^{(i-1)-k}y^{k}\right)-\psi_i(a+a^2p)\left( \sum_{k=0}^{i}x^{(i-1)-k}y^{k}\right)$$Thus $$\Rightarrow \sum_{i\le n}\left(\sum_{k=0}^{i}\psi_{i}a^{i}(x^{(i-1)-k}y^{k}-\sum_{k=0}^{i}\psi_{i}(a+a^p)(x^{(i-1)-k}y^{k}\right)=\sum_{i \le n}\sum_{k=0}^{i}\psi_{i}a^{i}(x^{(i-1)-k}y^{k})-\sum_ {i \le n}\sum_{k=0}^{i}\psi_{i}(a+a^2p)(x^{(i-1)-k}y^{k}) \Longleftrightarrow \left(\sum_{i\le n }\psi_{i}a^{i}\right)\left(\sum_{k=0}^{i}x^{(i-1)-k}y^{k}\right)-\left( \sum_{i\le n}\psi_{i}(a+a^2p)\right)\left(\sum_{k=0}^{i}x^{(i-1)-k}y^{k}\right)$$ As a result we can find this equation:$$\left( \sum_{k=0}^{i}x^{(i-1)-k}y^{k}\right) \left( \sum_{i\le n}\psi_{i}(a^{i}-(a^2p+a)\right) \equiv 0 \pmod{p^n}$$this equation contains $2$ diffrent case. $\text{Case 1:}$ $$\Rightarrow \sum_{i\le n}\psi_{i}(a(a^{i-1}-ap-1)) \equiv 0 \pmod{p^{n}}$$for $n=1$, its easy to see $-\psi_{1}a^2p\equiv 0 \pmod p$ İf $n=2$ the requirement of definition, this equation must be this form $\psi_{2} \equiv 0 \pmod {p^2}$. We claim $$\sum_{i\le n}\psi_{i}(a(a^{i-1}-ap-1)) \equiv 0 \pmod{p^{n}}$$this equation has a solution if only if when $\psi_{i} \equiv 0 \pmod {p^{i}}$. $\text{Proof:}$ We do some induction. Now, assume that $\psi_{1} \equiv 0\pmod p$ and $\psi_{2} \equiv 0\pmod{p^2}$ equations has solution then if $\psi_{i} \equiv 0 \pmod{p^{i}}$ has a solution, $\psi_{k+1} \equiv 0 \pmod{p^{k+1}}$ equation has a solution too. Let $\mathcal{F}$ is the solution of $\psi_{i} \equiv 0 \pmod{p^{i}}$ equation. For this equation has a solution $\psi_{k+1}^{\mathcal{F}} \equiv 0 \pmod{p^{k+1}}$, this conditions must be correct: $p|0$ and $p^{n+1}|\psi_{k}(\mathcal{F})$. We can see this $2$ conditions All correct. $\square$ As a result $i$ can be $p^n$ diffrent types and at least $p^n$ functions satisfishes. $\text{Case 2:}$ $$\left( \sum_{k=0}^{i}x^{(i-1)-k}y^{k}\right) \equiv 0\pmod{p^n} \Rightarrow \sum_{k=0}^{i}a^{i-1-k}(2a+a^2p)^k = \sum_{k=0}^{i}a^{i-1-k}a^{k}(2a+a^2p)^k \Rightarrow \sum_{k=0}^{i}a^{i-1}(2a+a^2p)^k \equiv 0 \pmod{p^n}$$ $$\Rightarrow a^{i-1}\sum_{k=0}^{i}(p^2+2)^k \equiv 0 \pmod{p^n}$$ This contains $2$ cases too. $\text{Case 1/b:}$ if $a^{i-1} \equiv \pmod {p^n}$ then must be $a|p^n$ but this case in the $\text{Case 1}$. $\text{Case 2/b:}$ $$\sum_{k=0}^{i}(p^2+2)^k \equiv \dfrac{(p^2+2)((p^2+2)^i-1)}{p^2+1} \pmod{p^n}$$but this case, when $p>2$ did not satisfishes the following condition for all $a,b$. $\square$ As a result at least $p^n$ functions satisfying the condition. Hope this is true.
27.07.2016 02:52
Is my proof correct? If i have a mistake anywhere please notice that.