( Zuming Feng ) Determine all composite positive integers for which it is possible to arrange all divisors of that are greater than 1 in a circle so that no two adjacent divisors are relatively prime.
Solution
Solution 1 (official solution)
No such circular arrangement exists for , where and are distinct primes. In that case, the numbers to be arranged are ; and , and in any circular arrangement, and will be adjacent. We claim that the desired circular arrangement exists in all other cases. If where , an arbitrary circular arrangement works. Henceforth we assume that has prime factorization , where and either or else . To construct the desired circular arrangement of , start with the circular arrangement of as shown.
Then between and , place (in arbitrary order) all other members of that have as their smallest prime factor. Between and , place all members of other than that have as their smallest prime factor. Continue in this way, ending by placing between and . It is easy to see that each element of is placed exactly one time, and any two adjacent elements have a common prime factor. Hence this arrangement has the desired property.
Note. In graph theory terms, this construction yields a Hamiltonian cycle in the graph with vertex set in which two vertices form an edge if the two corresponding numbers have a common prime factor. The graphs below illustrate the construction for the special cases and .
Solution 2
The proof that no arrangement exists for , where are distinct primes follows from above. Apply induction to prove all other cases are possible
Base case:
, where is a prime and is a positive integer. Any arrangement suffices , where are distinct primes. The following configuration works
Inductive step: Suppose the desired arrangement exists for a composite , show the arrangement exists for , where is a prime relatively prime to and is a positive integer
Let be the arrangement of divisors of , then for , where . The divisors of greater than 1 are of the form The following sequence works since all other divisors are divisible by .
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.