Let $n \ge 2$ be an integer and let $a_1,a_2,...,a_n$ be $n$ distinct positive integers. For all pairs $(i,j)$ such that $i \ne j$ numbers $gcd(a_i,a_j)$ and $lcm(a_i,a_j)$ are written on the blackboard. Prove that there are at least $n$ distinct numbers on the blackboard.
Everything I have tried to do with this problem has failed. Trying to find just some pairs of $(i,j)$, using induction or using the identity $gcd(a,b)lcm(a,b)=ab$ - none of these have worked for me. So I am stuck and don't know how to look at this problem.