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.
$\begingroup$
$\endgroup$
7
asked Jul 25, 2020 at 14:18
-
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 MurrayCommented Jul 25, 2020 at 16:05
-
4$\begingroup$ And what does "four of them, pairwise" mean? $\endgroup$– ascheplerCommented Jul 25, 2020 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 ScherphuisCommented Jul 25, 2020 at 19:11
-
$\begingroup$ Are the integers unique? $\endgroup$– Weather VaneCommented Jul 25, 2020 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 SantosCommented Jul 26, 2020 at 13:43
|
Show 2 more comments
2 Answers
$\begingroup$
$\endgroup$
2
The following 12 numbers satisfy the conditions:
$$203,385,437,713,814,1330,1479,1495,2418,3441,11951,70499$$
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:
In SageMath Cell Server it can be evaluated.
-
$\begingroup$ May I know how you came up with these numbers? $\endgroup$ Commented Jul 27, 2020 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$ Commented Jul 27, 2020 at 12:43
$\begingroup$
$\endgroup$
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.
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.
answered Jul 27, 2020 at 10:03