Let $x_{i}(i=1,2,\ldots,1000)$ be integers,and for all postive integers $k\le 672$,such $$2017 \mid\sum_{i=1}^{1000}x^k_{i}$$

show that $$2017 \mid x_{i},\forall i=1,2,\ldots,1000$$

maybe is use Newton's identities to solve it? I remember this is old problem for any prime number $p=2017$ . But I can't solve it


Notations, discussion, restatement:

Let $p$ be the prime $2017$.

Let $N=1000$, $n=672$ to have a simpler notation, e.g. when using indices. We also introduce $m=N-n=328$.

We will work over the finite field $F=\Bbb F_p$ with $p$ elements instead of $\Bbb Z$, by passing once for all times from the given $x_1,x_2,\dots,x_N$ to their images in $F$ via the modulo $p$ map $\Bbb Z\to\Bbb F_p$, and use by a slight abuse of notation the same notations $x_1,x_2,\dots,x_N$ for the images. Let $x$ be the compound tuple / variable $x=(x_1,x_2,\dots,x_N)$.

If i correctly understand the OP, we have $$ p_1(x)=p_2(x)=\dots=p_n(x)=0\ , $$ where $p_k=p_k(X)$ is the $k$.th (symmetric) Newton polynomial in the multiple variable $X$, $$ p_k(X)=\sum_{1\le j\le N}X_j^k\ .$$ Let $e_1,e_2,\dots,e_n$ be the (symmetric) elementary polynomials of degree, respectively, $1,2,\dots,n$. Let us set $e_0=1$. There is a linear relation (linked in the OP) relating $$ke_k\text{ with }e_0p_k,\ e_1p_{k-1},\ \dots,\ e_{k-1}p_1$$ in the polynomial ring. (It is the sum of these products.) Conversely, each symmetric polynomial of degree $k$ (e.g. $p_k$) can be written as a polynomial in the elementary polynomials (of homogenous weighted degree $k$) so the given relations are equivalent to $$e_1(x)=e_2(x)=\dots=e_n(x)=0\ .$$ (The factor $k$ of $ke_k$, considered in $F=\Bbb F_p$, $1\le k\le n<p$, does not vanish.)

This is further equivalent to the relation $$ \prod_{1\le j\le n}(X+x_j) = X^N + \underbrace{e_{n+1}(x)X^{N-n-1}+\dots+e_N(x)}_{P(X)}\ , $$ where $P$ is a polynomial of degree $<N-n=m$.

So we have to show that there is no polynomial of the shape $X^N+P(X)$, $\deg P<N-n=m$, which splits as a product of linear factors over $F=\Bbb F_p$.


To get a feeling about the choice of the special values of $p,N,n$, let us give a counterexample for "similar, slightly changed values". In $F$ we have a split of $X^p-X$ in linear factors. In particular, every factor of $X^{p-1}-1$ splits linearly over $F$. In particular for every $d$ divisor of $p-1$ the polynomial $X^d-1$ splits linearly over $F$. In our case, here are the divisors of $p-1=2016$ between $100$ and $1000$, sage code:

sage: [ d for d in 2016.divisors() if 100 < d < 1000 ]
[112, 126, 144, 168, 224, 252, 288, 336, 504, 672]

So $d=672$ is in the list. Then $X^{1000-672}\;\Big(X^{672}-1\Big)$ splits linearly in $F$. This is a counterexample for the case with the last Newton polynomial equation removed, i.e. the case with $671$ taken instead of $n=672$. There is a thin air difference between the counterexample values and the OP values, but a major one, and this should show up in the argumentation. So let us go on.

How many multiple (i.e. double, triple, a.s.o.) roots can be there for the (sparse, "sedimentary") polynomial $$ G = X^N+P(X)$$ as above?


Any multiple root of $G$ survives as root of the derivative, which is $NX^{N-1}+P'(X)$, so it is the root of the polynomial $NP-XP'$ of degree $<(N-n)$, i.e. of degree $\le (N-n-1)$. We assume now $P\ne 0$. (And search for a contradiction in the sequel. The case $P=0$ corresponds exactly to the case when all components of $x$ are zero, this is what we need to prove.)

Then the leading coefficient of $(NP-XP')$ occurs in the same degree as the one for $P$, i.e. it is a non-zero polynomial with degree between $0$ and $(n+1)$. So $X^N+P$ has at least $N-(N-n-1)=(n+1)$ different roots.

We come back to the special values. So far we know that the polynomials $$ \begin{aligned} F &= X^{2016}-1\ ,\\ G &= X^{1000}+P \end{aligned} $$ have at least $n=(n+1)-1=672$ common roots. (The zero is not a root for $F$, but it may be for $G$. We subtracted this one case from the $(n+1)$ above.) Consider now the polynomial $$ F-X^{16}\Big(X^{1000}-P\Big)G =X^{16}\, P^2-1\ . $$
It shares also the common mentioned $n=672$ (non-zero) different roots with $F$ and $G$, and it has degree $$\le 16+2\cdot 327=670\ .$$


The assumption $P\ne 0$ is thus absurd. We have proven by contraposition $P=0$, i.e. $x=0$ (i.e. all its $N=1000$ components vanish in $F=\Bbb F_p=\Bbb F_{2017}$).



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.