ILL 1983 Problem 13

Let $p$ be a prime number and $a_1, a_2, \ldots, a_{(p+1)/2}$ different natural numbers less than or equal to $p.$ Prove that for each natural number $r$ less than or equal to $p$ , there exist two numbers (perhaps equal) $a_i$ and $a_j$ such that $$p \equiv a_i a_j \pmod r.$$