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?
 A: 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.
A: PNT has already answered i).
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$.
