On division by gcd

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$.