4
$\begingroup$

i) Is it true that all divisors greater than 1 of any positive integer can be placed around a circle so that any two which are next to each other are never relatively prime?

ii) For which positive integers n is it possible to place all proper divisors of n (that is, all divisors of n besides n itself) around a circle so that any two which are next to each other are relatively prime?

$\endgroup$
9
  • 1
    $\begingroup$ What are your thoughts on these questions? $\endgroup$ Sep 27, 2019 at 1:39
  • $\begingroup$ I believe i) is indeed true and perhaps not too difficult to prove. I suspect there are infinitely many (and diverse) integers whose divisors cannot be placed around a circle with adjacent divisors relatively prime. Perfect powers of primes, for example. $\endgroup$ Sep 27, 2019 at 1:45
  • 1
    $\begingroup$ Right: an easy way to look at it is since $n|n$ and $n$ has to be placed on the circle, unless $n$ is prime, any pair containing $n$ and its divisor is obviously not relatively prime (e.g. the circle for the integer $24$ will contain in some order $2, 3, 4, 6, 8, 12, 24$. While it's possible to choose a pair that are relatively prime, like $(3,8)$, you will still have to pair $24$ with one of its divisors). Given this, the answer to the second question is, well, only prime numbers. $\endgroup$ Sep 27, 2019 at 1:53
  • $\begingroup$ @AndrewChin You are right! I should have said all divisors except integer itself. If I may I shall amend question. $\endgroup$ Sep 27, 2019 at 1:58
  • 3
    $\begingroup$ Why don't you run some experiments, Bernardo, and report back to us? What happens with divisors of $30$? of $210$? $\endgroup$ Sep 27, 2019 at 2:20

2 Answers 2

5
$\begingroup$

For (i) the only exception is numbers with exactly two distinct prime factors.

Let $n$ be a positive integer greater than $1$.

If $n=pq$ then it can't be done because in a circle $p$ will always be next to $q$.

If $n=p^a$ then it can be done because in this case the divisors of $n$ are all multiples of $p$ so just place them in any order around the circle.

Finally if $n=p_1^{a_1}...p_k^{a_k}$ (excluding the above cases) then it can be done like this: First place the prime factors $p_1,...,p_k$ on the circle in this order, then between $p_i$ and $p_{i+1}$ put every number in the form $p_i^jp_{i+1}$ with $a_i\ge j\ge1$ (in increasing order). After that put every multiple of $p_ip_{i+1}$ that remains between $p_i^{a_i}p_{i+1}$ and $p_ip_{i+1}$. (There will be some overlap but starting from numbers between $p_1^{a_1}p_2$ and $p_2$ you can just not add a number that already exists somewhere else).

Till now why this works? well note that with this method every number between $p_i$ and $p_{i+1}$ is a multiple of $p_ip_{i+1}$ so we're good. But we still have to deal with the $p_i^j$'s...Just put them somewhere between $p_ip_{i+1}$ and $p_i^2p_{i+1}$.

(ii) is a bit harder but I think the answer is the opposite of (i) i.e $n=pq$ are the only numbers that work (and they trivially work) furthermore powers of prime obviously don't work.

Let $n=p_1^{a_1}...p_k^{a_k}$ (excluding the above cases). If one of the exponents is $>1$ then it can't be done. Here's why: The number $r=p_1...p_k$ is going to be somewhere on the circle, but any other divisor of $n$ shares a common factor with $r$ therefore the neighbors of $r$ are $1$ and $d$ with $(d,r)>1$ hence it doesn't work.

Therefore we are left with squarefree numbers...I don't how to solve them but a few experiments shows they probably don't work and indeed I managed to solve the case $n=pqr$ like this: consider the number $pq$ it's only possible neighbors are $1$ and $r$, but $r$ is either next to $p$ or $q$ wlog assume it's $p$. Now $p$ is either next to $q$ or $qr$. If it's the latter then we are left with $pr$ and $q$ and they don't work. If it's $q$ then the next one is $pr$ and after that is $qr$ and again they don't work. Unfortunately this method is hard to generalize because the more prime factors $n$ has the more cases you have to check.

$\endgroup$
0
4
+100
$\begingroup$

PNT has already answered i).

ii)

Let $n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$ where $p_1\lt p_2\lt \cdots\lt p_k$ are prime numbers, and $a_1,a_2,\cdots, a_k$ are positive integers.

  • If $k=1$ and $a_1\leqslant 2$, then it is possible.

  • If $k=1$ and $a_1\geqslant 3$, then it is impossible since there are no two divisors which are coprime to $p_1$.

  • If $k=2$ and $(a_1,a_2)=(1,1)$, then it is possible.

  • If $k=2$ and $(a_1,a_2)\not=(1,1)$, then it is impossible since there are no two divisors which are coprime to $p_1p_2$.

  • If $k\geqslant 3$ and $(a_1,a_2,\cdots, a_k)\not=(1,1,\cdots,1)$, then it is impossible since there are no two divisors which are coprime to $p_1p_2\cdots p_k$.

  • If $k\geqslant 3$ and $(a_1,a_2,\cdots, a_k)=(1,1,\cdots,1)$, then it is impossible. The reason is as follows. The divisors which are coprime to $p_2p_3\cdots p_k$ are only $1$ and $p_1$. Also, the divisors which are coprime to $p_1p_3p_4\cdots p_k$ are only $1$ and $p_2$. So, the neighbors of $1$ have to be $p_2p_3\cdots p_k$ and $p_1p_3p_4\cdots p_k$. Then, it is impossible to place $p_1p_2\cdots p_{k-1}$ since the divisors which are coprime to $p_1p_2\cdots p_{k-1}$ are only $1$ and $p_k$.

$\endgroup$
1
  • 2
    $\begingroup$ (+1) In the case $k=3$ I had roughly the same idea (because $pq$ limits its neighbors) but I didn't thought of repeating the argument for $qr$ and $pr$ . $\endgroup$
    – PNT
    Feb 14, 2023 at 22:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .