A property of divisors

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

A property of divisors

G H J

Reveal topic tags

national olympiad

L

G H BBookmark kLocked kLocked NReply

Source: Kazakhstan NMO 2016, P1

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

868 posts

#1 h Mar 17, 2016, 9:48 AM • 3 Y

Y by Adventure10, Mango247, ItsBesi

Prove that one can arrange all positive divisors of any given positive integer around a circle so that for any two neighboring numbers one is divisible by another.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

652 posts

#2 h Mar 17, 2016, 10:15 AM • 2 Y

Y by Adventure10, Mango247

This problem is quite old. For instance, a special case can be found in the Ireland Team Training materials.
So I come to a solution.
This result trivially holds if the number, $n$ , is a prime power, so assume otherwise. Now let $n =ap$ where $a,p$ are positive integers and $p$ is prime. We induct, assuming this result to be true for $a.$ Create the circle for $a$ and call it $\mathcal{C}.$ Further, by $k\mathcal{C}$ we denote the circle obtained by multiplying each entry of $\mathcal{C}$ by $k.$ Then, consider the two circles $\mathcal{C}$ and $p\mathcal{C}.$ Let $a,b$ be two successive entries in $\mathcal{C}.$ Then cut $\mathcal{C}$ in between $a,b$ and $p\mathcal{C}$ between $pa,pb.$ Now attach the two figures obtained so that $pa$ is joined to $a$ and $b$ is joined to $pb.$ Clearly this arrangement suffices by induction.
We can choose the base case as any prime power, for which any arrangement holds. By induction, this result holds for all $n \in \mathbb{N}.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1329 posts

#3 h May 29, 2024, 5:17 PM • 1 Y

Y by sami1618

OTIS stronger version wrote:

Let $n\geq 2$ be a positive integer.
Prove that all divisors of $n$ can be written as a sequence $d_1,\dots,d_k$ such that
for any $1\leq i<k$ one of $\frac{d_i}{d_{i+1}}$ and $\frac{d_{i+1}}{d_i}$ is a prime number.

We can show that there is a bijection between finding a sequence of divisors and finding a path(from vertex to adjacent vertex) on an lattice $n$ -dimensional hyperbox(on the coordinate plane) so that all lattice points are covered by the path. Note that vertex Here $n$ is the number of distinct prime divisors of the positive integer in question which we will call $\mathcal{P}$ . Note that our hyperbox has dimensions $(e_1 + 1) \times (e_2 + 1) \times \dots \times (e_n + 1)$ where $\mathcal{P} = \prod_i^n p_i^{e_i}$ . Note that point $(x_1, x_2, x_3, \dots, x_n)$ corresponds to $\prod_i^n x_i^{p_i}$ . WLOG our path starts at the origin on the coordinate plane which corresponds to $1$ in terms of a divisors.
We will use induction to prove this claim. Our base case of $n = 1$ is trivially true. Then we can easily induct upwards since we can connect our path between two $n-1$ hypercube graphs at the corners to form a block of $n-1$ hypercube graphs with length $e_n + 1$ , so our induction is done.

This post has been edited 2 times. Last edited by dolphinday, May 29, 2024, 7:53 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

147 posts

#4 h Aug 28, 2024, 4:38 PM

Y by

OTIS version
We will prove it by using induction.

$\textbf{Base case:}$ $n$ -has only one prime factor $\iff n=p^{\alpha}$ then we can form the sequence as follows:
$1,p,p^2, \dots , p^{\alpha}$ .

$\textbf{Inductive hypothesis:}$ Assume it's true for $n$ -having $\ell$ prime factors.

$\textbf{Inductive step:}$ Now we will prove that works for $n$ having $\ell+1$ prime factors.
$\iff n=q^{\beta} \cdot t$ where $t$ has $\ell$ prime factors and let $a_1,a_2, \dots, a_k$ be the sequence of $t$ .
So now to prove that $n=q^{\beta} \cdot t$ works we form the sequence as follows:
$a_1,a_2, \dots, a_k , q \cdot a_1, q \cdot a_2, \dots, q \cdot a_k \cdot q^2 \cdot a_1, q^2 \cdot a_2, \dots , q^2 \cdot a_k ,\cdots \cdots q^{\beta} \cdot a_1 , q^{\beta} \cdot a_2, \dots, q^{\beta} \cdot a_k.$

Hence we are done $\blacksquare$ .

This post has been edited 1 time. Last edited by ItsBesi, Oct 1, 2024, 1:01 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

balllightning37

389 posts

balllightning37

#5 h Sep 5, 2024, 2:06 PM

Y by

The Otis version:

Let the prime factorization of $n$ be $p^aq^br^c\dots$ . Now, consider a coordinate lattice from $(1,1,1,...)$ to $(a,b,c,...)$ so that we have a one-to-one correspondence from factors of $n$ to points on the lattice. Notice that the given condition means that the lattice points corresponding to two adjacent terms of the sequence are adjacent themselves.

Thus, the question is just asking if all such coordinate lattices have a Hamiltonian path. This is pretty easy induction on the dimension of the lattice.

remark

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1012 posts

#6 h Nov 11, 2024, 3:05 PM

Y by

Otis version:
Induction of the number of prime factors of n works

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

575 posts

#7 h Nov 22, 2024, 1:22 AM

Y by

We claim that there exists a sequence with either $d_1=1, d_k=n$ or $d_k=1, d_1=n.$ We show this by inducting on $\alpha,$ the number of prime factors that $n$ has.

The base case is trivial. Now, suppose that our proposition holds for $\alpha=\ell$ for some positive integer $\ell.$ Then suppose $n$ has $\ell+1$ prime factors. Let $p$ be a prime factor of $n$ such that $v_p(n)=x.$ Also, let $n=p^xm.$ Then by our inductive hypothesis, there exists a sequence from $1$ to $m.$ Then, we can move to $mp,$ and using our inductive hypothesis again we can get to $p.$ Continuing, we will eventually end at either $p^x$ or $mp^x=n.$ (Visualize this as a path through lattice points in a $\ell$ -dimensional space.) Hence, this provides a valid path, so we are done. QED

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

362 posts

#8 h Mar 14, 2025, 5:50 PM

Y by

OTIS wrote:

Let $n\geq 2$ be a positive integer. Prove that all divisors of $n$ can be written as a sequence $d_1,\dots,d_k$ such that for any $1\leq i<k$ one of $\frac{d_i}{d_{i+1}}$ and $\frac{d_{i+1}}{d_i}$ is a prime number.

For a sequence $S$ let $S^{*}$ be the reverse of $S$ and $m \times S$ for a number $m$ as the sequence $S$ when corresponding elements are multiplied by $m$ .

Now suppose $n$ has $\ell$ distinct prime factors, we induct on $\ell$ . For the base case of $\ell = 1$ , let $n = p^a$ where $p$ is prime. The sequence $1, p, p^2, \dots, p_a$ clearly works. Now assume that the claim holds for an arbitrary $\ell \ge 1$ . Then consider the prime factorization $n = p_1^{e_1} p_2^{e_2} \dots p_{\ell + 1}^{e_{\ell + 1}}$ . By the inductive hypothesis, there exists some sequence of divisors $T$ of $p_1^{e_1} p_2^{e_2} \dots p_{\ell}^{e_{\ell}}$ that satisfies the conditions of the problem. Then the composite sequence
$T, p_{\ell + 1} \times T^{*}, p_{\ell + 1}^2 \times T, p_{\ell + 1}^3 \times T^{*} \dots$ works, so our induction is complete. We are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

203 posts

#9 h Mar 23, 2025, 6:45 PM

Y by

We will induct on the number of prime factors of $n$ . If $n$ has $m=1$ prime factors then clearly the sequence
$1,p,p^2,\ldots,p^{e}$ works.

Then let us assume that this works $m=l$ . Consider $m=l+1$ , so $n=p_1^{e_1}p_2^{e_2}\cdots p_{l+1}^{e_{l+1}}$ . We will divide the sequence into $e_{l+1}+1$ blocks of length $(e_1+1)\cdots(e_l+1)$ . For the first block we will use the good construction for $m=l$ , $1, \ldots , p_1^{e_1}\cdots p_l^{e_l}$ For the second block we will flip this sequence and multiply each term by $p_{l+1}$ ,

$p_1^{e_1}\cdots p_l^{e_l} p_{l+1}, \ldots , p_{l+1}$
For the third block we will flip this sequence again and multiply each term by $p_{l+1}$ ,

$p_{l+1}^2, \ldots, p_1^{e_1}\cdots p_l^{e_l} p_{l+1}^2$ and we can easily verify that we get a satisfactory construction following this method. Thus by induction we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

648 posts

#10 h Mar 28, 2025, 3:44 PM

Y by

Proceed with induction on the number of distinct primes that divide $n$ . When exactly one prime divides $n$ , we can write out the divisors as follows: $1, p, p^2, \dots, p^{k-1}$ .

Now, let the prime factorization of $n$ be $p_1^{e_1}p_2^{e_2}\dots p_i^{e_i}$ . Let $m=p_1^{e_1}p_2^{e_2}\dots p_{i-1}^{e_{i-1}}$ , so $n=mp_i^{e_i}$ . We are clearly able to write a sequence starting with $mp_i^{e_i}$ and ending with $dp_i^{e_i}$ where $d\mid m$ by induction (this sequence covers all divisors of $n$ with $\nu_{p_i}(n)=e_i$ ). Then, we write $dp_i^{e_{i-1}}$ and (by induction) ``build back up" to $mp_i^{e_i-1}$ (this covers all divisors of $n$ with $\nu_{p_i}=e_i-1$ ). Then, we write $mp_i^{e_i-2}$ and build down to $dp_i^{e_i-2}$ , covering all divisors of $n$ with $\nu_{p_i}=e_i-2$ . We can continue this ``building up" and ``building down" process until we cover all divisors of $n$ , completing our induction. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1801 posts

akliu

#11 h Apr 2, 2025, 6:26 PM

Y by

I actually solved this question fairly quickly because it relates to a question from a math camp's application that I did this year. Consider a single prime $p_1$ , and list out the sequence as follows: $1$ , $p_1$ , $p_1^2$ , $\dots$ , $p_1^{\nu_{p_1}(n)}$ . For each value $k$ in the sequence, replace the number with another sequence $k$ , $kp_2$ , $kp_2^2$ , $\dots$ , $kp_2^{\nu_{p_2}(n)}$ , and alternate this between values of $k$ such that adjacent values are multiplied by the same sequence in either increasing or decreasing order. For example, for $n = 18$ , we start out with the sequence $1$ , $2$ . Then, we include the prime $3$ , and we get $1$ , $3$ , $9$ , $18$ , $6$ , $2$ . Do this for all primes, and we have a sequence that goes over all the divisors of $n$ where each step is either dividing or multiplying by a prime number; the sequence is split into groups of varying values of $\nu_p$ , and each of those gorups has groups of varying values of $\nu_q$ , and so on throughout all desired primes.

An example for $3$ primes for the reader's clarity: $n = 60$ turns into $1$ , $2$ , $4$ . We alternate the sequences of the powers of $3$ , and arrive at $1, 3$ , $6, 2$ , $4, 12$ . Finally, adding the sequences of $5$ , we get the final sequence: $1, 5, 15, 3, 6, 30, 10, 2, 4, 20, 60, 12$ .

A short bonus: It is possible to loop the sequence back to $1$ if and only if $n$ is not a perfect square, or a perfect power of a prime. In particular, the example with $n = p^aq^b$ can be drawn as a grid as such:
$\begin{align*} 1, p, p^2, \dots\\ q, pq, p^2q, \dots\\ \dots \\ q^b, q^bp, q^bp^2,\dots \end{align*}$
Finding a "prime dividing path" on this grid such that the path covers all the numbers on the grid bijects to trying to find a Hamiltonian cycle through a rectangular grid of dimensions $(a+1)(b+1)$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

249 posts

#12 h Apr 11, 2025, 3:15 AM • 2 Y

Y by akliu, centslordm

Induct on the number of distinct prime factors $k$ of $n$ . The base case $k=1$ or $n=p_1^{e_1}$ for primes $p_1$ works with the sequence $\overset\rightarrow{X_1}=\{1,p_1,p_1^2,\dots,p_1^{e_1}\}$ .

Let $\overset\leftarrow{X_k}$ be the sequence $\overset\rightarrow{X_k}$ with all elements in the opposite order. If $A\oplus B$ concatenates sequences $A$ and $B$ , it then follows that
$\overset\rightarrow{X_{k+1}}=\overset\rightarrow{X_k}\oplus(p_{k+1}\cdot\overset\leftarrow{X_k})\oplus(p_{k+1}^2\cdot\overset\rightarrow{X_k})\oplus(p_{k+1}^3\cdot\overset\leftarrow{X_k})\dots$ is a sequence satisfying the problem statement, which completes the inductive step.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1801 posts

akliu

#13 h Apr 11, 2025, 3:34 AM

Y by

Nice formalization! I didn't think about writing it that way.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

672 posts

#14 h Apr 25, 2025, 7:42 AM

Y by

Notice that all powers of primes work, and 1 work. Also notice that any number that is of the form $pq$ work, where $p, q$ are primes, because of the sequence $1, p, pq, q.$

Let $k$ be the number of primes dividing $n.$ Assume that $n\geq 2.$ I claim that there exists a sequence satisfying the problem such that the first element is 1, and the last element is the product of at most $k - 1$ primes. We prove this with induction on number of divisors. The idea is:

Now, assume that for $n < k,$ our statement is true. We will prove that $n = k$ works. If $k$ is prime, we have $1, k$ works. If $k$ isn't prime, let a prime dividing $k$ be $p.$ Let the sequence of $\frac{k}{p}$ be $a = \{1, s_2, s_3, \ldots, s_a\}.$ Let the sequence of $\frac{k}{p^{\nu_p(k)}}$ be $b = \{1, s_2', \ldots, s_{\frac{k}{p^{\nu_p(k)}}}'\}.$ We know these both exist since our hypothesis. I claim that $\{1, s_2p, s_3p, \ldots, s_a p, \frac{k}{p^{\nu_p(k)}s_1'}, \ldots\}$ works.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a