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.

1318 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.

136 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

382 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.

936 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.

510 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.

314 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.

185 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

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a