# prove there are $b > a+1$ so that for $a+1\leq k<b, \gcd(a,k) > 1$ or $\gcd(b,k) > 1$

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

• $2184 = 8 \times 3 \times 7 \times 13,~$ while $~2200 = 11 \times 8 \times 25.~$ The combined prime factorizations include each of $\{2,3,5,7,11,13\}.$ So, for example, $2189$ and $2191$ were handled. That's as far as my thinking takes me. Commented Dec 3, 2022 at 3:56
• It's not clear what you are asking. Commented Dec 3, 2022 at 8:59
• Anyway, your example has been noted here before, e.g., math.stackexchange.com/questions/1315344/… and math.stackexchange.com/questions/1720497/… Commented Dec 3, 2022 at 9:02
• And math.stackexchange.com/questions/1699375/… and probably others. Commented Dec 3, 2022 at 9:08

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.