# Determine the number of functions $f: \mathbb{Z}_{p^n} \to \mathbb{Z}_{p^n}$

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.$ How can one 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}$?

-
Computer experimentation seems to indicate that generically there will be $p^n$ of such functions. They are parametrized by free value of $f(1)$. I used the following Mathematica code: <pre>EnumerateFunctions[n_?Positive, p_?PrimeQ] := Block[{f},Solve[(Flatten[ Outer[f[#1]+f[#2]-f[Mod[#1+#2+p #1 #2, p^n]] &, Range[0, p^n - 1], Range[0, p^n-1]]] // Union) == 0, Modulus -> p^n]]</pre> –  Sasha Aug 12 '11 at 14:30
Tiny note @Sasha: here in the comments, you could use the backtick character  instead of the <pre> tag, like so: EnumerateFunctions[n_?Positive, p_?PrimeQ] := Block[{f},Solve[(Flatten[ Outer[f[#1]+f[#2]-f[Mod[#1+#2+p #1 #2, p^n]] &, Range[0, p^n - 1], Range[0, p^n-1]]] // Union) == 0, Modulus -> p^n]]` –  Ｊ. Ｍ. Aug 15 '11 at 4:56

The function $* : (a,b) \mapsto a + b + pab$ is an associative and commutative operation with $0$ as identity element, and since the function $x \mapsto a + (1+pa)x$ is bijective (because $1+pa$ is invertible in $\mathbb{Z}_{p^n}$), it's a group law. Now a simple calculation shows $1$ is of order $p^n$ in this group. This means $(\mathbb{Z}_{p^n}, *)$ is isomorphic to $(\mathbb{Z}_{p^n}, +)$.
So it turns out you're counting group morphisms form $(\mathbb{Z}_{p^n}, *)$ to $(\mathbb{Z}_{p^n}, +)$. This is the same as counting group endomorphisms of $(\mathbb{Z}_{p^n}, +)$ (chose any bijection $\varphi$ such that $\varphi(x+y) = \varphi(x)*\varphi(y)$, then if $f$ satisfies $f(a*b) = f(a) + f(b)$ then $g = f \circ \varphi$ satisfies $g(x+y) = g(x) + g(y)$). There are $p^n$ of those, corresponding to multiplication by a given element of $\mathbb{Z}_{p^n}$.