Here is my candidate for the solution with the most overkill. We will use the following results from graph theory. Dirac's Condition: Let $G$ be a graph with $v \ge 3$ vertices. If every vertex has degree at least $\frac{v}{2}$, then $G$ has a Hamiltonian cycle. Chvatal's Condition: Let $G$ be a graph with $v$ vertices ($v$ odd). If every vertex has degree at least $\frac{v-1}{2}$, and at most $\frac{v-1}{2}$ vertices have degree exactly $\frac{v-1}{2}$, then $G$ has a Hamiltonian cycle. We can check that the divisor graph obeys one of these two conditions, provided that $n$ is not the product of two distinct primes. Can you find a solution with more overkill?

He-he. In another thread rrusczyk wrote that convex hull and discrete continuity are too complicated ideas... Your idea with Hamiltonian graph is absolurely right and clear. It was my first idea too. I always have in my mind this nice theorem.

an easy one we proof by induction we only need to proof that if n is an int and p is a prime and it's true for n it's true for N*p

some thing else how can I get some of those stars !!!!!!!

$ n=p^k is the answer $

I claim that all composites except for numbers of the form $pq$ work, where $p$ and $q$ are distinct primes. It is easy to see that $pq$ fails, and that numbers of the form $p^k$ work. I will now show that all numbers of the form $p^aq^b$ work for all pairs of $a$ and $b$ except for when they are both one. We first isolate the factors of the form $p^k$, and place them such that $p$ and $p^a$ are adjacent. Now, "split" open this circle and place $pq$ next to $p$ and $p^aq$ next to $p^a$. Since the numbers left all have some factor of $q$, they are all not pairwise prime, so "closing" the circle with these numbers yields a valid construction. I now show that numbers with $\geq 3$ primes work. For the three primes, take the previous construction, and split the circle open at $p$ and $pq$. Note that all the numbers we have left to place have some factor of the third prime $r$, so we can simply place $pqr$ next to $pq$ and $pr$ next to $p$ to achieve a valid construction. Now we can see that we can achieve four primes in a similar fashion: split at $p$ and $pr$, and suppose the fourth prime is $s$. We can place $ps$ next to $p$ and $prs$ next to $pr$ and place all factors that are divisible by $s$. This can clearly be extended to an indefinite number of primes, so we are done.

We claim that such an arrangement is possible iff $n$ is not the product of two distinct primes. First, we show that such an arrangement is impossible in the latter case; let $n=pq$, then the divisors of $n$ greater than $1$ are $p,q,pq$, but $p$ must be next to $q$ in any such circle, contradiction. Now, we show that such an ordering is possible for any other $n$. First, in the case that $n=p^k$ for some prime $p$ and integer $k\ge 2$, note that any ordering works. Additionally, remark that in the case $n=pqr$ for some primes $p,q,r$, we can take the ordering $\{p,pq,q,qr,r,rp,pqr\}$. In the case that $n$ is square-free, either we can use the construction for $n=pqr$, or $n$ has at least four prime divisors and we can take some prime divisor $p\mid n$, then take the construction for $n/p$, choose two adjacent elements $a,b$ in that construction, then insert the multiples of $p$ in some consecutive order with $ap$ next to $a$ and $bp$ next to $b$. Similarly, in the case that $n$ is not square-free, choose a prime $p\mid n$ such that $n/p$ is not square-free and insert multiples of $p$ similarly to before, or $n=p^k$ and we have already found the construction thereof. At least one of the criteria $\exists p\mid n \mbox{ s.t. } p^2\mid n$, $\exists p\ne q\ne r\ne p \mbox{ s.t. } pqr\mid n$ must hold as long as $n$ is not the product of exactly two distinct primes, hence we are done.

Claim: We can create such a circle for all composite numbers other than numbers of the form $n = pq$ where $p,q$ are distinct primes. If $n = pq$ with $p,q$ distinct primes, the three divisors that are greater than $1$ are $p, q, pq$. Obviously they do not meet the condition as $p,q$ are forced to be next to each other, and they are relatively prime to each other. There are a few cases we have to look at. The first case is if $n = p^k$ where $k \geq 2$. Obviously, all numbers of this form must satisfy the condition as all divisors $>1$ are multiples of $p$. The next case we have to look at is $p^aq^b$ with $a,b \geq 2$. Notice that all of the terms with the exception of the powers of $p$ and $q$ must share a common divisor as they contain powers of both $p$ and $q$. So, start with a circle of the divisors of $p^aq^b$ other than 1 and the powers of $p,q$. All of these divisors have both powers of $p$ and $q$. If you place all of the powers of $p$ between one pair of terms and all of the powers of $q$ between another pair of terms, you have a circle that satisfies the conditions. So, you can do it for this case as well. Another case to consider is the case where we have $pq^n$ with $n \geq 2$. Note that all of the divisors other than $1$ and $p$ have a power of $q$ in them. So, you can place all of the divisors greater than $1$ except for $p$ into a circle in such a way that there is at least one pair of adjacent numbers that are multiples of $p$ and place the $p$ in between that pair of adjacent numbers. So, it is possible for this case as well. There is one last case to consider, which is $n = p_1^ap_2^bp_3^c\ldots$ where $a,b,c,\ldots \geq 1$. First, we can start by creating a circle that contains the integers $p_1p_2,p_2,p_3,\ldots,p_np_1$. All multiples of $p_1$ go in between $p_np_1$ and $p_1p_2$ and so on with multiples of $p_k$ going between $p_{k-1}p_k$ and $p_kp_{k+1}$. So, it is also possible to create such a circle for this case. As all of the cases have been addressed, it has been proven that you can create such a circle for all composite numbers other than $n=pq$ with $p,q$ distinct primes.

First we shall show that for all numbers $n=p_1p_2p_3\dots p_k$ there is a possible arrangment, where $k \geq 3$. We define a $p_i$-sector to be a circle section of angle $\alpha$ where all the numbers that are on the circumference of the circle are divisible by $p_i$. We firstly throw on the numbers $p_i$ and $p_ip_{i+1}$ onto the circle for all $i$, where $1 \leq i \leq k$ and where all the indexes are taken $\text{mod}\; k$. Now we devise the following algorithm: The algorithm: We start by taking the $p_1$ sector, and we place all the numbers divisible by $p_1$ and who divide $n$, into the $p_1$ sector and we place this between $p_1$ and $p_1p_2$, now we do this for the $p_2$ sector, then for $p_3$, etc... When this is done we take a look at the repeating numbers and delete one of that number until we have just one of that number on the circle. By this way every single divisor is on the circle and the neighboring condition is satisfied.Because we have that in the $p_i$-sector the $GCD$ is equal to at least $p_i$. Now we shall show that it is possible for $n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k}$, where $k \geq 3$ We still use our algorithm but this time when we encounter a number of the form $p_1^{\beta_1}p_2^{\beta_2}\dots p_k^{\beta_k}$ we take a look at the exponents. Now if we have let's say number $d$, where $d \mid n$, depending on the exponent we place $d$ in the $p_i$ sector, if we have that $v_{p_i}(d) \geq v_{p_j}(d)$ for all $j$, where $1 \leq i,j \leq k$. Now again we delete until we are left with just one of $d$. Now we take a look at trivial $n=p^{\alpha}$, where $\alpha > 1$.This is an easy construction. We just place $p^i$, in ascending order on the circle, where $k \geq i > 0$. Now we look at $n=p^{\alpha}q^{\beta}$. Obviously when $n=pq$ this is impossible. So let's assume $WLOG$ that $\alpha \geq \beta$. We start off with the construction for $p^2q$.We place the numbers in the following order: $p,p^2,p^2q,q,pq$ onto the circle. Again we divide into the $p$ sector and $q$ sector. We now use our algorithm with the divisor types $p^{\gamma}q^{\delta}$ to generalize for $p^{\alpha}q^{\beta}$. Thus giving us the answer of $n \in \mathbb{N} \backslash (\mathbb{P} \cup \{1\} \cup \{pq \mid p\neq q;p,q\in \mathbb{P}\})$,where $\mathbb{P}$ is the set of primes. In other words the only solutions are all composite numbers except of the form $n=pq$, where $p,q$ are distinct primes

We claim that all composite numbers not in the form of $pq$ work, where $p$ and $q$ are primes. We have several cases. It is easy to see that numbers in the form $p^a$ work, where $p$ is a prime. For numbers in the form $n=p^aq^b$ where $a\geq2$ and $b\geq1$, we can take all of the factors of the form $p^k$, and put them in the order $p, p^2, \dots , p^a$. We then put $pq$ next to $p$, and $p^aq$ next to $p$ and $p^a$, respectively. Then, the rest of the factors have $q$ as a divisor, so none of them are relatively prime. Let $n=p_1^{n_1}p_2^{n_2}\dots p_k^{n_k}$, where $n_i\geq 1$ and $k\geq 3$. We start by putting the integers $p_1p_2,p_2,p_3,\ldots,p_np_1$ on the circle. We then put all multiples of $p_1$ in between $p_np_1$ and $p_1p_2$ and so on with multiples of $p_k$ going between $p_{k-1}p_k$ and $p_kp_{k+1}$. Thus, it is also possible to create such a circle for this case. Thus, we have proved that all cases work other than the case $pq$, as desired.

Extremely clunky solution: We claim that it works if the sum of the exponents of the prime factorization is $\ge 3$ or it is a prime power with exponent $\ge 2$. Another way of saying this is not $p_1 \cdot p_2$ where $p_1$ and $p_2$ are primes. (and of course also not $1$ or any prime, as the problem statement asks). It is obvious that $p_1 \cdot p_2$ is impossible as we must place $p_1,p_2,p_1p_2$, and since there are only 3, inevitably, $p_1$ and $p_2$ must be adjacent. The case $p^k$ works as they all share a common factor of $p$. The case $p_1^{e_1}p_2^{e_2}$ works as long as at least one of the exponents is $\ge 2$. For this we can place it around the circle with $n$ at the very top, then circling around with all the powers of $p_1$ on one side and $p_2$ on the other and then spamming the multiples of $p_1p_2$ that aren't $n$ at the bottom. If there are three or more primes, then the circle can be constructed as follows: $$p_1,(\text{all } d \mid n, p_1 \mid d, d \ne p_1p_2,p_1p_k),p_1p_2, p_2, (\text{all } d \mid n, p_1 \nmid d, p_2 \mid d, d\ne p_2p_3), p_2p_3,\ldots, p_k, p_k^2,\ldots , p_k^{e_k},p_kp_1.$$This works for more than 3 primes since from there, $p_kp_1 \ne p_1p_2$.

We define $p_1,p_2,p_3,\ldots$ as distinct arbitrary primes. The answer is any $n$ that cannot be expressed in the form $p_1p_2$. First we prove that no numbers of the form $p_1p_2$ work. The factors greater than $1$ here are $p_1,p_2,p_1p_2$. We can easily see by placing them in a circle (there is actually only one way to do this, since reflections and rotations don't change the result) that this arrangement doesn't work, since we have $p_1$ next to $p_2$. Now we prove that everything else works. First, consider a number of the form $p_1^k$ for some integer $k>1$. Clearly, all factors greater than $1$ of this number are divisible by $p_1$, so this works. The remainder of the solution assumes that $n$ is divisible by at least $2$ distinct primes. Next, consider a number of the form $p_1p_2p_3\ldots p_n$, with $n>2$. For convenience, we define $p_{n+1}=p_1$. We first place $p_1,p_2,p_3,\ldots,p_n$ a circle in that order. Then, we put $p_i p_{i+1}$ between $p_i$ and $p_{i+1}$. Afterwards, we may place any other divisors in the circle. We may do this by placing all divisors divisible by $p_1$ in between $p_1$ and $p_1p_2$. Then place all remaining divisors divisible by $p_2$ in between $p_2$ and $p_2p_3$, and so on. That is, we place all remaining divisors divisible by $p_i$ in between $p_i$ and $p_i p_{i+1}$. This clearly works, since all the numbers between $p_i$ and $p_i p_{i+1}$ share a factor of $p_i$, and $p_i p_{i+1}$ shares a factor of $p_{i+1}$ with $p_{i+1}$. Now suppose a number is of the form $p_1^2p_2$. We give the following explicit construction, which can easily be verified to work. Starting from the top and going clockwise, we place: $p_1,p_1^2,p_1p_2,p_2,p_1^2p_2$. Finally, we can induct to every other number. Given that $p_1^{k_1}p_2^{k_2}p_3^{k_3}\ldots p_n^{k_n}$ works, for positive integers $k_1,k_2,\ldots,k_n$, $p_1^{k_1+1}p_2^{k_2}p_3^{k_3}\ldots p_n^{k_n}$ will work as well. All factors of $p_1^{k_1+1}p_2^{k_2}p_3^{k_3}\ldots p_n^{k_n}$ are factors of $p_1^{k_1}p_2^{k_2}p_3^{k_3}\ldots p_n^{k_n}$, except for those divisble by $p_1^{k_1+1}$. Thus we can put all these "new factors" in between $p_1$ and $p_1 p_2$. Then all the numbers between $p_1$ and $p_1 p_2$ share a factor of $p_1$. Nothing else is changed, so the arrangement works. Thus we have finished the inductive step. Now, since $p_1$ is arbitrary, we can start from either $p_1^2p_2$ or $p_1p_2p_3\ldots p_n$ with $n>2$, and repeatedly apply the "inductive step" to reach any other composite number. Thus, we have proven that everything else works. We are done. $\blacksquare$

The answer is all $n$ which is not the product of two primes. Clearly, products of two primes fail, because in a circle of three elements, every two elements are adjacent. Yet the two distinct prime factors will be adjacent to each other, violating the problem condition. To show that all other numbers work, we proceed by induction on the number of distinct prime factors in $n$. Base Case. We will show that $n=p^k$ for $k \geq 2$ satisfy the conditions. Consider arranging the $k$ numbers in a circle in the order $p, p^2, p^3, p^4, \cdots, p^k$. This clearly works. (In fact, any placement of the numbers around the circle works!) We also need to show that $n=pqr$ satisfies the conditions, for primes $p, q, r$. This is not hard; arrange the numbers in the order $1, p, pq, q, qr, r, pr, pqr$. Clearly no two divisors are relatively prime. Inductive Step. Assume that $n= p_1^{k_1} p_2^{k_2}\cdots p_i^{k_i}$ satisfies the condition. We will show that $$n' = p_1^{k_1} p_2^{k_2}\cdots p_i^{k_i}p_{i+1}^{k_{i+1}}$$satisfies the conditions. Arrange the divisors of $n$ in a valid circle, which we know exists. Then, insert all divisors of $n'$ that contain $p_{i+1}$ (aka all divisors of $n'$ that are not divisors of $n$) consectutively into the circle, between $n$ and some number $j$. We can arrange the numbers such that the number adjacent to $n$ is $n'$, while the number adjacent to $j$ is $p_{i+1} \cdot j$. Since all the numbers between $n$ and $j$ satisfy the conditions, and so do the numbers in the consecutive ``block" (since they all contain the factor $p_{i+1}$) and the numbers between the two blocks, we have a valid placement for $n'$, as desired. Thus the induction is complete, and the assertion holds for all $n$ not the product of two primes.

We claim the answer is all $n$ not of the form $pq$ where $p\neq q$. It is clear that such $n$ fail. Otherwise, we do casework on the number of distinct prime divisors of $n$. Case 1: $n=p^k$. This clearly works because all divisors $>1$ have common factor $p$. Case 2: $n=p^a q^b$ where wlog $a\geq 2, b\geq 1$. Then, we may construct: \[\text{multiples of $p$}, pq, \text{multiples of $q$} , p^2q\] Case 3: $n$ has $p_1,\ldots,p_m$ as $m$ distinct prime divisors. Then, we may place \[p_1p_2,\text{multiples of $p_2$},p_2p_3, \text{multiples of $p_3$},p_3p_4,\ldots\]Thus, all $n\neq pq$ work, and we are done. $\blacksquare$.

The answer is all composite numbers not of the form $pq$. It's easy to see that this fails. We provide the construction for all other composites : First, $p^k$ works, so ignore that It's easy to get the construction for $p^a \times q^b, \max{(a,b)} \geq 2$ For all others - Let $n=p_1^{a_1} \times \dots \times p_k^{a_k}$. Start by placing $p_1$ anywhere on the circle. Then add $p_1^1, \dots, p_1^k$ in any arbitrary order, clockwise (all numbers are added adjacent to the previous one - figure is attached for reference). Then add all numbers divisible by $p_1p_2$. Then add all powers of $p_2$. Keep doing that with $p_3$ and so on. At the end, add all remaining numbers divisible by neither $p_1$ or $p_k$, but divisible by say $p_i$ to the group of numbers not coprime to $p_i$ (for example, by adding them between $p_i$ and $p_ip_{i+1}$). Also add all remaining numbers not divisible by $p_1p_k$ but divisible by $p_1$ anticlockwise to $p_1$, and do the same with $p_k$ except add them anticlockwise. In the middle of the two groups, add numbers divisible by $p_1p_k$ (at least $p_1p_k$ must have been unused ). This satisfies the required conditions $\blacksquare$

The answer is all composites excluding semi-primes. It's easy to see semi-primes, i.e. $n = p_1 \cdot p_2$, must fail, as $p_1$ and $p_2$ are adjacent in all possible arrangements. We now proceed with induction on the number of distinct primes dividing $n$. (In this solution, we assume the first and last terms of our arrangement on paper are actually adjacent in the circle.) Base Cases (Prime Powers and $K = 2$ Primes, Excluding Semi-Primes): If $n = p_1^{e_1}$ where $e_1 \ge 2$, then the construction $$p_1, p_1^2, \ldots, p_1^{e_1}$$obviously works. If $n = p_1^{e_1} \cdot p_2^{e_2}$ such that $e_1 = e_2 = 1$ doesn't hold, then the construction $$p_1, p_1^2, \ldots, p_1^{e_1}, p_1 \cdot p_2, p_2, p_2^2, \ldots, p_2^{e_2}, \{p_1^{a} \cdot p_2^{b}\}$$clearly works, where $a$ ranges from $1$ to $e_1$ inclusive, and $b$ ranges from $1$ to $e_2$ inclusive, such that $a = b = 1$ doesn't occur. Inductive Hypothesis: Assume the desired construction is possible for all $n$ with $k = m$ distinct prime divisors. We will show it is also possible for all $n$ with $k = m+1$ distinct prime divisors. Induction Step: Suppose $$d_1, d_2, \ldots, d_i$$is a satisfactory arrangement of all the divisors, other than $1$, of some arbitrary $n$ with $k = m$ distinct prime divisors. If $p_{m+1}$ denotes our $m+1$th prime divisor, then the construction $$p_{m+1}, p_{m+1}^2, \ldots, p_{m+1}^{e_{m+1}}, d_1 \cdot p_{m+1}^{e_{m+1}}, d_1 \cdot p_{m+1}^{e_{m+1} - 1}, \ldots, d_1, \{d_2 \cdot p_{m+1}^{t} \}, \{d_3 \cdot p_{m+1}^{t} \},$$$$ \ldots, \{d_{i-1} \cdot p_{m+1}^t \}, d_i, d_i \cdot p_{m+1}, \ldots, d_i \cdot p_{m+1}^{e_{m+1}}$$clearly works, where $t$ ranges from $0$ to $e_{m+1}$ inclusive. $\square$ Because all composites are divisible by at least $2$ distinct prime divisors, we're done. $\blacksquare$

Clearly numbers of the form \(pq\) where \(p,q\) are two primes don't work. We show that numbers of the form \[p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdots p_k^{\alpha_k}\]where at least two of the \(\alpha_i\) are positive. If we show this, we can conclude that this set of numbers are the final answer, because the set of all numbers of the form \(pq\) and the other set are two disjoint sets whose union is the set of all composite natural numbers. For the numbers of the form we wanted to show work, start with \(p_1\) and go all the way till \(p_1^{\alpha_1}\), then we place \(p_1^{\alpha_1}p_2\) and then we place \(p_2\) and then place \(p_1^{\alpha_1}p_2^2\) and go all the way up till \(p_1^{\alpha_1}p_2^{\alpha_2}\), and then place \(p_1^{\alpha_1}p_2^{\alpha_2}p_3\) and then place \(p_3\) and keep following this pattern, in the end you would reach \(p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdots p_k^{\alpha_k}\). You can easily see that this way, no two adjacent numbers are relatively prime, and thus our desired conclusion follows.

Outline (indices taken mod k): Numbers of the form $pq$ don't work, then for powers of primes it works. For anything else we have $p_1^{e_1}p_2^{e_2}\dots p_k^{e_k}$. First place $p_1p_2,p_2p_3,\dots,p_kp_{k+1}$ on the circle in that order. Then for all other numbers we can just place them between the numbers $p_{i-1}p_i$ and $p_ip_{i+1}$ if $p_i$ is a divisor of that number.

The claim is that all the composite numbers $n\neq pq,$ where $p,q$ are primes, work. First observe that $n=pq,$ $p,q$ primes, does not work. Indeed, in this case divisors of $n$ are $1,p,q,pq$, so only way we can arrange them in a circle is $p$ then $pq$ and then $q$, but clearly $p,q$ are also adjacent here, so this does not work. Now assume $n=p^{\alpha}q^{\beta}, \alpha\geq 2, \beta\geq 1.$ To see that this works fine, isolate $p, p^{2},\dots,p^{\alpha}$ then put $p^{\alpha}q$ adjacent to $p^{\alpha}$. Now the remaining factors are $p^{\alpha}q^2,\dots, p^{\alpha}q^{\beta}.$ So we simply put all these factors after $p^{\alpha}q$. So last adjacent pair will be $(p^{\alpha}q^{\beta},p)$ which have gcd $p$. So this construction clearly works. At last, assume $n=p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{r}^{k_{r}}, r\geq 3, k_{i}\geq 1, i=1,2,3,\dots,r.$ Observe that when $k_{i}>1$ we can just arrange all the divisors like previous arrangement. So now we only have to check the case when $k_{i}=1$, that is $n=p_{1}p_{2}\cdots p_{r},p_{1}\geq 3.$ For this, put all $p_{1}p_{2},\dots p_{r}p_{1}$. Now put the divisors containing $p_{1}$ between $p_{r}p_{1}, p_{1}p_{2}$ then put all divisors containing $p_{2}$ between $p_{1}p_{2},p_{2}p_{3}$ and we continue this way, put $p_{i}$ between $p_{i-1}p_{i},p_{i}p_{i+1}.$ So we see this clearly works. Hence this completes the proof.$\boxed{}$

The answer is all not of the form $n \equiv pq$,clearly any number of this form doesn't work,to show number of the form \[p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdots p_k^{\alpha_k}\]use the above(no below) construction.

We claim the answer is all $n$ with $1$ or at least $3$ prime divisors. $n$ has one prime divisor $n=p^k$ This clearly works if we place it in the form of $p, p^2, p^3, ... , p^k.$ $n$ has at least $3$ prime divisors We partition the set of divisors of $n$ into $f(n)+2$ sets, where $f(n)$ is the number of prime divisors of $n$ as follows, where $n = p_1^{e_1}p_2^{e_2}...p_k^{e_k}.$ $S_i \text{with}1 \leq i \leq k$ where all $x \in S_i$ is in the form of $p_i^{m}, 1 \leq m \leq e_i, 1 \leq i \leq k$ $S_{i,j}, 1 \leq i < j \leq k$where all $x \in S_{i, j}$ is in the form of $p_1^{x_1},p_2^{x_2}, ... ,p_k^{x_k}, \text{where at exactly 2 of the} x_i, x_j \geq 1$ $S_{i_1, i_2, ..., i_m}$where all $x \in S_{i_1, i_2, ..., i_m}$ is in the form of $p_1^{x_1},p_2^{x_2}, ... ,p_k^{x_k}, \text{where at least 3 of the} x_{i_1}, x_{i_2}, ... , x_{i_m} \geq 1$ Now, we develop our algorithm as follows: Place all the $x \in S_i$ all adjacent Place all the $x \in S_{i,j}$ adjacently and then stick them between the $S_i$ and $S_j$ block For all $x \in S_{i_1, i_2, ... , i_m}, $ first stick them all together, and then place it in between $S_{i_1}$ and $S_{i_2}$ [\list] This algorithm clearly works, so we are done.

We will prove that the only time that $n$ doesn't work is when $n=pq$ where $p$, $q$ are distinct primes. It is easy to see that if $n=pq$ where $p$ and $q$ are distinct primes, it is impossible to place $p, q, pq$ in a circle such that $p$ and $q$ are not bordering. If $n=p^k$ it is easy to see that it will work since any divisor of $n$ that is greater than 1 will be a multiple of $p$. Now we will prove that other $n$ work as well. Let $n=p_1^{e_1}p_2^{e_2}\dots p_k^{e_k}$ where $p_1, p_2, \dots, p_k$ are distinct primes and is in strictly increasing order. That is, $p_1<p_2<\dots<p_k$. Now we define $A_i$ from $1\le i\le k$ to be the strictly increasing set containing the divisors of $n$ such that the divisor is a multiple of $p_i$ but is not a multiple of $p_j$ with $j<i$. We will now perform two changes on $A_1$. Take the last element of $A_1$ and move it to the front of the set without changing the order of the other elements. Take the element $p_1\cdot p_2$ and move it to the end of the set without changing the order of the other elements. For the second operation, it is quite obvious that the number $p_1\cdot p_2$ does appear in $A_1$ since it is a multiple of $p_1$. Now imagine if we strung together all of these sets into a circle so that the last element of some $A_j$ and the first element of $A_{j+1}$ are neighboring. If $j=k$ then the last element of $A_k$ and the first element of $A_1$ are neighboring. We will claim that this construction works. It is easy to see that the first element of $A_1$ and the last element of $A_k$ are not coprime because the first element of $A_1$ is now $n$. Notice that the last element of $A_1$ is now $p_1p_2$ and the first element of $A_2$ is $p_2$ so the connection between $A_1$ and $A_2$ works. Furthermore, it is easy to see that if $1<j<k$ then the last element of $A_j$, $p_jp_{j+1}\dots p_k$ and the first element of $A_{j+1}$ which is $p_{j+1}$ are obviously not coprime so we are done. $\blacksquare$

Induction for number prime divisor.

Every number that isn't equal to pq with p and q being prime works. To prove this we will show that n works if it is one of the following: -$p^2q$ -$pqr$ -$p^k$ where $p, q,$ and $r$ are prime and $k$ is a positive integer. Then we will prove that if $n$ works then $xn$ works where $x$ is any positive integer. Note that putting the divisors greater than 1 on a circle is equivalent to putting the proper divisors greater than 1 on a line. We will now prove it is possible for the three cases mentioned earlier. Just do the following: -$p^2q$: $p^2$ $p$ $pq$ $q$ -$pqr$: $p$ $pq$ $q$ $qr$ $r$ $pr$ -$p^k$: $p$ $p^2$ $\ldots$ $p^k$ Now we will prove that if you multiply $n$ by any integer you will still be able to put the divisors on a circle. It suffices to show that you can multiply $n$ by a prime $p$ and still be able to put the divisors on a circle. If it is possible to put the divisors of $n$ on a circle satisfying the given property, for each divisor $d$, insert $pd$ after $d$. Then, before $n$, insert $p$ and $pn$. Now we will prove it is impossible to put the divisors of $pq$ on a circle so that neighbors are not relatively prime. We are putting $p, q,$ and $pq$ on a circle. Then, $p$ and $q$ are next to each other, a contradiction.

The answer is all $n$ not equal to the product of two distinct primes. We first show all such $n$ work. Case 1: $n=p^k$, where $p$ is prime and $k\ge 2$. Then all divisors of $n$ greater than $1$ are divisible by $p$, so any arrangement works. Case 2: $n=p^aq^b$, where $p,q$ are distinct primes and $a\ge 2$. First, arrange some divisors as follows: $p, pq, q, p^2q$. Then for each remaining divisor, place it next to $p$ if it's divisible by $p$, or next to $q$ if it's divisible by $q$. Case 3: $n=p_1^{e_1}p_2^{e_2}\ldots p_k^{e_k}$, where the $p_i$ are distinct primes and $k\ge 3$. Arrange some divisors as follows: $p_1, p_1p_2, p_2, p_2p_3, p_3, \ldots p_kp_1$. For each remaining divisor, if it's divisible by $p_i$, put it next to $p_i$ on the circle. This ensures no two adjacent divisors are relatively prime. Now, we show $n=pq$ does not work. The three divisors that must be arranged are $p$, $q$, and $pq$, and no matter the arrangement, $p$ and $q$ are adjacent, a contradiction.

Let $n$ be juxtaposable if we can arrange $n$ in such a way, and let $\tau(n)$ be the number of divisors of $n$, $\omega(n)$ of which are prime. Claim: if $n$ is juxtaposable, $\omega(n)\ge1$ and $q\nmid n$ is a prime, then $q^kn$ is juxtaposable for any integer $k\ge2$. Moreover, if $\omega(n)\ge2$ then $q^kn$ is juxtaposable for any integer $k\ge1$. First, we show that $q^kn$ is juxtaposable for $k\ge2$. Suppose we know that $n=\prod_{i=1}^{\omega(n)}p_i^{a_i}$ is juxtaposable with $d_1,d_2,\ldots,d_{\tau(n)-1}$ arranged clockwise in the circle, where $d_{\tau(n)-1}=n$. Insert $qd_1$ to the left of $d_1$, and $q^2d_i$ in between $qd_1$ and $d_1$, and each $q^ad_i$ and $q^a$ in between $qd_1$ and $q^2d_1$. We end up with: $$qd_1,q,q^2,\ldots,q^k,q^3d_1,q^3d_2,\ldots,q^3d_{\tau(n)-1},q^4d_1,q^4d_2,\ldots,q^4d_{\tau(n)-1},\ldots,q^kd_1,q^kd_2,\ldots,q^kd_{\tau(n)-1},q^2d_1,d_2,d_3,\ldots,d_{\tau(n)-1}$$written in the circle. Then $\gcd(qd_1,d_{\tau(n)-1}\ge\gcd(d_1,d_{\tau(n)-1})>1$, $\gcd(q^ad_i,q^bd_j)\ge q^{\min\{a,b\}}>1$ for all $3\le a,b\le k$ and $1\le i,j\le\tau(n)-1$, and $\gcd(q^2d_1,d_2)\ge\gcd(d_1,d_2)>1$, so this construction works. Then, suppose $\omega(n)\ge2$ and $k=1$. We have $\tau(n)\ge4$. If $i=1$ or $i\ge3$, insert $qd_i$ to the right of $d_i$. Then, insert $qd_2$ to the left of $d_2$ and $q$ between $qd_1$ and $qd_2$. We end up with: $$d_1,qd_1,q,qd_2,d_2,d_3,qd_3,\ldots,d_{\tau(n)-1},qd_{\tau(n)-1},$$which, similarly to before, shows that $n$ is juxtaposable. We claim that the only $n$ that is not juxtaposable are the product of two primes. Now we induct on $\omega(n)$, with the following two base cases. If $\omega(n)=1$, $n=p^a$, so we can simply write the divisors: $$p,p^2,\ldots,p^a.$$If $\omega(n)=2$, $n=p^aq^b$ and $(a,b)\ne(1,1)$. Note that $p^a$ and $q^b$ are juxtaposable, so if either $a$ or $b$ is at least two, by the claim, $n$ is juxtaposable. Then the induction step is just the claim, so we're done.

USAMO 2005.1. Determine all composite positive integers $n$ for which it is possible to arrange all divisors of $n$ that are greater than 1 in a circle so that no two adjacent divisors are relatively prime. Solution. We claim that only all numbers that are products of two distinct primes do not satisfy the conditions. It is clear that we cannot, for a number of the form $n=pq$ where $p,q$ are distinct primes, arrange the divisors $p,q,pq$ in a circle so that no two adjacent divisors are relatively prime, because $p$ and $q$ must be adjacent regardless of the arrangement. For the other direction, note that the case when $n=1$ and $n=p$ for some prime is vacuous. If $n$ is a perfect prime power $p^k$, we can arrange the divisors arbitrarily. If $n=p^aq^b$ for distinct primes $p,q$ and $a>1$, we can place $pq$ and $p^2q$ and place the multiples of $p$ in one arc and the multiples of $q$ in the other arc. This obviously satisfy the problem condition. It suffices to consider the case when $n=\prod\limits_{j=1}^kp_j^{e_j}$ for $k\ge 3$ and pairwise distinct primes $p_1,\dots,p_k$. Then we can place $p_1p_2,p_2p_3,\dots,p_{k-1}p_k,p_kp_1$ in that order and place the multiples of $p_j$ in the arc $p_{j-1}p_j$ and $p_jp_{j+1}$ that does not contain the number $p_{j+1}p_{j+2}$, indices taken modulo $k$. It is easily seen that this arrangement satisfies the problem condition, and hence completing the proof.

Denote the multiples of $n$ as $m(n).$ Clearly, $pq$ doesn't work and $p^k$ works for all primes $p$ and $q.$ Also, $p^k$ for $k>1$ works. We claim all other positive integers work. For $n=p^kq^{\ell}$ with $\ell\ge 1$ and $k>1$ the construction $$\dots,pq,m(p),p^2q,m(q),\dots$$suffices, where the multiples of $pq$ are counted in multiples of $p.$ When $n$ has at least three prime factors $p_1,p_2,\dots p_i,$ the construction $$\dots,m(p_1),m(p_1p_2),m(p_2),\dots,m(p_{i-1}p_i),m(p_i),m(p_ip_1),\dots$$works. $\square$

We claim that all numbers not of the form $p_1p_2$ for distinct primes $p_1$ and $p_2$ work. Clearly $p^k$ always works and $p_1p_2$ does not. Let $n=p_1p_2…p_m$ for $m\geq 3$. Arrange the primes $p_1$ thru $p_m$ clockwise in a circle, and put $p_1p_m$ between $p_1$ and $p_m$. Now, between $p_i$ and $p_{i+1}$ insert all divisors whose smallest prime factor is $p_i$, such that $p_ip_{i+1}$ is adjacent to $p_{i+1}$. This satisfies the requirements. Now suppose $n=p_1^{k_1}p_2^{k_2}…p_m^{k_m}$. We proceed by induction. Clearly our condition can be satisfied for $k_1=k_2=…=k_m=1$. Now suppose one of the exponents is greater than $1$, WLOG let it be $k_1$. Then if there exists a valid drawing for $p_1^{k_1-1}p_2^{k_2}…p_m^{k_m}$, we just need to insert all divisors of $n$ that are divisible by $p_1^{k_1}$, and so if we place $p_1^{k_1}q$ clockwise adjacent to $p_1^{k_1-1}q$, then we have a valid configuration for $n$, completing the inductive step. Thus, any number with three or more prime factors satisfies the problem statement. For $n=p_1^2p_2$, we can arrange the numbers consecutively as follows: $p_1,p_1^2,p_1^2p_2,p_2,p_1p_2$, and using the inductive statement above, any number with two prime factors and an exponent greater than one in its prime factorization works, and we are done.

The answer is all prime powers and numbers with at least 4 divisors, none of which is equal to 1. (This is equivalent to saying that it works for positive integers not of the form $n=pq$, where $p$ and $q$ are primes). For prime powers, every arrangement works. So assume $n$ is not the power of a prime.

Now assume that $n$ is has less than four divisors and is not a prime power, i.e. it is of the form $pq$ and thus has divisors $pq,p,q$. This forces $p$ and $q$ besides each other, so this case does not work.

I believe the following solution is much cleaner than a lot of the solutions on the thread, so long as it's not a fakesolve (if anyone could check for me). Call all $n$ that satisfy the condition expressible. The key claim is the following: Claim: Suppose $n$ is expressible and let $p$ be a prime such that $\gcd(n,p)=1$. Then, for every integer $k\geq 1$, $np^k$ is also expressible. Proof. Suppose the divisors of $n$ are $d_1, \dots, d_m$ arranged in that order as well. Then, we will arrange the divisors of $np^k$ as such: \begin{align*} \dots , d_2, d_1, pd_1, (\text{all other divisors that are a multiple of } p), pd_2, \dots, pd_m, d_m. \end{align*}Since $p^2$ where $p$ is a prime is expressible, all nonsquarefree $n$ are expressible. Now, we look at squarefree $n$. Clearly, $pq$ is not expressible but $pqr$ is, as the following arrangement works: \begin{align*} p, pq, pqr, q, qr, r, pr. \end{align*}Hence, all squarefree $n$ that have more than $3$ distinct prime divisors are expressible. Therefore, all composite $n$ are expressible except for when $n=pq$ where $p,q$ are distinct primes.

The answer is $n\in \mathbb{Z}^+-\left\{\{p_ip_j\}\cup \{p_i\}\right\}$, where $p_i$ and $p_j$ are primes Let the arrangement with no two adjacent divisors being relatively prime be good. For $n=p_ip_j$, the divisors are $p_i,p_j$ and $p_ip_j$. Since $\gcd(p_i,p_j)=1$ and $p_i,p_j$ will be adjacent in every possible arrangement, so no good arrangement is possible. Claim: A good arrangement is possible for $n=p^k$ and $n=p_1p_2\cdots p_k$, where $p,p_1,p_2,\cdots,p_k$ are primes and $k>2$ Proof: For $n=p^k$, the divisors of $n$ are $\{p,p^2,\cdots, p^k\}$. Since $\gcd(p^m,p^n)>0$ for $m,n>0$, then every arrangement is a good arrangement. For $n=p_1p_2\cdots p_k$, we will use induction. We have that, for $n=p_1p_2p_3$, we get [asy][asy] import graph; size(5cm); draw(circle((0,0),5),red+linewidth(1pt)); dot((5,0),blue); dot((0,5),blue); dot((-5,0),blue); dot((3.53553390593,3.53553390593),blue); dot((-3.53553390593,3.53553390593),blue); dot((-3.53553390593,-3.53553390593),blue); dot((3.53553390593,-3.53553390593),blue); label("$n$", (0,5), N); label("$p_1$", (-3.53553390593,3.53553390593), NW); label("$p_1p_3$", (-5,0), W); label("$p_3$", (-3.53553390593,-3.53553390593), SW); label("$p_3p_2$", (3.53553390593,-3.53553390593), SE); label("$p_2p_1$", (5,0), E); label("$p_2$", (3.53553390593,3.53553390593), NE); [/asy][/asy] So a good arrangement is possible for $k=3$. Assume that, it is possible to arrange for $k=k-1$. Thus, the arrangement will look like [asy][asy] import graph; size(5cm); draw(circle((0,0),5),red+linewidth(1pt)); dot((5,0),blue); dot((0,5),blue); dot((-5,0),blue); dot((3.53553390593,3.53553390593),blue); dot((-3.53553390593,3.53553390593),blue); dot((-3.53553390593,-3.53553390593),blue); dot((3.53553390593,-3.53553390593),blue); label("$n$", (0,5), N); label("$p_ap_b\cdots$", (-3.53553390593,3.53553390593), NW); label("$\vdots$", (-5,0), W); label("$\ddots$", (-3.53553390593,-3.53553390593), SW); label("$\cdots$", (3.53553390593,-3.53553390593), SE); label("$p_ip_j\cdots$", (5,0), E); label("$\ddots$", (3.53553390593,3.53553390593), NE); [/asy][/asy] where $a,b,i,j\leq k-1$. For $k=k$, we have $n=p_1p_2\cdots p_k$. Now, we can group the divisors having $p_k$ in them. Thus we get, [asy][asy] import graph; size(5cm); draw(circle((0,0),5),red+linewidth(1pt)); dot((5,0),blue); dot((0,5),blue); dot((-5,0),blue); dot((3.53553390593,3.53553390593),blue); dot((-3.53553390593,3.53553390593),blue); dot((-3.53553390593,-3.53553390593),blue); dot((3.53553390593,-3.53553390593),blue); label("$n$", (0,5), N); label("$p_ap_b\cdots$", (-3.53553390593,3.53553390593), NW); label("$\vdots$", (-5,0), W); label("$p_ip_j\cdots$", (-3.53553390593,-3.53553390593), SW); label("$p_ip_k$", (3.53553390593,-3.53553390593), SE); label("\vdots", (5,0), E); label("$p_jp_k\cdots$", (3.53553390593,3.53553390593), NE); [/asy][/asy] Therefore, $n=p_1p_2\cdots p_k$ can have a good arrangement for $k>2$. $\blacksquare$ From above proof of $n=p_1p_2\cdots p_k$, we can infer that if $n$ has a good arrangement, then $np$ also has a good arrangement for $p$ being a prime. Since $n=p_1p_2\cdots p_k$ is possible, then $n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$ is also possible for $a_i\geq 0$. Thus all composite $n$ are possible, except $n=p_ip_j$

My first combinatorics post . Hope I didn't fakesolve The answer is all $n$ that are not represented as $n=p_1p_2$ for distinct primes $p_1,p_2$. There are three cases for $n$: 1)$n=p^a$. This is always possible since all divisors of $n$ greater than 1 are divisible by $p$ and thus are not coprime with each other. 2)$n=p_1p_2$ for distinct primes $p_1,p_2$. This is impossible since there are only three divisors of $n$ greater than 1 and $p_1,p_2$ are always adjacent in a circle and are relatively prime. 3)$n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$ for distinct primes $p_1,p_2, \cdots p_k$. We set the construction of this case like this: Define $b_i$ as a group of divisors of $n$ greater than 1 that are divisible by $p_i$, not divisible by $p_j$ and the last term being divisible by $p_{i+1}$ for $1 \leq j \leq k-1, 1 \leq i \leq k, j<i$ (To avoid confusion we define $k+1 \equiv 1$). Note that in this configuration, the last term of $b_k$ will be divisible by $p_1$. For example terms of $b_1$ will include all divisors that are divisible by $p_1$ except the last term of $b_k$, terms of $b_2$ will not be divisible by $p_1$, terms of $b_3$ will not be divisible by $p_1, p_2$ and so on. Now when these groups are in order in a circle, all the divisors adjacent to each other will not be coprime and we're done.

There are three cases to consider, when $n = p_1^{e_1}$, $n = p_1p_2$ and $n = p_1^{e_1} p_2^{e_2}p_3^{e_3} \cdots p_k^{e_k}$. For the first case $n = p_1^{e_1}$ it is obvious on how to put the factors in the circle. For the second case $n = p_1p_2$ we claim that it is impossible to put them on a circle and this obvious as to why. Now we look at the case when $n = p_1^{e_1} p_2^{e_2}p_3^{e_3} \cdots p_k^{e_k}$. Here is the construction:

We claim that all $n$ will work except for those in the form $n=p_{1}*p_{2}$, where $p_{1}$ and $p_{2}$ are primes. First we will show that $n=p_{1}*p_{2}$ does not work (trivial) Construction: We start with an empty circle. Let $n=p_{1}^{a_{1}}*p_{2}^{a_{2}}*...$. Add $n$ to this circle. Then, pick a prime from the prime factorization of $n$ (WLOG $p_{1}$) and repeatedly add multiples of it to the circle, ensuring that the last added factor contains another factor. For example: consider $n=2^{2}*3^{2}=36$ Once such configuration would be 36 - 2 - 4 - 18 - 12 - 6 - 3 - 9 - 36 This construction only doesn't work when a "transition" that is already taken: meaning that the transition (which is the product of 2 primes) is $n$, and since we have already proved that, we are done. $\blacksquare{}$

Another solution cuz why not We claim that $n$ can be all compositive positive integers except for those in the form $p_{1}*p_{2}$. We begin by adding $n$ to the circle. We can split the problem up into 3 cases as follows: $\textbf{Case 1}$ $n=p_{1}^{q_{1}}$, where $p_{1}$ is prime. It is trivial that such a configuration must occur. $\textbf{Case 2}$ $n=p_{1}*p_{2}$, where $p_{1}$ and $p_{2}$ are both prime. It is also trivial that there are no configurations that satisfy the problem conditions. $\textbf{Case 3}$ $n=p_{1}^{q_{1}}*p_{2}^{q_{2}}*...*p_{k}^{q_{k}}$, where $p_{i}$ is prime for all $1 \le i \le k$. For simplicity, WLOG $p_{1} < p_{2} < ... < p_{k}$. Define a "transition" as $p_{a}*p_{a+1}$ for $1 \le a \le k-1$. Add all "transitions" in order $p_{1}, p_{2}, ..., p_{k}$ to the circle in a clockwise manner. Then, for the remaining factors, insert them immediately after the second occurrence of the least prime factor, reading from $n$, EXCEPT for $p_{1}$, where you can insert it after $n$. This completes the proof. $\blacksquare{}$

Claim: We claim that only composite $n$ that are not of the form $n = pq$ where $p, q$ are distinct primes work. To quickly show $n = pq$ is not feasible, observe that $p$ and $q$ must be adjacent in the circle, which is absurd. To finish our claim, we aim to demonstrate a construction for every other possible prime factorization, which we will do in cases. Case 1: $n = p^a$ for some prime $p$ and some integer $a \ge 2$. Every divisor besides $1$ of $n$ is divisible by $p$, so any arrangement works. Case 2: $n = p^a q^b$ work for distinct primes $p, q$ and $a, b$ are positive integers with $(a, b) \ne (1, 1)$. We demonstrate a construction. Observe that for numbers of the form $n = p^a q^b$, we can construct the cycle (arrangement of the divisors in the circle) $$p \to p^2 \to p^3 \dots \to p^a \to$$$$p^2q \to p^3q \to \dots \to p^aq \to$$$$pq^2 \to p^2q^2 \to p^3q^2 \dots \to p^aq^2 \to$$$$pq^3 \to p^2q^3 \to p^3q^3 \dots \to p^aq^3 \to$$$$\dots$$$$pq^b \to p^2q^b \to p^3q^b \dots \to p^aq^b \to$$$$q \to q^2 \to q^3 \dots \to q^b \to pq$$ Case 3: $n$ has at least $3$ prime factors. Let $n = p_1^{e_1} p_2^{e_2} \dots p_k^{e_k}$ be the prime factorization of $n$, where $p_i$ are distinct prime factors of $n$, and $p_1 < p_2 \dots < p_k$. Observe that we can classify any divisor of $d~|~n$ with a $k$-sized binary tuple, where a $1$ in the $i$-th position means $p_i~|~d$, and a $0$ denotes otherwise. For example, if a divisor generated the tuple $(0, 1, 1, 0, 1)$, it has $p_2, p_3, p_5$ as factors. With this new definition in mind, observe that it suffices to construct a cycle of all binary tuples of size $k$ except the all-$0$ tuple, such that any adjacent tuples have a $1$ in the same position (This is sufficient as we can group terms with the same generated tuple together.) We proceed with induction for $k \ge 3$, here is a construction for $k = 3$: $$(1, 0, 0) \to (1, 1, 0) \to (0, 1, 0) \to (0, 1, 1) \to (0, 0, 1) \to (1, 0, 1) \to (1, 1, 1)$$Now assume that for $k = t$, there exists some cycle $X_1 \to X_2 \dots \to X_{2^t - 1}$ that works. To finish the induction, we construct a valid cycle for $k = t + 1$. Without loss of generality, assume that $X_{2^t - 1}$ is the all-$1$ tuple of size $t$. Suppose $A_i$ and $B_i$ are the tuple $X_i$ with an extra $0$ and $1$ appended to the rightmost end respectively for integers $1 \le i \le 2^t - 1$. Then $$A_1 \to A_2 \dots \to A_{2^t - 1} \to B_1 \to (0, 0, \dots, 1) \to B_2 \dots \to B_{2^t - 1}$$is a valid sequence, where the tuple between $B_1$ and $B_2$ contains $t$ zeroes. Therefore, the induction is complete, and all positive integers $n$ with at least $3$ prime factors work. Collectively, all of our steps show that only composite positive integers $n$ that satisfy the condition cannot be expressed as the product of two distinct primes. Our proof is complete. $\blacksquare$

The answer is all integers not of the form $pq$, where $p$ and $q$ are prime numbers. We will show that all other integers work. It's easy to see that numbers of the form $p^k$, $k\ge 1$ work because $p$ divides each one of the divisors of $p^k$. Next, consider the case $n=p^{k_1}\cdot q^{k_2}$ where $k_1$, $k_2$ are not both equal to $1$. Also, WLOG $k_1\ge k_2$. Place $p$ and $q$ in the circle first. We can then find two numbers that are able to "fill" the gap between $p$ and $q$, say $pq$ and $p^2q$. It's easy to see then that we can place the remaining divisors of $p^{k_1}\cdot q^{k_2}$ to make a good circle, as shown in the following construction: Finally, consider the case $p_1^{k_1}p_2^{k_2}\cdots p_m^{k_m}$. Like before, place $p_1$, $p_2$, $\ldots$, $p_m$ in the circle first. Then, use $p_1p_2$, $p_2p_3$, $\ldots$, $p_{m-1}p_m$ to "fill" the gaps between adjacent primes. It's to easy to see then that we can place the remaining divisors of $n$ to make a good circle, shown in the construction below. It's trivial to see that all $n=pq$ fail, so we're done. $\blacksquare$

All positive integers work except $\left\{1,pq\right\}$ where $p$ and $q$ are two distinct primes. Divide into cases where the prime factorization has $\ge 3$ primes in it, $2$ or $1$. $p^k$ clearly works for $k\ge 1$ and $pq$ clearly doesn't work for distinct $p$, $q$. For the base case for $k=3$, we have the image below. Now for an increase in the value of $k$ to $k+1$, note that the divisors that get introduced are $p_{k+1} \times \left\{\text{set of divisors of } p_1\cdot p_2 \cdots p_k\right\}$. For this we can select a divisor from the configuration for $k$ from induction and its neighboring divisor and then insert the new divisors as shown below. For increasing the power of a prime (WLOG $p_1$) in the factorization from $e$ to $e+1$, we can see that the new divisors that get introduced are those who have $\nu_{p_1}(\text{divisor}) = e+1$. Now note in the configuration of the inductive hypothesis, that the divisor adjacent to $p_1$ must also have $p_1$ in it. Thus we can insert all the new divisors in between the two selected divisors as shown below. And we are done.

The answer is all composite numbers not of the form $pq$, where p, q are primes. It is easy to see by hand that $n = pq$ doesn't work. Also, $n = p^a$ , where $a \geq 2$ works. Arrange the divisors as {$p$, $p^2$, ... , $p^a$, $p$}, which works. Now we show that $$ n = p_1^{a_1} \cdot p_2^{a_2} ... \cdot p_m^{a_m} $$where, $m \geq 2$, $a_i \geq 1$, works . We do so using induction. Base case: $m = 2$ Consider the arrangement, {$p_1$, $p_1^2$, ... ,$p_1^{a_1}$, $p_1 p_2$, $p_2$, $p_2^2$, ..., $p_2^{a_2}$, $p_1 p_2^2$, ... , $p_1^{a_1} p_2^{a_2}$, $p$}, which clearly works Inductive hypothesis: Assume for $m = k$, the required arrangment is possible. Inductive step: For $m = k+1$ By inductive hypothesis, we have an arrangement for $ n = p_1^{a_1} \cdot p_2^{a_2} ... \cdot p_k^{a_k} $. We make the construction for $m = k+1$ by placing the divisors containing $p_{k+1}$ in the arrangement of $m = k$. We place $p_{k+1} \cdot p_1$ next to $p_1$ then all the divisors that contain $p_{k+1}$ and finally $ p_1^{a_1} \cdot p_2^{a_2} ... \cdot p_k^{a_k} \cdot p_{k+1}^{a_{k+1}}$. This works and we are done. $\square$

The answer is all positive integers $n$ that cannot be expressed as $pq$ where $p$, $q$ are distinct primes. For sufficiency note that $p$ and $q$ must be adjacent in the cycle which are relatively prime. Now we will provide a construction for all other possibilities. $\textbf{Case 1:}$ $n$ is a prime power. All divisors in the cycle are divisible by some prime, so this is valid. $\textbf{Case 2:}$ $n = p^a q^b$ where $p$, $q$ are primes and $a, b \ge 1$, $\max(a, b) \ge 2$. Consider the construction $$pq \to p \to p^2 \to \dots \to p^a \to (\text{sequence of divisors divisible by } pq \text{ except } pq) \to q \to q^2 \to \dots \to q^b$$which is a valid cycle. $\textbf{Case 3:}$ $n$ has at least $3$ prime divisors. First we show for squarefree $n = p_1 p_2 \dots p_k$ where $p_i$ are primes and $k \ge 3$. We proceed with induction, the base case $k = 3$ achieved by the following cycle: $$p_1 \to p_1p_2 \to p_2 \to p_2p_3 \to p_3 \to p_1p_3 \to p_1p_2p_3$$Now assume a valid cycle exists for $k = t$. To prove for $k = t + 1$, we will insert the new divisors after $p_1p_2 \dots p_t$ in the $k = t$ cycle. We have the valid cycle $$\underbrace{a \to (\text{some valid sequence}) \to p_1 p_2 \dots p_t \to p_1 p_2 \dots p_{t + 1}}_{\text{cycle for } k = t} \to (\text{any sequence of divisors divisible by } p_{t + 1})$$where the last sequence ends in $ap_{t + 1}$. Now clearly if a cycle exists for $n = p_1 p_2 \dots p_k$ we can extend it to all $n = p_1^{e_1} p_2^{e_2} \dots p_k^{e_k}$ for $e_i \ge 1$ as we can simply bunch divisors with the same set of prime factors. We have exhausted all other cases, and our proof is complete.