Maths Olympiad Prep

Library / /485 of 520

Number theory Difficulty 7.2 National olympiad, round 2 Prove it

17. Let pp be an odd prime, and f(x1,x2,,xn)f\left(x_{1}, x_{2}, \cdots, x_{n}\right) be an nn-variable integer coefficient polynomial of degree less than nn. Prove: The number of integer solutions (x1,x2,,xn)\left(x_{1}, x_{2}, \cdots, x_{n}\right) satisfying the following conditions
(1) 0xip1,i=1,2,,n0 \leqslant x_{i} \leqslant p-1, i=1,2, \cdots, n;
(2) f(x1,x2,,xn)0(modp)f\left(x_{1}, x_{2}, \cdots, x_{n}\right) \equiv 0(\bmod p)

is a multiple of pp.

Solution

17. Let S={(x1,x2,,xn)0xip1,i=1,2,,n}S=\left\{\left(x_{1}, x_{2}, \cdots, x_{n}\right) \mid 0 \leqslant x_{i} \leqslant p-1, i=1,2, \cdots, n\right\}, then S=|S|= pnp^{n}. Consider the following sum:
T=(y1,y2,,yn)Sf(y1,y2,,yn)p1T=\sum_{\left(y_{1}, y_{2}, \cdots, y_{n}\right) \in S} f\left(y_{1}, y_{2}, \cdots, y_{n}\right)^{p-1}

Notice that, the degree of f(x1,x2,,xn)f\left(x_{1}, x_{2}, \cdots, x_{n}\right) is less than nn, hence the degree of each term in the expansion of f(x1,x2,,xn)p1f\left(x_{1}, x_{2}, \cdots, x_{n}\right)^{p-1} is less than (p1)n(p-1) n. Thus, when each term in TT is expanded and like terms are combined, the term Ay1q1y2q2ynqn,αiNA y_{1}^{q_{1}} \cdot y_{2}^{q_{2}} \cdot \cdots \cdot y_{n}^{q_{n}}, \alpha_{i} \in \mathbf{N} satisfies:
α1+α2++αn<(p1)n\alpha_{1}+\alpha_{2}+\cdots+\alpha_{n}<(p-1) n

Therefore, for this term, there exists an ii such that αip2\alpha_{i} \leqslant p-2. Fixing y1,y2,,yi1,yi+1,,yny_{1}, y_{2}, \cdots, y_{i-1}, y_{i+1}, \cdots, y_{n} and letting yiy_{i} vary from 0 to p1p-1, using the conclusion from Example 1 in Section 3.2, we have:
yi=0p1Ay1q1y2q2ynqn0(modp)\sum_{y_{i}=0}^{p-1} A y_{1}^{q_{1}} \cdot y_{2}^{q_{2}} \cdots \cdots y_{n}^{q_{n}} \equiv 0(\bmod p)

Thus, (y1,y2,,yn)SAy1q1y2q2ynqn0(modp)\sum_{\left(y_{1}, y_{2}, \cdots, y_{n}\right) \in S} A y_{1}^{q_{1}} \cdot y_{2}^{q_{2}} \cdot \cdots \cdot y_{n}^{q_{n}} \equiv 0(\bmod p), and hence T0(modp)T \equiv 0(\bmod p).
On the other hand, by Fermat's Little Theorem, we know:
f(y1,y2,,yn)p1{1(modp),f(y1,y2,,yn)0(modp),0(modp),f(y1,y2,,yn)0(modp).f\left(y_{1}, y_{2}, \cdots, y_{n}\right)^{p-1} \equiv\left\{\begin{array}{ll} 1(\bmod p), & f\left(y_{1}, y_{2}, \cdots, y_{n}\right) \neq 0(\bmod p), \\ 0(\bmod p), & f\left(y_{1}, y_{2}, \cdots, y_{n}\right) \equiv 0(\bmod p) . \end{array}\right.

Thus, from T0(modp)T \equiv 0(\bmod p), we know that the number of arrays (y1,y2,,yn)\left(y_{1}, y_{2}, \cdots, y_{n}\right) in SS such that f(y1,y2,,yn)(modp)f\left(y_{1}, y_{2}, \cdots, y_{n}\right) \neq \equiv(\bmod p) is a multiple of pp. Combining this with S=pn|S|=p^{n}, we obtain the desired conclusion.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.