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

This answer completes rtybase's answer, which finished off with

• 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. Also, assume the sequence values are sorted into increasing order, for simpler handling. First, here are $$2$$ lemmas I will use later.

Lemma #$$1$$:

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, with $$j \gt i$$, 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 first divided from all $$a_i$$. Note that 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$$:

For any sub-sequence of $$t \ge 1$$ integers, i.e., $$a_{b_i}$$ for increasing indices $$b_i$$ with $$1 \le i \le t$$, we have $$L = \operatorname{lcm}(a_{b_1},a_{b_2},\ldots,a_{b_t}) \ge ta_{b_1}$$. Consider the strictly decreasing sequence $$\frac{L}{a_{b_i}}$$ for $$1 \le i \le t$$. With each value being a positive integer, the largest (i.e., first) one must be $$\ge t$$. Thus, $$\frac{L}{a_{b_1}} \ge t \;\to\; L \ge ta_{b_1}$$. Note similar proofs for this are given at LCM of list of strictly increasing positive integers, and in the AoPS thread number theory.

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 = \gcd(a_i,a_j)$$ for some distinct $$i$$ and $$j$$, 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 we 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$$ we 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, we have a ratio $$\ge p + 1$$.

Otherwise, for all $$n$$ where $$p \nmid a_n$$, we have

$$\gcd(a_n,a_i)=h_i \;\;\forall\;\; 1 \le i \le f \tag{4}\label{eq4A}$$

Then, with $$r = \operatorname{lcm}(h_1,h_2,\ldots,h_f)$$, we get as shown in lemma #$$2$$ that

$$r \ge f(h_1) \tag{5}\label{eq5A}$$

Also, we 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{6}\label{eq6A}$$

From \eqref{eq5A}, this means

$$a_u \ge mf(h_1) \;\;\to\;\; \frac{a_u}{h_1} \ge mf \tag{7}\label{eq7A}$$

Using \eqref{eq3A}, we get

$$mf = ((p + 1) - f)f = (p + 1)f - f^2 \tag{8}\label{eq8A}$$

If \eqref{eq8A} is $$\ge p$$, then because it's a lower bound in \eqref{eq7A}, it means we're finished. This is because, by using \eqref{eq2A}, with a lower bound of $$p$$ (i.e., for $$f=p$$), we have $$\frac{a_u}{h_1} = p \;\to\; a_u = ph_1 = a_{g_1}$$. However, since $$u \neq g_1$$, this contradicts the requirement the integers are all distinct, so this possibility is not valid. Thus, $$\frac{a_u}{h_1}$$ will have to be at least $$p+1$$ anyway. We can therefore use $$i=g_1$$ and $$j=u$$ because, from \eqref{eq2A} and \eqref{eq4A}, we have $$h_1 = \gcd(a_u, a_{g_1})$$.

For $$2 \le f \le p - 1$$, note that \eqref{eq8A} is always $$\ge p + 1$$. This can easily be shown since, if we let $$w(x) = (p + 1)x - x^2$$, then $$w(x) = w(p + 1 - x)$$, with $$w(2) = w(p - 1) = 2p - 2$$. Also, $$w'(x) = p + 1 - 2x \ge 0 \implies x \le \frac{p + 1}{2}$$. In other words, $$w(x)$$ increases up to $$x = \frac{p + 1}{2}$$ and then decreases symmetrically.

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 exist at least $$2$$ sequence values such that the ratio of the larger value to their $$\gcd$$ is always at least $$p + 1$$.

• @uvdose Once again, thank you for your feedback, and insight. You're correct that $(p+1)f-f^2\ge p$ is always true, including for $p=2$, so there is no need to handle that case separately. Instead, I just account for $f=p$ as one case where the lower bound of $p$ is reached then, but the value can't be $p$ as I explained due to the values needing to be distinct, so it must be at least $p+1$ instead. I've just made this change to my answer, which somewhat simplifies the explanation. I appreciate your help to first correct, and now simplify, my answer. Commented Aug 21, 2023 at 3:30
• You're welcome. I appreciated your solution which I found very clever. Commented Aug 21, 2023 at 8:08
• I posted a related question that you might be interested in : math.stackexchange.com/questions/4756251/… Commented Aug 21, 2023 at 10:43

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 ...
• Your answer appears to be incomplete. Note you could have $p \mid k$ (not to mention that $p \mid a_i$ & $p \mid a_j$ as well, so $p \mid d$). For example, if $a_j = 2p$ and $a_i = p$, then $\gcd(2p,p) = p$, so $\frac{2p}{p} = 2 \lt p + 1$. You need to account for these possibilities as well. Commented Nov 14, 2019 at 22:37
• @JohnOmielan indeed, you're right. I need to sleep ... I will continue that case tomorrow, unless somebody else answers it by then. Commented Nov 14, 2019 at 23:03
• Since it's been just under a whole day, and I wasn't sure when you would finish your answer, I trust you don't mind that I did that instead. I believe what I wrote is robust & complete (please let me know if it's not) but, as you can see, it's somewhat long & convoluted, with this partially due to my trying to ensure I fully explained each part. Commented Nov 15, 2019 at 22:56

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