Let $n\ge 2$ be a positive integer. For any integer $a$, let $P_a(x)$ denote the polynomial $x^n+ax$. Let $p$ be a prime number and define the set $S_a$ as the set of residues mod $p$ that $P_a(x)$ attains. That is, $$S_a=\{b\mid 0\le b\le p-1,\text{ and there is }c\text{ such that }P_a(c)\equiv b \pmod{p}\}.$$Show that the expression $\frac{1}{p-1}\sum\limits_{a=1}^{p-1}|S_a|$ is an integer. Proposed by fattypiggy123
Problem
Source: SMO Open 2022
Tags: number theory, polynomial, modulo, algebra, prime numbers
CANBANKAN
02.07.2022 18:44
Call $(r,a)$ a good pair if there exists a solution to $x^n+ax=r$ in $\mathbb{Z}_p$, where $a\ne 0$. The problem asks us to show the number of such pairs is a multiple of $p-1$. Clearly, $(0,a)$ is a good pair by subbing $x=0$
Consider $(g^ei^n, g^fi^{n-1})$ where $0\le e<gcd(p-1,n), 0\le f<\frac{p-1}{\gcd(n-1,p)}$. I claim this is a bijection of $(\mathbb{Z}_p\backslash \{0\})^2$. It suffices to show injectivity. For two entries to be equal, the $e$'s must be equal, so we can show $p-1/gcd(p-1,n)$ divides the difference in $f$. Note every row is either all good or all bad because $x^n+ax=r \leftrightarrow (kx)^n+ (ak^{n-1})(kx)=k^n(x^n+ax)=rk^n$ so $(rk^n, ak^{n-1})$ good iff $(r,a)$ is good. Since each row has $p-1$ elements I am done.
v_Enhance
04.09.2023 14:39
For each $1 \le a \le p-1$, we clearly have $0 \in S_a$, so focus on nonzero values of $S_a$ (this affects the count by exactly $p-1$). Then \[ |S_1 \setminus \{0\}| + |S_2 \setminus \{0\}| + \dots + |S_{p-1} \setminus \{0\}| \]actually counts the size of the set \[ \mathcal T = \left\{ (y,a) \in {\mathbb F}_p^\times \times {\mathbb F}_p^\times \mid \exists x \in {\mathbb F}_p \text{ such that } y = x^n + ax \right\}. \]The first claim is: Claim: If $(y,a) \in \mathcal T$ then $(\lambda^n y, \lambda^{n-1} a) \in \mathcal T$ for any $\lambda \in {\mathbb F}_p^\times$. Proof. Because \[ y = x^n + ax \implies \lambda^n y = (\lambda x)^n + (\lambda^{n-1} a) \cdot (\lambda x). \]$\blacksquare$ This lets us define a relation on $\mathcal T$ by declaring \[ (y,a) \sim (\lambda^n y, \lambda^{n-1} a) \]across $\lambda \neq 0$, which is easily seen to be an equivalence relation. The following claim then solves the problem: Claim: Each equivalence class has $p-1$ elements in it. Proof. It suffices to show that the ordered pairs $(\lambda^n y, \lambda^{n-1} a)$ are pairwise distinct across the $p-1$ choices of $\lambda \in {\mathbb F}_p^\times$. But this is obvious because if \[ (\lambda_1^n y, \lambda_1^{n-1} a) = (\lambda_2^n y, \lambda_2^{n-1} a) \implies \frac{\lambda_1^n y}{\lambda_1^{n-1} a} = \frac{\lambda_2^n y}{\lambda_2^{n-1} a} \implies \lambda_1 = \lambda_2. \]$\blacksquare$ Remark: By fixing a primitive root $g$ it's possible to describe fairly explicitly the ordered pairs of multipliers $(\lambda^n, \lambda^{n-1})$, although this is unnecessary for the actual problem. Let $\alpha = \gcd(n,p-1)$ and $\beta = \gcd(n-1,p-1)$, so $\gcd(\alpha,\beta)=1$. Write $p-1 = \alpha \beta \gamma$. Then \[ \left\{ (\lambda^n, \lambda^{n-1}) \right\} = \left\{ \left( g^{\alpha k}, g^{\beta \ell} \right) \mid (n-1)\alpha k = n\beta \ell \pmod{p-1} \right\} \]where $k$ is being taken modulo $\beta\gamma$ and $\ell$ is being taken modulo $\alpha\gamma$. Each of the $\beta\gamma$ choices of $k$ (which give every possible value of $\lambda^n$, each exactly once) gives $\alpha$ valid choices of $\ell$. (Or symmetrically, each of the $\alpha\gamma$ choices of $\ell$ gives $\beta$ valid choices of $k$.) So there are a total of $\alpha\beta\gamma = p-1$ possible pairs.