Prove the given congruency
Source: Balkan MO ShortList 2011 N1
April 6, 2020
Problem Statement
Given an odd number , let
\begin{align*} S =\{ k \mid 1 \le k < n , \gcd(k,n) =1 \} \end{align*}
and let \begin{align*} T = \{ k \mid k \in S , \gcd(k+1,n) =1 \} \end{align*}
For each , let be the remainder left by upon division by . Prove
\begin{align*} \prod _{k \in T} \left( r_k - r_{n-k} \right) \equiv |S| ^{|T|} \pmod{n} \end{align*}