Problem

Source: VIII International Festival of Young Mathematicians Sozopol 2017, Theme for 10-12 grade

Tags: number theory



Let $n$ be a composite number and $a_1,a_2… a_k\in \mathbb{N}$ are the numbers smaller than $n$ and not coprime with it (in this case $k=n-\phi (n)$). Let $b_1,b_2…b_k$ be a permutation of $a_1,a_2… a_k$ Prove that there exist indexes $i$ and $j$, $i\neq j$ for which $a_i b_i\equiv a_j b_j (mod $ $n)$.