6
$\begingroup$

Can 17 positive integers in arithmetic progression be found such that that no four of them have, pairwise, a common divisor greater than 1, but, likewise, no four of them are, pairwise, relatively prime?

Because R(4,4)=18, 18 such numbers are impossible.

At https://puzzling.stackexchange.com/questions/100391/seventeen-positive-integers/100477#100477 it has been shown that 17 numbers with the required property, but not necessarily in arithmetic progression, can be easily found based on Paley's graph of order 17. The question arises: could those 17 numbers be in arithmetic progression?

$\endgroup$
1
  • 5
    $\begingroup$ Do you have an example for five numbers for R(3,3)? Gerhard "Likes To Start Out Small" Paseman, 2020.07.27. $\endgroup$ Jul 27, 2020 at 16:19

1 Answer 1

5
$\begingroup$

No, there cannot be 17 such numbers in arithmetic progression (and there cannot be 5 such numbers with the corresponding property for triples).

Suppose we have such an arithmetic progression of length $k$, say $x,x+d,\ldots,x+(k-1)d$. I claim that if a prime $p$ divides any two of them then either it divides all of them (which cannot be the case), or else $p<k$.

Indeed, if $p\mid x+id$ and $p\mid x+jd$ for $0\leq i<j<k$ then $p\mid \ell d$ for some $1\leq \ell<k$. If $p\mid d$ then $p\mid x$ and so all members of the AP are divisible by $p$. Therefore $p\mid \ell$ for some $1\leq \ell <k$, and hence $p<k$.

When $k=5$, the only possibilities are $p=2$ or $p=3$. Consider the graph on these 5 numbers. If there is no triangle/anti-triangle in this graph, every vertex has degree exactly two, and in particular must be divisible by either 2 or 3. By the pigeonhole principle at least 3 of the numbers are divisible by one of them, so there are three numbers with a common non-trivial divisor, contradiction.

Similarly, when $k=17$, the only primes are $2,3,5,7,11,13$. If we draw a graph as above, then to avoid a monochromatic 4-clique it must be the Paley graph of order 17, and in particular every vertex has degree at least one. Colour each vertex by the primes out of $2,3,5,7,11,13$ which divide that vertex, so this is a 6-colouring of the vertices (where a vertex may receive multiple colours). Clearly no colour can appear on more than 3 such vertices, and each vertex receives at least one colour.

It is easy to see that 5 of the colours must appear on exactly 3 of the vertices (since $2\times 2+4\times 3<17$), and the remaining colour appears on the remaining 2 vertices and at most one of the other 15 vertices. Choosing one vertex from each of the 4 colour classes of size 3 that don't receive this 6th colour produces 4 vertices that are pairwise jointly divisible by none of the primes $2,3,5,7,11,13$, and hence pairwise have no common divisor.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.