Maths Olympiad Prep

Library / /455 of 520

Number theory Difficulty 7.0 National olympiad Prove it

Theorem 1 In a reduced residue system modulo pp, there are exactly (p1)/2(p-1) / 2 quadratic residues modulo pp, and (p1)/2(p-1) / 2 quadratic non-residues modulo pp. Moreover, if dd is a quadratic residue modulo pp, then the number of solutions to the congruence equation (5) is 2.

Solution

To prove the evident, we only need to consider the absolute minimal reduced residue system modulo pp:
p12,p12+1,,1,1,,p121,p12-\frac{p-1}{2},-\frac{p-1}{2}+1, \cdots,-1,1, \cdots, \frac{p-1}{2}-1, \frac{p-1}{2}

dd is a quadratic residue modulo pp if and only if
d(p12)2,(p12+1)2,,(1)2,12,,(p121)2 or (p12)2(modp).\begin{aligned} d \equiv & \left(-\frac{p-1}{2}\right)^{2},\left(-\frac{p-1}{2}+1\right)^{2}, \cdots,(-1)^{2}, 1^{2}, \cdots, \\ & \left(\frac{p-1}{2}-1\right)^{2} \text { or }\left(\frac{p-1}{2}\right)^{2}(\bmod p) . \end{aligned}

Since (j)2j2(modp)(-j)^{2} \equiv j^{2}(\bmod p), dd is a quadratic residue modulo pp if and only if
d12,,(p121)2 or (p12)2(modp).d \equiv 1^{2}, \cdots,\left(\frac{p-1}{2}-1\right)^{2} \text { or }\left(\frac{p-1}{2}\right)^{2}(\bmod p) .

When 1i<j(p1)/21 \leqslant i<j \leqslant(p-1) / 2,
i2≢j2(modp),i^{2} \not \equiv j^{2}(\bmod p),

Therefore, equation (7) gives all the quadratic residues modulo pp, totaling (p1)/2(p-1) / 2. Since the reduced residue system modulo pp has p1p-1 numbers, the other (p1)/2(p-1) / 2 must be quadratic non-residues modulo pp, which proves the first half of the conclusion. When dd is a quadratic residue modulo pp, by equations (7) and (8), there must be a unique i,1i(p1)/2i, 1 \leqslant i \leqslant(p-1) / 2, such that xi(modp)x \equiv i(\bmod p) is a solution to (5). Consequently, in the reduced residue system (6), there are exactly x±i(modp)x \equiv \pm i(\bmod p) as solutions to (5), meaning the number of solutions to (5) is 2. Proof completed.

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.