MathDB

N1

Part of 2011 Balkan MO Shortlist

Problems(1)

Prove the given congruency

Source: Balkan MO ShortList 2011 N1

4/6/2020
Given an odd number n>1n >1, 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 k∈Sk \in S, let rkr_k be the remainder left by k∣S∣−1n\frac{k^{|S|}-1}{n} upon division by nn. Prove \begin{align*} \prod _{k \in T} \left( r_k - r_{n-k} \right) \equiv |S| ^{|T|} \pmod{n} \end{align*}