Suppose $p$ is an odd prime number. We call the polynomial $f(x)=\sum_{j=0}^n a_jx^j$ with integer coefficients $i$-remainder if $ \sum_{p-1|j,j>0}a_{j}\equiv i\pmod{p}$. Prove that the set $\{f(0),f(1),...,f(p-1)\}$ is a complete residue system modulo $p$ if and only if polynomials $f(x), (f(x))^2,...,(f(x))^{p-2}$ are $0$-remainder and the polynomial $(f(x))^{p-1}$ is $1$-remainder. Proposed by Yahya Motevassel
Problem
Source: Iran TST 2012-Third exam-2nd day-P4
Tags: algebra, polynomial, modular arithmetic, induction, Vieta, calculus, Iran
16.05.2012 20:45
Small typo in the problem: use $ \sum_{p-1|j,j>0}a_{j}\equiv i \pmod{p}$ rather than $ \sum_{p-1|j,j>0}a_{j}\equiv i (\mod p) $ The forward direction of this problem is basically just a Turkey NMO problem from 2000. It suffices to consider $n \le p-1$. First we will show if the set is a complete residue system, the remainder things hold. Define $S_i = \sum_{j=0}^{p-1} j^i$ Now let $k$ be a positive integer such that $1 \le k \le p-2$. Let $f(x)^k = \sum_{i=0}^{p-1} a_ix^i$ under $\mathbb{Z}_p[x]_{x^{p}-x}$ $0 \equiv S_k \equiv 0^k + 1^k + 2^k + ... + (p-1)^k \equiv \sum_{i=0}^{p-1} f(i)^k \equiv \sum_{i=0}^{p-1} S_ia_i$ $\equiv S_{p-1}a_{p-1} \implies a_{p-1} \equiv 0 \pmod{p}$, thus $f(x)^k$ is $0$-remainder. For the case of $k=p-1$ you get $S_{p-1} \equiv S_{p-1}a_{p-1} \pmod{p} \implies a_{p-1} \equiv 1 \pmod{p}$. Hence we are done with the forward direction. Now suppose all of the $f(x)^k$ are $0$-remainder for $1 \le k \le p-2$ and $f(x)^{p-1}$ is $1$-remainder. By mimicking the work above we have $\sum_{i=0}^{p-1} f(i)^k \equiv 0 \pmod{p}$ for each $1 \le k \le p-2$ and $\sum_{i=0}^{p-1} f(i)^{p-1} \equiv p-1 \pmod{p}$. Now remark the peculiar fact that shifting $f$ by a constant does not change the fact it's image is $\mathbb{Z}_p$ or not nor that fact that it's powers are $0$-remainder except for $f(x)^{p-1}$ (prove this by induction on $k$ for $f(x)^k$)! The fact that $\sum_{i=0}^{p-1} f(i)^{p-1} \equiv p-1 \pmod{p}$ tells us $f$ has exactly one root. But then taking $f(x) - c$ we have $f(x)$ has exactly one root at $f(x) \equiv c \pmod{p}$, and hence $f(0),f(1),...,f(p-1)$ form a complete residue system modulo $p$. Sketch of Induction: Base case of $k=1$ is trivial, $\sum_{i=0}^{p-1} (f(i) - c) \equiv \sum_{i=0}^{p-1} f(i) - pc \equiv 0 \pmod{p}$ Now to induct from $k-1$ to $k$, $\sum_{i=0}^{p-1} (f(i)-c)^k \equiv \sum_{j=0}^k \dbinom{k}{j}(-c)^j \sum_{i=0}^{p-1} f(i)^{k-j} \equiv 0 \pmod{p}$ OR $\equiv p-1 \pmod{p}$ if $k=p-1$ EDIT : An $x^{p-1} - 1$ should have been an $x^p - x$.
16.05.2012 21:23
dinoboy wrote: We have $\sum_{i=0}^{p-1} f(i)^k \equiv 0 \pmod{p}$ for each $1 \le k \le p-2$ and $\sum_{i=0}^{p-1} f(i)^{p-1} \equiv p-1 \pmod{p}$. After arriving this point , we can end problem with use Newton's identities , these identities show that $\sigma_k = \sum_{0 \leq i_1 < i_2 < \dots < i_k \leq p-1}^{ } f(i_1)f(i_2) \dots f(i_k)$ for $k=1,2,\dots,p-2 ,p$ is zero $\mod p$ and $\sigma _{p-1} \equiv -1$ . Now according to Vieta relations and above result we have $(x-f(0) )(x-f(1) ) (x-f(2) ) \dots (x-f(p-1) ) \equiv x^p - x$ The derivative of right side is $px^{p-1} -1$ and so has no root , hence left side has no double-root $\implies$ $f(0) , f(1) , \dots,f(p-1)$ are distinct $\mod p$ .
17.05.2012 04:49
dinoboy wrote: Small typo in the problem: use $ \sum_{p-1|j,j>0}a_{j}\equiv i \pmod{p}$ rather than $ \sum_{p-1|j,j>0}a_{j}\equiv i (\mod p) $ Thanks. Edited.
26.06.2013 16:22
dinoboy wrote: $a_{p-1} \equiv 0 \pmod{p}$, thus $f(x)^k$ is $0$-remainder. Could you explain this step? It is clear for $k=1$ but for other $k$ is not.
14.03.2017 20:35
Let $j$ be the primitive root modulo p.We have: $$\sum_{p-1\mid j,j>0} a_j\equiv_p \frac{\sum_{i=0}^{p-2} f(j^i)}{p-1}-f(0)\equiv \frac{\sum_{i=0}^{p-1} f(i)}{p-1}$$Now if $\{f(0),f(1),...,f(p-1)\}$ is a complete residue system than from the well-known $\sum_{i=1}^{p-1} i^k\equiv 0\text{if k is not p-1 and p-1 otherwise}$ the first part follows.Clearly one of them is zero from the last condition,throw this number out.As for the others $a_i=\sum_{k=1}^{p-1}x_k^i$ than we have: $$a_{p-1}=+\sigma_1a_{p-2}-\sigma_2a_{p-3}+...+\sigma_{p-1}$$Varying $p$ in the last recursion all $\sigma_i$ are zero except for $\sigma_n$ which is minus one.Taking the spanning poly of $x_i$ we get the desired.