Maths Olympiad Prep

Library / /22 of 29

Number theory Difficulty 6.6 National olympiad Prove it Silk Road Mathematics Competition

A subset SS of the set M={1,2,,p1}M = \{1, 2, \dots, p-1\}, where pp is a prime number of the kind 12n+1112n + 11 is essential, if the product Πs\Pi_s of all elements of the subset is not less than the product Πs\overline{\Pi}_s of all other elements of the set. The difference Δs=ΠsΠs\Delta_s = \Pi_s - \overline{\Pi}_s is called the deviation of the subset SS. Determine the least possible remainder of division by pp of the deviation of an essential subset, containing p12\frac{p-1}{2} elements.

Solution

Answer: 2.
Let's consider the subset S={(p+1)/2,,p2,p1}S = \{(p+1)/2, \dots, p-2, p-1\}. Then
Πs=(1)p12(p12)!=(p12)!a(modp), \Pi_s = (-1)^{\frac{p-1}{2}} \left(\frac{p-1}{2}\right)! = - \left(\frac{p-1}{2}\right)! \equiv a \pmod{p},
Πs=(p12)!a(modp). \overline{\Pi}_s = \left(\frac{p-1}{2}\right)! \equiv -a \pmod{p}.
By the Wilson's theorem a21(modp)a^2 \equiv 1 \pmod{p}. Hence, two cases are possible:
Case 1. a1(modp)a \equiv 1 \pmod{p}. Then the deviation of the essential subset SS is equal to Δs=2(modp)\Delta_s = 2 \pmod{p}.
Case 2. a1(modp)a \equiv -1 \pmod{p}. Then the deviation of the essential subset TT, where TT is obtained from SS by substituting p+12\frac{p+1}{2} to p12p+12(modp)\frac{p-1}{2} \equiv -\frac{p+1}{2} \pmod{p}, is equal to ΔT=ΠTΠT1(1)2(modp)\Delta_T = \Pi_T - \overline{\Pi}_T \equiv 1 - (-1) \equiv 2 \pmod{p}.
Now we prove that 22 is the least possible remainder.
Note that ΠsΠs=1\Pi_s \cdot \overline{\Pi}_s = -1 by the Wilson's theorem again. Since 1-1 is not a quadratic residue by modulo a prime number of the kind 4k+34k+3, we have certainly ΠsΠs(modp)\Pi_s \neq \overline{\Pi}_s \pmod{p}. In other words, the deviation is not divisible by pp. Suppose to the contrary, let SS be a subset with deviation ΠsΠs=1\Pi_s - \overline{\Pi}_s = 1. Then Πsm+1(modp)\Pi_s \equiv m+1 \pmod{p}, Πsm(modp)\overline{\Pi}_s \equiv m \pmod{p} for some m{2,3,,p3}m \in \{2, 3, \dots, p-3\} and m2+m1(modp)m^2 + m \equiv -1 \pmod{p}. This implies m31(modp)m^3 \equiv 1 \pmod{p} and by the Fermat's (little) theorem p1p-1 is divisible by 33, which is a contradiction.

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.