A prime number $p> 3$ is given. Prove that integers less than $p$, it is possible to divide them into two non-empty sets such that the sum of the numbers in the first set will be congruent modulo p to the product of the numbers in the second set.
Problem
Source: Ukraine TST 2015 p4
Tags: Sum, Product, number theory, modulo
02.05.2020 09:08
Let $x = 1$ and $y = 2^{-1} - 1\pmod{p}$. Obviously $x \neq y$ or else $p$ divides $3$. Let $P = {x, y}$ and $S$ contain the other elements. Then the sum of the elements in $S$ is \[ 1 + 2 + \cdots + p-1 - x - y = \frac{p(p-1)}{2} - x - y \pmod{p} . \]On the other hand the product of the elements of $P$ just $xy$. Thus we simply need to check that $p \mid xy + x + y$: \[ xy + x + y = (x+1)(y+1) -1 \equiv 2 \cdot 2^{-1} -1 \equiv 0\pmod{p}. \]Done.
02.05.2020 12:42
HKIS200543 wrote: Let $x = 1$ and $y = 2^{-1} - 1\pmod{p}$. Obviously $x \neq y$ or else $p$ divides $3$. Let $P = {x, y}$ and $S$ contain the other elements. Then the sum of the elements in $S$ is \[ 1 + 2 + \cdots + p - x - y = \frac{p(p+1)}{2} \equiv - x - y \pmod{p} . \]On the other hand the product of the elements of $P$ just $xy$. Thus we simply need to check that $p \mid xy + x + y$: \[ xy + x + y = (x+1)(y+1) -1 \equiv 2 \cdot 2^{-1} -1 \equiv 0\pmod{p}. \]Done. This is a nice work!
17.05.2020 07:58
>> Prove that integers less than $p$ .. Is this correct or it is Prove that integers less than or equal to $p$? In the solution i could see terms used is till "P"
27.06.2020 10:13
My solution is consider two sets $\{ 1, p-2, p-1\}$ and $\{ 2,..., p-3\}$ (here both sets are non-empty).The product of the elements in first set is congruent mod $p$ to the sum of the elements in the second set.
27.05.2023 03:01
No need for $p$ to be prime.