A subset of the set , where is a prime number of the kind is essential, if the product of all elements of the subset is not less than the product of all other elements of the set. The difference is called the deviation of the subset . Determine the least possible remainder of division by of the deviation of an essential subset, containing elements.
Solution
Answer: 2.
Let's consider the subset . Then
By the Wilson's theorem . Hence, two cases are possible:
Case 1. . Then the deviation of the essential subset is equal to .
Case 2. . Then the deviation of the essential subset , where is obtained from by substituting to , is equal to .
Now we prove that is the least possible remainder.
Note that by the Wilson's theorem again. Since is not a quadratic residue by modulo a prime number of the kind , we have certainly . In other words, the deviation is not divisible by . Suppose to the contrary, let be a subset with deviation . Then , for some and . This implies and by the Fermat's (little) theorem is divisible by , 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.