Maths Olympiad Prep

Library / /46 of 115

Number theory Difficulty 7.2 National olympiad, round 2 Find the answer

( Zuming Feng ) Determine all composite positive integers nn for which it is possible to arrange all divisors of nn that are greater than 1 in a circle so that no two adjacent divisors are relatively prime.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Solution 1 (official solution)
No such circular arrangement exists for n=pqn=pq , where pp and qq are distinct primes. In that case, the numbers to be arranged are pp ; qq and pqpq , and in any circular arrangement, pp and qq will be adjacent. We claim that the desired circular arrangement exists in all other cases. If n=pen=p^e where e2e\ge2 , an arbitrary circular arrangement works. Henceforth we assume that nn has prime factorization p1e1p2e2pkekp^{e_1}_{1}p^{e_2}_{2}\cdots p^{e_k}_k , where p1<p2<<pkp_1<p_2<\cdots<p_k and either k>2k>2 or else max(e1,e2)>1\max(e1,e2)>1 . To construct the desired circular arrangement of Dn:={d:dn and d>1}D_n:=\lbrace d:d|n\ \text{and}\ d>1\rbrace , start with the circular arrangement of n,p1p2,p2p3,pk1pkn,p_{1}p_{2},p_{2}p_{3}\ldots,p_{k-1}p_{k} as shown.

Then between nn and p1p2p_{1}p_{2} , place (in arbitrary order) all other members of DnD_n that have p1p_1 as their smallest prime factor. Between p1p2p_{1}p_{2} and p2p3p_{2}p_{3} , place all members of DnD_n other than p2p3p_{2}p_{3} that have p2p_2 as their smallest prime factor. Continue in this way, ending by placing pk,pk2,,pkekp_k,p^{2}_{k},\ldots,p^{e_k}_{k} between pk1pkp_{k-1}p_k and nn . It is easy to see that each element of DnD_n 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 DnD_n 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 n=p2qn=p^{2}q and n=pqrn=pqr .

Solution 2
The proof that no arrangement exists for n=pqn=pq , where p,qp,q 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
p,pq,pr,r,qr,q,pqrp,pq,pr,r,qr,q,pqr Inductive step: Suppose the desired arrangement exists for a composite nn , show the arrangement exists for nprnp^r , where pp is a prime relatively prime to nn and rr is a positive integer
Let a1,a2,,ama_1,a_2,\cdots,a_m be the arrangement of divisors of nn , then (ai,ai+1)>1(a_i,a_{i+1})>1 for i=1,2,,mi=1,2,\cdots,m , where am+1=a1a_{m+1}=a_1 . The divisors of nprnp^r greater than 1 are of the form aipj,pj1im,1jra_ip^j,p^j\qquad 1\leq i\leq m,1\leq j\leq r The following sequence works a1,,am1,am1p,other divisors in arbitrary order,amp,ama_1,\cdots,a_{m-1}, a_{m-1}p,\text{other divisors in arbitrary order},a_mp,a_m since all other divisors are divisible by pp .
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.