Problem 1593

We say that a positive integer is good if it has the given property. Let $n$ be a good number, and let $d_{1}, d_{2}, \ldots, d_{k}$ be the divisors of $n$ in the circle, in that order. Then for all $1 \leq i \leq k, d_{i+1} / d_{i}$ (taking the indices modulo $k$) is equal to either $p_{i}$ or $1 / p_{i}$ for some prime $p_{i}$. In other words, $d_{i+1} / d_{i} = p_{i}^{\epsilon_{i}}$, where $\epsilon_{i} \in \{1, -1\}$. Then

$$p_{1}^{\epsilon_{1}} p_{2}^{\epsilon_{2}} \cdots p_{k}^{\epsilon_{k}} = \frac{d_{2}}{d_{1}} \cdot \frac{d_{3}}{d_{2}} \cdots \frac{d_{1}}{d_{k}} = 1$$

For the product $p_{1}^{\epsilon_{1}} p_{2}^{\epsilon_{2}} \cdots p_{k}^{\epsilon_{k}}$ to equal 1, any prime factor $p$ must be paired with a factor of $1 / p$, and vice versa, so $k$ (the number of divisors of $n$) must be even. Hence, $n$ cannot be a perfect square.

Furthermore, $n$ cannot be the power of a prime (including a prime itself), because 1 always is a divisor of $n$, and if $n$ is a power of a prime, then the only divisor that can go next to 1 is the prime itself.

Now, let $n = p^{a} q^{b}$, where $p$ and $q$ are distinct primes, and $a$ is odd. We write the divisors of $n$ in a grid as follows: In the first row, write the numbers $1, q, q^{2}, \ldots, q^{b}$. In the next row, write the numbers $p, p q, p q^{2}, \ldots, p q^{b}$, and so on. The number of rows in the grid, $a+1$, is even. Note that if two squares are adjacent vertically or horizontally, then their corresponding numbers are prime-related. We start with the square with a 1 in the upper-left corner. We then move right along the first row, move down along the last column, move left along the last row, then zig-zag row by row, passing through every square, until we land on the square with a $p$. The following diagram gives the path for $a=3$ and $b=5$:

!

Thus, we can write the divisors encountered on this path in a circle, so $n = p^{a} q^{b}$ is good.

Next, assume that $n$ is a good number. Let $d_{1}, d_{2}, \ldots, d_{k}$ be the divisors of $n$ in the circle, in that order. Let $p$ be a prime that does not divide $n$. We claim that $n \cdot p^{e}$ is also a good number. We arrange the divisors of $n \cdot p^{e}$ that are not divisors of $n$ in a grid as follows:

$$\begin{array}{cccc} d_{1} p & d_{1} p^{2} & \ldots & d_{1} p^{e} \\ d_{2} p & d_{2} p^{2} & \ldots & d_{2} p^{e} \\ \vdots & \vdots & \ddots & \vdots \\ d_{k} p & d_{k} p^{2} & \ldots & d_{k} p^{e} \end{array}$$

Note that if two squares are adjacent vertically or horizontally, then their corresponding numbers are prime-related. Also, $k$ (the number of rows) is the number of factors of $n$, which must be even (since $n$ is good). Hence, we can use the same path described above, which starts at $d_{1} p$ and ends at $d_{2} p$. Since $d_{1}$ and $d_{2}$ are adjacent divisors in the circle for $n$, we can insert all the divisors in the grid above between $d_{1}$ and $d_{2}$, to obtain a circle for $n \cdot p^{e}$.

Finally, let $n$ be a positive integer that is neither a perfect square nor a power of a prime. Let the prime factorization of $n$ be

$$n = p_{1}^{e_{1}} p_{2}^{e_{2}} \cdots p_{t}^{e_{t}}$$

Since $n$ is not the power of a prime, $t \geq 2$. Also, since $n$ is not a perfect square, at least one exponent $e_{i}$ is odd. Without loss of generality, assume that $e_{1}$ is odd. Then from our work above, $p_{1}^{e_{1}} p_{2}^{e_{2}}$ is good, so $p_{1}^{e_{1}} p_{2}^{e_{2}} p_{3}^{e_{3}}$ is good, and so on, until $n = p_{1}^{e_{1}} p_{2}^{e_{2}} \cdots p_{t}^{e_{t}}$ is good.

Therefore, a positive integer $n$ has the given property if and only if it is neither a perfect square nor a power of a prime.

To solve the problem, we need to find all positive integers $n$ such that $n$ has at least three divisors, and all the divisors can be arranged in a circle so that any two adjacent divisors are prime-related.

1. Prime Power Case:
- If $n$ is a prime power, say $n = p^k$ where $p$ is a prime and $k \geq 1$, then the divisors of $n$ are $1, p, p^2, \ldots, p^k$.
- For $n$ to have at least three divisors, $k \geq 2$.
- However, in this case, $1$ and $p$ must be adjacent, and $p$ and $p^2$ must be adjacent. But $1$ and $p^2$ are not prime-related, so $n$ cannot be a prime power.

2. Perfect Square Case:
- If $n$ is a perfect square, say $n = m^2$, then $n$ has an odd number of divisors.
- Consider the sum of the exponents of the primes in the prime factorization of a number. Each move (from one divisor to the next) changes the parity of this sum.
- Starting from $1$ and ending at $1$ after an odd number of moves implies that the parity of the sum of the exponents changes an odd number of times, which is a contradiction.
- Therefore, $n$ cannot be a perfect square.

3. General Case:
- We claim that integers $n$ with at least three prime factors work.
- Consider $n = p^a q^b$ where $p$ and $q$ are primes and $a, b \geq 1$.
- Assume $b$ is odd. We can construct a sequence of divisors as follows:
$$1, q, pq, p^2q, \ldots, p^{a-1}q, q^2p^{a-1}, q^2p^{a-2}, \ldots, pq^2, q^2, q^3, q^3p, \ldots, q^b, q^bp, q^bp^2, \ldots, q^bp^{a-1}$$
- This sequence maintains the condition that any two adjacent divisors are prime-related.
- The remaining divisors are of the form $p^i$ and $p^a q^j$ for $1 \leq j \leq b$. We attach the following string:
$$p^a q^b, p^a q^{b-1}, \ldots, p^a q, p^a, p^{a-1}, p^{a-2}, \ldots, p$$
- This construction works for $n = p^a q^b$.

4. Inductive Step:
- Assume that for $n = \prod_{i=1}^{k-1} p_i^{a_i}$, there is a valid construction.
- For $n' = \prod_{i=1}^{k+1} p_i^{a_i}$, consider the sequence:
$$b_1, b_2, \ldots, b_l, p b_l, p, b_{l-1}, \ldots, p b_3, p b_2, p^2 b_2, p^2 b_3, \ldots, p^2 b_l, \ldots$$
- If $a_{k+1}$ is even, the sequence ends with $p^{a_{k+1}} b_l$. If $a_{k+1}$ is odd, it ends with $p^{a_{k+1}} b_2$.
- Add the following string:
$$p^{a_{k+1}} b_1, p^{a_{k+1}-1} b_1, \ldots, p^2 b_1, p b_1$$
- This construction works, and every number which is not a square or a prime power works.

$\blacksquare$

The final answer is all positive integers $\boxed{ n }$ that are not prime powers or perfect squares.