Let $p \ge 3$ be a prime. For $j = 1,2 ,... ,p - 1$, let $r_j$ be the remainder when the integer $\frac{j^{p-1}-1}{p}$ is divided by $p$. Prove that $$r_1 + 2r_2 + ... + (p - 1)r_{p-1} \equiv \frac{p+1}{2} (\mod p)$$
Problem
Source: 2011 Saudi Arabia BMO TST 4.4 - Balkan MO
Tags: number theory, remainder
FIREDRAGONMATH16
29.12.2021 23:46
By Fermat's Little Theorem, we have $j^{p-1} \equiv 1 \mod p \implies j^{p-1} - 1 \equiv 0 \mod p$.
In addition, we also have
$$\frac{j^{p-1}-1}{p} \equiv r_j \mod p$$
$$j^{p-1} - 1 \equiv pr_j \mod p$$
$$j^{p-1} - 1 \equiv r_j \mod p$$
However, from our first conclusion we can see that $r_j \equiv 0 \mod p$, which collapses the sum, makes $jr_j \equiv 0 \mod p$ and makes the sum $$S \equiv 0 \equiv \frac{p+1}{2} \mod p$$or $$p \equiv -1 \mod p$$
which is a contradiction to the problem. Hence our original statement is not true?
parmenides51
29.12.2021 23:56
Official solution is available, there is a chance that they have a typo in the result and it is $\frac{-p+1}{2}$ instead of $\frac{ p+1}{2}$
$jr_j+ (p - j)r_{p-j}+1 \equiv 0 \, (\mod p)$ for $j=1,2,..., p-1$
FIREDRAGONMATH16
01.01.2022 03:53
Oh wait a second, I think I may have gotten it. Thank you @parmenides51 for the major claim, though I discovered most of it on my own by trial and error.
Crucial Claim. We have $jr_j + (p-j)r_{p-j} \equiv -1 \mod p$ for all $1 \le j \le p-1$.
Proof: We may write $r_j \equiv \frac{j^{p-1} - 1}{p} \mod p$ and $r_{p-j} \equiv \frac{(p-j)^{p-1} - 1}{p} \mod p$. Multiplying by $j$ and $p-j$ respectively gives $$jr_j \equiv \frac{j^{p}-j}{p} \mod p$$and $$(p-j)r_{p-j} \equiv \frac{(p-j)(p-j)^{p-1} - (p-j)}{p} = \frac{(p-j)^{p} + j - p}{p} \mod p$$. Adding these two congruences together will yield $$jr_j + (p-j)r_{p-j} \equiv \frac{j^{p}-j + (p-j)^p + j - p}{p} \mod p$$
We must further note that by the Binomial Theorem, $$(p-j)^p = p^p + \binom{p}{1}p^{p-1}(-j)^1 \binom{p}{2}p^{p-2}(-j)^2 + \cdots + \binom{p}{p-1}p^{1}(-j)^{p-1} + (-j)^{p}$$
This is important because we see that the first $p-1$ terms are divisible by $p$. Also, $(-j)^{p} = j^{p}$ since $p$ is a prime and odd. Hence because $j<p$, we can say that $(p-j)^p \equiv -j^{p} \mod p$.
Our modulus will cancel out:
$$jr_j + (p-j)r_{p-j} \equiv \frac{j^{p}-j + (p-j)^p + j - p}{p} \mod p$$$$\equiv \frac{j^{p}-j-j^{p}+j-p}{p} \mod p$$$$\equiv \frac{-p}{p} = \boxed{-1 \mod p}$$Our crucial claim is therefore true.
Continuing, we must see that if we sum over $1 \le j \le p$, we will obtain: $$\sum_{j=1}^{p-1} jp_j + (p-j)r_{p-j} = 2(r_1+2r_2+\cdots + (p-1)r_{p-j}).$$Since we are iterating over this range, there are $p-1$ sums that will contribute a $-1$ when we take this sum modulus $p$. Therefore, we have our desired expression,
$$2(r_1+2r_2+\cdots + (p-1)r_{p-j}) \equiv p-1 \mod p$$
$$\implies r_1+2r_2+\cdots + (p-1)r_{p-j} \equiv \frac{p-1}{2} \equiv \frac{p+1}{2} \mod p$$
Note that division by $2$ above is legal because of the fact that $p$ is a prime greater than or equal to $3$, which implies that $p$ is odd and relatively prime to $2$.
Remarks. I really liked solving this problem! Although this is a number theory olympiad problem and that my number theory is not very strong, it still taught me a lot about how collapsing a sum using symmetry can help a lot. Also, the binomial theorem can help a lot with number theory problems