Maths Olympiad Prep

Library / /20 of 32

Number theory Difficulty 6.5 National Olympiad Prove it Belarus

Prove that all divisors of any positive integer can be arranged in the circle such that for any two consecutive divisors one would divide another.
(Mikhail Karpuk)

Solution

Let's prove this statement by induction on the number of distinct prime divisors of a given number. In this case, this number will be denoted by nn, the number of its divisors — by d(n)d(n) and the divisors written in counterclockwise order — by a1,a2,,ad(n)a_1, a_2, \dots, a_{d(n)}, where a1=1a_1 = 1.

Base: let n=pkn = p^k, where pp is a prime number. Let's arrange all divisors of the number nn in ascending order: a1=1,a2=p,,ak+1=pka_1 = 1, a_2 = p, \dots, a_{k+1} = p^k. It is obvious that such arrangement satisfies the condition.

Step: suppose the assertion is proved for all numbers having at most ss different prime divisors, let us prove it for an arbitrary number nn having s+1s + 1 prime divisors. We write nn as n=pkmn = p^k m, where pp is a prime number that does not divide mm.

If \ell is a sequence of numbers written in a clockwise circle then by \ell^* we will denote the same sequence but written in reverse order, i. e., if \ell is a1,a2,,aka_1, a_2, \dots, a_k, then \ell^* is ak,,a2,a1a_k, \dots, a_2, a_1. Moreover by qq\ell we denote the sequence obtained from \ell by multiplying all its terms by qq, i. e. qq\ell is qa1,qa2,,qakqa_1, qa_2, \dots, qa_k.

By the induction hypothesis all divisors of the number mm can be arranged in a circle according to the condition: a1,a2,,ad(m)a_1, a_2, \dots, a_{d(m)}. Denote this sequence \ell. Then we arrange the divisors of the number nn around the circle in the following order:

,(p),p2,,(pk1),pk\ell, (p\ell)^*, p^2\ell, \dots, (p^{k-1}\ell)^*, p^k\ell, if kk is odd,
and
,(p),p2,,pk1,(pk)\ell, (p\ell)^*, p^2\ell, \dots, p^{k-1}\ell, (p^k\ell)^*, if kk is even.

It is easy to see that these sequences satisfy the condition of the problem.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.