Find 17 positive integers such that no four of them have, pairwise, a common divisor greater than 1, but, likewise, no four of them are, pairwise, relatively prime.

Do so in such a way that the largest of those numbers is as small as possible.

  • 6
    $\begingroup$ Can you clarify what you mean by "no four of them have, pairwise, a common divisor greater than 1, but, likewise, no four of them are, pairwise, relatively prime"? Let $a,b,c,d$, be four of the integers: if a pair $a,b$ do not share a common divisor greater than $1$ then they are automatically coprime. $\endgroup$ – Mark Murray Jul 25 at 16:05
  • 4
    $\begingroup$ And what does "four of them, pairwise" mean? $\endgroup$ – aschepler Jul 25 at 16:50
  • 3
    $\begingroup$ Yeah, if we're only looking at pairwise properties, taking them in sets of four is totally irrelevant. $\endgroup$ – Jaap Scherphuis Jul 25 at 19:11
  • $\begingroup$ Are the integers unique? $\endgroup$ – Weather Vane Jul 25 at 19:12
  • 5
    $\begingroup$ Consider the six numbers 10, 14, 105, 195, 231, and 286. No matter how you choose four of them (15 ways of doing this), you will be able to find a pair among the four which have no common divisor greater than 1, and a pair which does. But I request seventeen such numbers, not six. Why 17? Because due to Ramsey's number r(4,4) being equal to 18, 18 is impossible. $\endgroup$ – Bernardo Recamán Santos Jul 26 at 13:43

The following 12 numbers satisfy the conditions:


Represented as a graph where the numbers are its vertices, two of which are joined by an edge if they have a common divisor greater than 1, the graph can be shown not to have a complete subgraph on four vertices ($K_4$):


nor does its complement:

complement graph

In SageMath Cell Server it can be evaluated.

| improve this answer | |
  • $\begingroup$ May I know how you came up with these numbers? $\endgroup$ – John Brookfields Jul 27 at 3:35
  • $\begingroup$ @JohnBrookfields I found a graph that does not contain an isomorphic subgraph to a complete graph on four vertices and labelled it as Jaap Scherphuis says. $\endgroup$ – Freddy Barrera Jul 27 at 12:43

I must admit that I looked this up, but the largest graph which works turns out to be unique, and is called

the Paley graph of order $17$. If you draw the vertices as a regular 17-gon, the edges connect the vertices that are a distance of 1, 2, 4, or 8 apart.
enter image description here

Now all that remains is to label the vertices appropriately. One easy way to do this is to

associate each of the edges with a unique prime. Label each vertex with the product of the eight primes associated with its eight edges.

Of course the numbers you get are rather large. You can improve this a bit as follows:

Label the triangles with edges 1,8,8 and those with edges 2,2,4 using unique primes. This way you only use 34 primes instead of 68. Label each vertex with the product of the primes associated with the triangles it is a vertex of. Every edge is used in at least one triangle, so two vertices have labels with a common factor iff they share a triangle iff they share an edge.
Each vertex will have a label that is the product of six primes, since it is part of six triangles (as any vertex of the two shapes of triangle).

There may be a way to reduce the numbers further.

| improve this answer | |

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.