Notice $a_i\not\equiv 0\pmod{p}$, so $a_i^{-1}\pmod{p}$ is well-defined for all $i$. Fix now an $r\not\equiv 0\pmod{p}$ and consider $S_1 = \{r/a_i:1\le i\le k\}$ and $S_2=\{a_j:1\le j\le k\}$ modulo $p$. If $r/a_i\equiv r/a_k\pmod{p}$ then $p\mid r(a_i-a_k)a_i^{-1}a_k^{-1}$, forcing $p\mid a_i-a_k$. So, $|S_1|=|S_2|=k=(p+1)/2$. Now suppose $S_1\cap S_2=\varnothing$ (modulo $p$). Then, $p\ge |S_1\cup S_2| = |S_1|+|S_2| = p+1$, a contradiction. So, there exists $i,j$ such that $r/a_i\equiv a_j\pmod{p}$, i.e., $a_ia_j\equiv r$, the end.