Problem:
Prove that there is a constant c>0 with the following property: If a,b,n are positive integers such that gcd(a+i,b+j)>1 for all i,j∈{0,1,…,n}, then
min{a,b}>cn⋅n2n
Solution:
Let a,b,n be positive integers as in the statement of the problem. Let Pn be the set of prime numbers not exceeding n. We will need the following
There is a positive integer n0 such that for all n≥n0 we have
p∈Pn∑(pn+1)2<32n2
Proof. Expanding and dividing by n2, and observing that ∣Pn∣≤n, it suffices to prove the inequality
p∈Pn∑p21+n2p∈Pn∑p1+n1<32
Since
n2p∈Pn∑p1<n2i=2∑ni1<n2logn
it suffices to prove the existence of a constant r<32 such that ∑p∈Pnp21<r. But
p∈Pn∑p21≤41+91+k=1∑n(2k+1)(2k+3)1
=41+91+k=1∑n21(2k+11−2k+31)=41+91+21(31−2n+31)<41+91+61<31
and we can take r=41+91+61.
From now on we fix such n0, and we prove the statement assuming n≥n0. Note that for any p∈Pn there are at most pn+1 numbers i∈{0,1,…,n−1} such that p∣a+i, and likewise for j∈{0,1,…,n−1} such that p∣b+j. Thus there are at most (pn+1)2 pairs (i,j) such that p∣gcd(a+i,b+j). Using the previous lemma, we deduce that there are less than 32n2 pairs (i,j) with i,j∈{0,1,…,n−1} such that p∣gcd(a+i,b+j) for some p∈Pn.
Let N be the least integer greater than or equal to 3n2. By the above, there are at least N pairs (i,j) with i,j∈{0,1,…,n−1} such that gcd(a+i,b+j) is not divisible by any prime in Pn. Call these pairs (is,js) for s=1,2,…,N. For each pair, choose a prime ps that divides gcd(a+is,b+js) (since, by hypothesis, gcd(a+is,b+js)>1 ); thus ps>n. The map s↦ps is injective, for if ps=ps′, then ps∣is−is′, implying is=is′, and similarly js=js′, hence s=s′.
We conclude that ∏i=0n−1(a+i) is a multiple of ∏s=1Nps. Since the ps are distinct prime numbers greater than n, then,
(a+n)n>i=0∏n−1(a+i)≥s=1∏Nps≥i=1∏N(n+2i−1)
Let X be this last product. Then
X2=i=1∏N[(n+2i−1)(n+2(N+1−i)−1)]>i=1∏N(2Nn)=(2Nn)N
where the inequality holds because
(n+2i−1)(n+2(N+1−i)−1)>n(2(N+1−i)−1)+(2i−1)n=2Nn
Finally
(a+n)n>(2Nn)2N≥(32n3)6n2
Thus,
a≥(32)61⋅n⋅n2n−n
which is larger than cn⋅n2n when n is large enough, for any constant c<(32)61. Similarly, the same inequality holds for b.
This shows that min{a,b}≥cn⋅n2n as long as n is large enough. By shrinking c sufficiently, we can ensure the inequality holds for all n.
One can see that the argument is not sharp, so that the factor n2n can be improved to nrn for some constant r slightly larger than 21. Consequently, for any c>0, the inequality in the problem holds if n is large enough.
This problem and solution was suggested by Titu Andreescu and Gabriel Dospinescu.
The problems on this page are the property of the MAA's American Mathematics Competitions