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.


closed as off-topic by Greg Martin, John Omielan, Cesareo, Song, Kemono Chen Feb 25 at 5:03

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Greg Martin, John Omielan, Cesareo, Song, Kemono Chen
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    $\begingroup$ What are your thoughts? What have you tried? Where are you stuck? You need to provide context for your question. Right now, it just looks like you want somebody to do your homework for you; that's not what this site is for. If you add some appropriate context, we will be happy to help. $\endgroup$ – Greg Martin Feb 24 at 19:40
  • 1
    $\begingroup$ I was trying to find some pairs which would create those $n$ distinct numbers but all my approaches have failed. Now I am stuck and see nothing what could be useful. $\endgroup$ – AlwaysWrongest Feb 24 at 19:45
  • $\begingroup$ How many numbers totally are written on the board? If every number is repeated $n-1$ times at most, then what can you conclude about the number of appearances of the "most common" number? $\endgroup$ – W-t-P Feb 24 at 20:12
  • $\begingroup$ I don't see how this can help me. $\endgroup$ – AlwaysWrongest Feb 24 at 21:02