$a$ is an integer and $p$ is a prime number and we have $p\ge 17$. Suppose that $S=\{1,2,....,p-1\}$ and $T=\{y|1\le y\le p-1,ord_p(y)<p-1\}$. Prove that there are at least $4(p-3)(p-1)^{p-4}$ functions $f:S\longrightarrow S$ satisfying $\sum_{x\in T} x^{f(x)}\equiv a$ $(mod$ $p)$. proposed by Mahyar Sefidgaran
Problem
Source: Iran 3rd round 2011-number theory exam-p6
Tags: function, number theory proposed, number theory
27.06.2020 04:43
We give an improved bound of $(p-5)(p-3)(p-1)^{p-4}$. Lemma: For any $1\le c \le p-1$ there exist $\ge p-5$ pairs $(u,v)$ with $1\le u,v \le p-1$ such that $u^2 +v^2 = c \pmod p$. Proof: The number of pairs $(u,v)$ is in fact $$\sum_{i=1, i \ne c}^{p-1} (\left(\frac{c-i}{p}\right)+1) (\left(\frac{i}{p}\right)+1) = \sum \left(\frac{(c-i)i}{p}\right) - 2\left(\frac{c}{p}\right) + p-2 = \sum_{i=1,i \ne c}^{p-1} \left(\frac{c/i-1}{p}\right) + p-2 - 2\left(\frac{c}{p}\right) = - \left (\frac{-1}{p}\right) + p-2 - 2\left(\frac{c}{p}\right) \ge p-5.$$$\blacksquare$ Since $p \ge 17$ the number of elements with order $\frac{p-1}{2}$ is $2\phi(\frac{p-1}{2}) \ge 3$. Let $u_1, u_2, u_3$ be $3$ such elements in $T$. Define $f$ arbitrarily for the other $p-4$ elements. We show that for each choice of $f$ there are at least $(p-5)(p-3)$ choices of $f(u_1), f(u_2), f(u_3)$ with this property. First note that there are at most $2$ choices of $f(u_3)$ such that $u_3^{f(u_3)} + \sum_{u \ne u_1, u_2, u_3, u \in T} u^{f(u)} \equiv 0 \pmod p$. Choose $f(u_3)$ such that this does not hold, we have $p-3$ choices of $u_3$. Next, by the lemma above there are $\ge p-5$ solutions to $u^2 + v^2 \equiv c \pmod p$ for each nonzero $c = - \sum_{u \ne u_1, u_2, u \in T} u^{f(u)}$. It's clear that there exists a bijection between the set of $(f(u_1), f(u_2))$ with $u_1^{f(u_1)} + u_2^{f(u_2)} = c$ and $(u,v)$ with $u^2 + v^2 = c$, so there are $\ge p-5$ choices of $(f(u_1), f(u_2))$ that work, as desired.