Let $S$ be the sum of all products $ab$ where $a$ and $b$ are distinct elements of the set $\{1,2,...,46\}$. Prove that $47$ divides $S$.
Problem
Source:
Tags: number theory, divides
23.10.2022 00:37
Notice that this set contains $23$ pairs of $\{x, -x\}$ modulo $47$. Now consider the sum $S$. If a summand $ab$ of $S$ does not have $a + b \equiv 0 \mod 47$, then there is exactly three other summands with $(-a)(b), (-a)(-b), (a)(-b)$ all modulo $47$. So most summands are part of a group of $4$, whose sum is $ab + ab - ab - ab \equiv 0 \mod 47$. So nearly all the summands of $S$ become $0$. The exception is products of the form $(a)(-a) = -a^2$ of which there are exactly $23$. So we need to find $-\sum_{n=1}^{23} n^2 \mod 47$. By sum of squares formula, this becomes $-\frac{(23)(24)(47)}{6} = -4(23)(47)$, but clearly this is divisible by $47$, so it contributes $0$ to the sum. So $S$ itself is divisible by $47$.
23.10.2022 01:49