On division by gcd I am interested in the following problem:

Let $a_1,a_2,...,a_{p+1}$ be a sequence of distinct positive integers where $p$ is prime. Show that we can find two numbers from this sequence such that largest of them divided by their $GCD$ is $\geq p+1$.

Here's what I have tried so far... Suppose that this is not true, then for all $a_i, a_j$, we have $\max\{a_i,a_j\}\leq p\cdot \gcd(a_i, a_j)$. Now, let $\gcd$ be $d$. Then, we have $a_i=b_id, a_j=b_jd$.
I am not able to use the prime condition too! Any help will be highly appreciated.
 A: This answer completes rtybase's answer. As it finished off there,

  
*
  
*if $\color{red}{\gcd(a_i,a_j)=d}>1$ and $p\mid d$ then ...
  

However, note $i$ and $j$ will be used as general indices here instead of the specific ones mentioned in the other answer. First, here are $2$ lemmas I will use later.
Lemma #$1$:
Assume the sequence values are sorted in increasing order, for simpler handling here. Also, note if there's any factor $e \gt 1$ where $e \mid a_i$ for all $1 \le i \le p + 1$, then $e \mid d = \gcd(a_i,a_j)$, so the fraction $\frac{a_j}{d}$ would be the same as if $e$ was divided from both $a_i$ and $a_j$. As such, the maximum fraction value would be the same as if $e$ was divided from all $a_i$. Note related proofs about moving out a common factor among GCD elements are given at Prove that $(ma, mb) = |m|(a, b)\ $ [GCD Distributive Law].
Lemma #$2$:
Note the lcm among any sequence of $t \gt 1$ distinct, positive integers must be at least $t$ times the smallest integer. Consider the lcm among just the smallest integer and each larger integer. The lcm must be a multiple, $\ge 2$, of the smallest integer, with each multiple among the various integers being different as they are distinct. Thus, you have $t - 1$ distinct integer multiples, each $\ge 2$, so the largest such multiple must be at least $t$. Note a similar proof for this is given at LCM of list of strictly increasing positive integers.
Back to extending the previous answer, use lemma #$1$ to divide by any common factor among all the $a_i$ so there's no factor $\gt 1$ in common among all the $a_i$. After doing this, if $p \mid d$, then there are
$$2 \le f \le p \tag{1}\label{eq1A}$$
sequence values which are a multiple of $p$ (note it's not all of them, i.e., $p + 1$, as discussed just above). Consider the indices of these values to be $g_i$, so you get for some integers $h_i$ that
$$a_{g_i} = h_i(p), \; 1 \le i \le f \tag{2}\label{eq2A}$$
Among the remaining
$$m = (p + 1) - f \tag{3}\label{eq3A}$$
sequence values which have no factor of $p$, if for any one of them, say $a_n$, for some $1 \le i \le f$ you have $\gcd(a_{g_i},a_n) = q \lt h_i$, then $\frac{a_{g_i}}{q} \ge 2p \gt p + 1$. If $a_n \gt a_{g_i}$, then $\frac{a_{n}}{q}$ would be even larger. In either case, you have a ratio $\ge p + 1$. Otherwise, if $r$ is the lcm of all $h_i$, then as shown in lemma #$2$, you have
$$r \ge f(h_1) \tag{4}\label{eq4A}$$
Also, you must have $r$ dividing all of those $m$ sequence values with no factor of $p$. As such, the largest of these $m$ values, say $a_u$, has
$$a_u \ge mr \tag{5}\label{eq5A}$$
From \eqref{eq4A}, this means $a_u \ge mf(h_1)$. From \eqref{eq2A}, since $v = \gcd(a_u, a_{g_1}) \le h_1$, this means
$$\frac{a_u}{v} \ge mf \tag{6}\label{eq6A}$$
Using \eqref{eq3A}, you get
$$mf = ((p + 1) - f)f = (p + 1)f - f^2 \tag{7}\label{eq7A}$$
If \eqref{eq7A} is $\ge p + 1$, then \eqref{eq6A} means you're finished. Consider for now that $p \gt 2$. Then \eqref{eq7A} is $\gt p$ for all $2 \le f \le p - 1$. This can easily be shown since if you let $g(x) = (p + 1)x - x^2$, then $g(x) = g(p + 1 - x)$, with $g(2) = g(p - 1) = 2p - 2$. Also, $g'(x) = p + 1 - 2x \ge 0 \implies x \le \frac{p + 1}{2}$. In other words, $g(x)$ increases up to $x = \frac{p + 1}{2}$ and then decreases symmetrically. The one case left to consider is if $f = p$. In that case, you have the largest $a_{g_f}$ is at least the $p$ times the smallest $a_{g_1}$. If it's more than $p$, you can use those $2$ sequence values for the ratio. However, if it's just $p$, then note you have both $p - 1$ and $p$ multiples of $a_{g_1}$, but since $\gcd(p-1,p) = 1$, then \eqref{eq4A} becomes $r \gt p(h_1)$, so the single non-multiple of $p$ sequence value can be used to get it divided by the gcd of $a_{g_1}$ to be more than $p$.
This accounts for all cases except for if $p = 2$. In this case, you have $2$ even values and one odd. To avoid any cases where the ratio is $\ge p + 1 = 3$ requires they each be at the most $2$. The gcd of the odd value, though, with either of the $2$ even values would be an odd value, so the ratio would be an odd value and would need to be only $1$ in both cases. This can only happen if both of the even values were a multiple of this odd value. As such, the smaller even value must be at least $2$ times this odd value and the larger even value must be at least $4$ times it. However, then the larger even value divided by the gcd of itself & the odd value would be at least $4 \ge p + 1 = 3$.
In summary, this handles all the remaining cases not covered by rtbyase's answer to prove the original requested problem always holds, i.e., there exists at least $2$ sequence values such that the ratio of the larger value to their gcd is always at least $p + 1$.
A: Partial answer
From the given conditions and using pigeonhole principle, there will $\exists a_i,a_j\in \{a_1,a_2,...,a_{p+1}\}$ s.t. $a_j\equiv a_i \pmod{p}$ (i.e. $p+1$ remainders all $< p$). Or simply 
$$a_j=k\cdot p +a_i \tag{1}$$
for a $\color{red}{k\geq 1}$ since all the $a_i$'s are distinct. In this configuration we assume $\max\{a_i,a_j\}=a_j$ of course, but this doesn't affect the final result. Now


*

*if $\gcd(a_i,a_j)=1 \Rightarrow \max\{a_i,a_j\}=a_j=\color{red}{k}\cdot p +a_i \leq p$ - contradiction.

*if $\color{red}{\gcd(a_i,a_j)=d}>1$ and $p\nmid d$ then, because $p$ is prime, $\color{red}{d\mid k}$ leading to $$\max\{a_i,a_j\}=a_j=k\cdot p +a_i \leq p\cdot d \iff \\
\color{red}{\frac{k}{d}}\cdot p + \color{red}{\frac{a_i}{d}}\leq p$$
which is another contradiction, given $\frac{k}{d}\geq 1$ and $\frac{a_i}{d}\geq 1$.

*if $\color{red}{\gcd(a_i,a_j)=d}>1$ and $p\mid d$ then ...

A: My attempt (mostly complimentary of rtybase's answer) :
First, consider arithmetic progressions with start element also the distance added. We see immediately, that if we factor out the common factor, we land at $1,\ldots ,p+1$; for which it's trivial (just take first and last elements). 
If we continue, with arithmetic progressions where the start term is a factor of the distance, we get to a sequence with 1 in it and top term is necessarily $\geq p+1$ (for which it is again trivial).  
