Prove there exist integers $a,b$ with $b > a+1$ and that for any $a+1\leq k\leq b-1,$ either $\gcd(a,k) > 1$ or $\gcd(b,k) > 1$.

Source: Problem 10 from this problem set.

I doubt this can be solved using brute force search over small pairs. But it could be useful to try some small values or make some general observations. To start with, $\gcd(a,a+1) = 1$ so $\gcd(a+1,b) > 1$. Similarly, $\gcd(a,b-1) > 1$. If $a$ is even, then we only need to consider odd values of $k$ between $a+1$ and $b-1$. It is not hard to see that there are arbitrarily long sequences of consecutive composite integers. For instance, to get a sequence of $n$ composite integers for a positive integer n, take $(2n)! + 2,\cdots ,(2n)! + n.$ The key to this problem seems to be that a lot of numbers greater than $a$ are not coprime to $a$ or $b$. First assume $b-a-1$ should have two distinct prime factors. Let $1\leq i\leq b-a-1$ and consider the number $a+i = b-(b-a-i)$. Then $\gcd(a,a+i) = \gcd(a,i)$. If $a=1,$ then for $2\leq k\leq b-1, \gcd(b,k) > 1,$ which is impossible as $\gcd(b,b-1)=1$. So $a>1$. If $a=2, $ for $3\leq k\leq b-2,\gcd(b,k) > 1$ and $b-1$ is even, so $b$ is odd. But then $b-2$ is coprime to $b$ and $a$, giving a contradiction. So $a > 2$. More generally, $a$ cannot be a power of $2$ by similar reasoning to the case where $a=2$. It seems natural to guess a value of a with a lot of factors like $a=24$ or $a=30$. I ran a computer program and I got the pair $(a,b) = (2184,2200)$ after checking only those values of $a$ and $b$ that were at most $3000$.


1 Answer 1


A strategy to find such a pair is as below:

First let's assume $b=a+k+1$ where $k$ is a positive integer. Then observe that $(a,a+1)=(a+k, a+k+1)=1$; hence we must have $(a,a+k)=d_1\gt1$ and $(a+1, a+k+1)=d_2\gt1$. It is obvious that $d_1|k$ and $d_2|k$. If $(d_1,d_2)=d_3$ then $d_3|a$ and $d_3|a+1$. Therefore $d_3$ must be $1$, which means $k$ has at least two distinct prime factors. So, let's suppose $k=15.$

If $a$ is even, then:

$$(a, a+i)\gt 1 \ where\ i=2,4,6,8,10,12,14. $$

If $3|a$ then: $$(a, a+i)\gt 1 \ where \ i=3,9,15.$$

If $5|a+1$ (or equivalently $5|a+16$) then: $$(a+i, a+16)\ge5 \ where \ i=1,6,11.$$

Now, $i=5,7,13$ are just left.

Note that $(a, a+5)=1$ because we supposed $5|a+1$ earlier. Thus we must have $(a+5,a+16)\gt 1$. As a result it is enough to assume $11|a+16$.

To have $(a,a+7)\gt 1$ and $(a,a+13)\gt 1$, we just need to assume $7 \times 13|a$. All in all, we get:

$$2 \times 3 \times 7 \times 13 |a \\ 5 \times 11|a+16.$$

The pair you found, indeed satisfies the condition above.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .