How would you go about the following proof?
Let $q > 1$ be an odd positive integer. Show that $q$ is prime if and only if for any set of $\frac{(q+1)}{2}$ distinct positive integers, there exist two integers $x$ and $y$ in the set such that $\frac{(x+y)}{\gcd(x, y)} ≥ q$.
I tried looking at a base case of $q=3$ at first, and then used induction but I'm not sure what to induct upon. Like I can create more primes in the form $pq+1$, but I'm just not sure what to do beyond that point.
This problem is harder and more interesting than it has gotten credit for. EDIT: We first establish "only if" direction. And then below, we establish the "if" direction:
The "only if" direction. Here we establish THM 1 stated next.
THM 1. Let $q$ be a prime integer and let $X$ be a set of $\frac{q+1}{2}$ positive integers. Then there is at least one pair $x,y \in X$ such that $\frac{x+y}{\gcd(x,y)} \ge q$.
Proof: Suppose this is not true. Then the following must hold:
Lemma 2. Let $x,y \in X$ with $x \pmod q = -(y \pmod q) \not = 0$. Then the inequality $\frac{x+y}{\gcd(x,y)} \ge q$ holds.
Proof of Lemma 2: Note that $\gcd(x,y)$ must divide $x+y$. However, $x+y=aq$ for some positive integer $a$, and as $q$ is prime and neither $x,y$ is divisible by $q$, it follows that $\gcd(x+y)$ must divide $a$ and thus the inequality $\gcd(x+y) \le a $ holds. The result follows from noting this inequality $\gcd(x+y) \le a$, together with $x+y=aq$. $\surd$
Lemma 3. Suppose there exists an $x,y \in X$ with $x \pmod q = y \pmod q \not = 0$. Then the inequality $\frac{x+y}{\gcd(x,y)} \ge q$ holds.
Proof of Lemma 3: Let us write $x' = \frac{x}{\gcd(x,y)}$ and $y' = \frac{y}{\gcd(x,y)}$. Then the equation $\frac{x+y}{\gcd(x,y)}=x'+y'$ holds. So to prove Lemma 3, it suffices to show that $x'+y'$ is at least $q$. However, $x'$ and $y'$ are distinct positive integers with $x' \pmod q = y' \pmod q' \not = 0$, so at least one of $x',y'$ must be at least $q$. As both $x',y'$ are positive, it follows that $x'+y'$ is indeed greater than $q$, which as observed earlier, suffices to show Lemma 3. $\surd$
Lemma 4. Let $x,y \in X$ such that exactly one of $x,y$ is a multiple of $q$. Then the inequality $\frac{x+y}{\gcd(x,y)} \ge q$ holds.
Proof of Lemma 4: Let $x$ be the multiple of $q$. Write $x=bq$ for some integer $b$; as $x$ is positive it follows that $b$ must be positive as well. As $q$ is prime and does not divide $y$ it follows that $\gcd(x,y)$ must divide $b$. Thus the inequality $\gcd(x,y) \le b$ must hold. However, the inequality $x+y \ge x = bq$ must also hold, and so from this Lemma 4 follows. $\surd$
REMAINDER OF THE PROOF OF THM 1: First, let us assume WLOG that there is no integer $a$ that divides every element in $X$. Then $q$ does not divide every integer in $X$. By Lemma 4 then, every element $x \in X$ must satisfy $x \pmod q \in \{1,2,\ldots, q-1\}$, lest there is a pair $x,y \in X$ such that the inequality $\frac{x+y}{\gcd(x+y)} \ge q$ holds. By Lemma 3 then, at least one of the following holds:
There is a pair $x,y \in X$ such that the inequality $\frac{x+y}{\gcd(x+y)} \ge q$ holds, or
The set $X$ must also satisfy the following condition (X): If $x,y$ are in $X$, then $x \pmod q \not = y \pmod q \not = 0$.
However, if $X$ satisfies (X), then as $|X| \ge \frac{q+1}{2}$, it follows that there is a pair $x,y \in X$ such that $x \pmod q=-(y \pmod q) \not = 0$. From this however, Lemma 2 implies that there is a pair $x,y \in X$ such that the inequality $\frac{x+y}{\gcd(x+y)} \ge q$ holds after all; namely, any pair $x,y \in X$ such that $x \pmod q=-(y \pmod q) \not = 0$ will do. And so THM 1 follows. $\checkmark$
The "if" direction. Here let $q$ be an odd integer that is not prime. We explicitly construct a set $X$ of $\frac{q+1}{2}$ positive integers such that for all $x,y\in X$ the strict inequality $\frac{x+y}{\gcd(x,y)}<q$ holds. First, let $p$ be a prime that divides $q$; as $q$ is odd and not prime it follows that $p \ge 3$ and $q=pr$ for some $r \ge 3$. Then consider $$X= A + B,$$ where $$A=\{1,2,3,\ldots,(p-1),p\},$$ and $$B=\Big\{(p+1) + 2i;$$ $$i=0,1,\ldots ,$$ $$\Big(\frac{q+1}{2}-(p+1)\Big)\Big\}.$$
Then one can check the following:
For each $x \in A$ and $y \in B$ the inequality $x+y \le q$ holds, with $x+y = q$ only if both $x$ is the largest element in $A$ and $y$ the largest in $B$.
Letting $x$ be the largest element in $A$ and $y$ the largest in $B$, note that $p$ divides both $x$ and $y$.
The integer $2$ divides each element in $B$, and the sum of every two elements in $B$ is strictly less than $2q$.
Finally, the sum of every two elements in $A$ is strictly less than $q$.
Then from 1--4 conclude that $X$ is indeed as claimed.
To tie this back to the "only if" proof, there is a pair $x,y$ such that $x+y$ is a multiple of $q$ [namely $x$ is the largest element in $A$ and $y$ the largest element in $B$, and $x+y=cq$ where here $c=1$, and there is a prime dividing both $x$ and $y$. Compare w Lemma 2 above.