Maths Olympiad Prep

Library / /444 of 520

Number theory Difficulty 6.9 National olympiad Prove it

26. Let pp be an odd prime, and let Tp(r)T_{p}^{*}(r) denote the number of solutions to the congruence equation
x12++xr20(modp),1x1cx_{1}^{2}+\cdots+x_{r}^{2} \equiv 0(\bmod p), \quad 1 \leqslant x_{1} \leq c
where c=(p1)/2c = (p-1)/2. When r>5r > 5, we have
(3!)pTp(3)=l=1px1=1cx2=1cx3=1ce2πil(x12+x22+x32)/p3l=1px1=1cx2=1ce2πil(x12+2x22)/p+2l=1px1=1ce2πil(3x12)/p,\begin{aligned} (3!) p T_{p}^{*}(3)= & \sum_{l=1}^{p} \sum_{x_{1}=1}^{c} \sum_{x_{2}=1}^{c} \sum_{x_{3}=1}^{c} \mathrm{e}^{2 \pi i l\left(x_{1}^{2}+x_{2}^{2}+x_{3}^{2}\right) / p} \\ & -3 \sum_{l=1}^{p} \sum_{x_{1}=1}^{c} \sum_{x_{2}=1}^{c} \mathrm{e}^{2 \pi i l\left(x_{1}^{2}+2 x_{2}^{2}\right) / p}+2 \sum_{l=1}^{p} \sum_{x_{1}=1}^{c} \mathrm{e}^{2 \pi i l\left(3 x_{1}^{2}\right) / p}, \end{aligned}
This formula also holds for p=3,5p=3,5.
(iii) Prove that T3(4)=T5(4)=Ti(4)=0T_{3}^{*}(4)=T_{5}^{*}(4)=T_{i}^{*}(4)=0. When p>7p>7, we have
 (4!) pTp(4)=l=1px1=1cx4=1ce2πil(x12++x42)/p6l=1px1=1cx2=1cx3=1ce2πil(x12+x22+2x32)/p+3l=1px1=1cx2=1ce2πil(2x12+2x22)/p+8l=1px1=1cx2=1ce2πil(x12+3x22)/p\begin{array}{l} \text { (4!) } p T_{p}^{*}(4)=\sum_{l=1}^{p} \sum_{x_{1}=1}^{c} \cdots \sum_{x_{4}=1}^{c} \mathrm{e}^{2 \pi i l\left(x_{1}^{2}+\cdots+x_{4}^{2}\right) / p} \\ \quad-6 \sum_{l=1}^{p} \sum_{x_{1}=1}^{c} \sum_{x_{2}=1}^{c} \sum_{x_{3}=1}^{c} \mathrm{e}^{2 \pi i l\left(x_{1}^{2}+x_{2}^{2}+2 x_{3}^{2}\right) / p} \\ \quad+3 \sum_{l=1}^{p} \sum_{x_{1}=1}^{c} \sum_{x_{2}=1}^{c} \mathrm{e}^{2 \pi i l\left(2 x_{1}^{2}+2 x_{2}^{2}\right) / p} \\ \quad+8 \sum_{l=1}^{p} \sum_{x_{1}=1}^{c} \sum_{x_{2}=1}^{c} \mathrm{e}^{2 \pi i l\left(x_{1}^{2}+3 x_{2}^{2}\right) / p} \end{array}
This formula also holds for p=3,5,7p=3,5,7.
(iv) Using the method of Example 4 in §4 and equation (63), find the expressions for Tp(3)T_{p}^{*}(3) and Tp(4)T_{p}^{*}(4).

Solution

26. The number of solutions to the congruence equation f(x1,,xr)0(modp),1xjaj,1jrf\left(x_{1}, \cdots, x_{r}\right) \equiv 0(\bmod p), 1 \leqslant x_{j} \leqslant a_{j}, 1 \leqslant j \leqslant r is
p1x1=1s1xr=1arl=1pe2xiif(x1,,xr)/p.p^{-1} \sum_{x_{1}=1}^{s_{1}} \cdots \sum_{x_{r}=1}^{a_{r}} \sum_{l=1}^{p} \mathrm{e}^{2 x_{i} i f\left(x_{1}, \cdots, x_{r}\right) / p} .

From this, using the principle of inclusion-exclusion, we can derive the formulas in (ii) and (iii). The specific results in (i), (ii), and (iii) are easy to prove directly; \square
 (iv) Tp(3)=(48)1(p1)(p8(1)(p1)/23(1+2(2p)))Tp(4)=(327)1(p1)(p214p+(71+(1)(p1)/230+24(1)(p1)/2(2p)+32(1)(p1)/2(3p)))\text { (iv) } \begin{aligned} T_{p}^{*}(3)= & (48)^{-1}(p-1)\left(p-8-(-1)^{(p-1) / 2} 3\left(1+2\left(\frac{2}{p}\right)\right)\right) \\ T_{p}^{*}(4)= & \left(3 \cdot 2^{7}\right)^{-1}(p-1)\left(p^{2}-14 p+\left(71+(-1)^{(p-1) / 2} 30\right.\right. \\ & \left.\left.+24(-1)^{(p-1) / 2}\left(\frac{2}{p}\right)+32(-1)^{(p-1) / 2}\left(\frac{3}{p}\right)\right)\right) \end{aligned}

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.