Placing an integer's divisors around a circle

i) Is it true that all divisors greater than 1 of any positive integer can be placed around a circle so that any two which are next to each other are never relatively prime?

ii) For which positive integers n is it possible to place all proper divisors of n (that is, all divisors of n besides n itself) around a circle so that any two which are next to each other are relatively prime?

• What are your thoughts on these questions? Sep 27, 2019 at 1:39
• I believe i) is indeed true and perhaps not too difficult to prove. I suspect there are infinitely many (and diverse) integers whose divisors cannot be placed around a circle with adjacent divisors relatively prime. Perfect powers of primes, for example. Sep 27, 2019 at 1:45
• Right: an easy way to look at it is since $n|n$ and $n$ has to be placed on the circle, unless $n$ is prime, any pair containing $n$ and its divisor is obviously not relatively prime (e.g. the circle for the integer $24$ will contain in some order $2, 3, 4, 6, 8, 12, 24$. While it's possible to choose a pair that are relatively prime, like $(3,8)$, you will still have to pair $24$ with one of its divisors). Given this, the answer to the second question is, well, only prime numbers. Sep 27, 2019 at 1:53
• @AndrewChin You are right! I should have said all divisors except integer itself. If I may I shall amend question. Sep 27, 2019 at 1:58
• Why don't you run some experiments, Bernardo, and report back to us? What happens with divisors of $30$? of $210$? Sep 27, 2019 at 2:20

For (i) the only exception is numbers with exactly two distinct prime factors.

Let $$n$$ be a positive integer greater than $$1$$.

If $$n=pq$$ then it can't be done because in a circle $$p$$ will always be next to $$q$$.

If $$n=p^a$$ then it can be done because in this case the divisors of $$n$$ are all multiples of $$p$$ so just place them in any order around the circle.

Finally if $$n=p_1^{a_1}...p_k^{a_k}$$ (excluding the above cases) then it can be done like this: First place the prime factors $$p_1,...,p_k$$ on the circle in this order, then between $$p_i$$ and $$p_{i+1}$$ put every number in the form $$p_i^jp_{i+1}$$ with $$a_i\ge j\ge1$$ (in increasing order). After that put every multiple of $$p_ip_{i+1}$$ that remains between $$p_i^{a_i}p_{i+1}$$ and $$p_ip_{i+1}$$. (There will be some overlap but starting from numbers between $$p_1^{a_1}p_2$$ and $$p_2$$ you can just not add a number that already exists somewhere else).

Till now why this works? well note that with this method every number between $$p_i$$ and $$p_{i+1}$$ is a multiple of $$p_ip_{i+1}$$ so we're good. But we still have to deal with the $$p_i^j$$'s...Just put them somewhere between $$p_ip_{i+1}$$ and $$p_i^2p_{i+1}$$.

(ii) is a bit harder but I think the answer is the opposite of (i) i.e $$n=pq$$ are the only numbers that work (and they trivially work) furthermore powers of prime obviously don't work.

Let $$n=p_1^{a_1}...p_k^{a_k}$$ (excluding the above cases). If one of the exponents is $$>1$$ then it can't be done. Here's why: The number $$r=p_1...p_k$$ is going to be somewhere on the circle, but any other divisor of $$n$$ shares a common factor with $$r$$ therefore the neighbors of $$r$$ are $$1$$ and $$d$$ with $$(d,r)>1$$ hence it doesn't work.

Therefore we are left with squarefree numbers...I don't how to solve them but a few experiments shows they probably don't work and indeed I managed to solve the case $$n=pqr$$ like this: consider the number $$pq$$ it's only possible neighbors are $$1$$ and $$r$$, but $$r$$ is either next to $$p$$ or $$q$$ wlog assume it's $$p$$. Now $$p$$ is either next to $$q$$ or $$qr$$. If it's the latter then we are left with $$pr$$ and $$q$$ and they don't work. If it's $$q$$ then the next one is $$pr$$ and after that is $$qr$$ and again they don't work. Unfortunately this method is hard to generalize because the more prime factors $$n$$ has the more cases you have to check.

ii)

Let $$n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$$ where $$p_1\lt p_2\lt \cdots\lt p_k$$ are prime numbers, and $$a_1,a_2,\cdots, a_k$$ are positive integers.

• If $$k=1$$ and $$a_1\leqslant 2$$, then it is possible.

• If $$k=1$$ and $$a_1\geqslant 3$$, then it is impossible since there are no two divisors which are coprime to $$p_1$$.

• If $$k=2$$ and $$(a_1,a_2)=(1,1)$$, then it is possible.

• If $$k=2$$ and $$(a_1,a_2)\not=(1,1)$$, then it is impossible since there are no two divisors which are coprime to $$p_1p_2$$.

• If $$k\geqslant 3$$ and $$(a_1,a_2,\cdots, a_k)\not=(1,1,\cdots,1)$$, then it is impossible since there are no two divisors which are coprime to $$p_1p_2\cdots p_k$$.

• If $$k\geqslant 3$$ and $$(a_1,a_2,\cdots, a_k)=(1,1,\cdots,1)$$, then it is impossible. The reason is as follows. The divisors which are coprime to $$p_2p_3\cdots p_k$$ are only $$1$$ and $$p_1$$. Also, the divisors which are coprime to $$p_1p_3p_4\cdots p_k$$ are only $$1$$ and $$p_2$$. So, the neighbors of $$1$$ have to be $$p_2p_3\cdots p_k$$ and $$p_1p_3p_4\cdots p_k$$. Then, it is impossible to place $$p_1p_2\cdots p_{k-1}$$ since the divisors which are coprime to $$p_1p_2\cdots p_{k-1}$$ are only $$1$$ and $$p_k$$.

• (+1) In the case $k=3$ I had roughly the same idea (because $pq$ limits its neighbors) but I didn't thought of repeating the argument for $qr$ and $pr$ .
– PNT
Feb 14, 2023 at 22:48