Let $p\geqslant 5$ be a prime number. Prove that the set $\{1,2,\ldots,p - 1\}$ can be divided into two nonempty subsets so that the sum of all the numbers in one subset and the product of all the numbers in the other subset give the same remainder modulo $p{}$.
Problem
Source: Russian TST 2015, Day 10 P2 (Group NG)
Tags: number theory, prime numbers
23.04.2023 04:51
Btw @above $p = 3$ seems to be failing; what follows is a solution for $p \geq 5$.
28.07.2023 21:13
Cute problem. Here's a different solution which provides an explicit construction Since $\prod_{i=1}^{p-1} i \equiv -1 \pmod{p}$ and $\sum_{i=1}^{p-1} i \equiv 1 \pmod{p}$, it suffices to show that there exists $S \subseteq \{1,\ldots,p-1\}$ such that $$\sum_{i \in S} i \equiv -\frac{1}{\prod_{i \in S} i} \pmod{p}.$$If $i \equiv 1 \pmod{4}$, then take $S=\{a\}$, where $a^2 \equiv -1 \pmod{p}$, and both sides are equivalent to $a$. Otherwise, since $p \geq 5$, there exists some odd prime $q \mid p-1$. Then pick $a \in \mathbb{F}_p$ such that $\mathrm{ord}_p(a)=q$, and let $$S=\left\{a^{\frac{q-1}{2}},a^{\tfrac{q-3}{2}},\ldots,a^1,a^{-1},a^{-3},\ldots,a^{-\frac{q-1}{2}}\right\},$$so then $$\prod_{i \in S} \equiv 1 \pmod{p} \text{ and } \sum_{i \in S}i \equiv -1 \pmod{p} \iff a^{\frac{q-1}{2}}\left(a^{\frac{q-1}{2}}+\cdots+a^{-\frac{q-1}{2}}\right)=a^{q-1}+\cdots+1 \equiv 0 \pmod{p},$$which is certainly true, so we're done. $\blacksquare$