Number Theory : $\frac{x + y }{\gcd(x,y)} \geq q$ 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.
 A: 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.
