# If no composite divisor of a positive integer $n$ divides any other composite divisor of $n$ can $n$ have more than three such divisors?

I wrote a program that finds the sequence of such integers and was surprised to find that is https://oeis.org/A217856 (Numbers with three prime factors, not necessarily distinct, except cubes of primes.) I imagined that as $$n$$ grew larger the number of such composite divisors would slowly grow, but this appears not to be the case. I have checked up to n=500000.

For example, 12 is the first number in the sequence because the divisors of 12 are 2,3,4 and 6. Now ignore the prime divisors and examine the composites that remain, 4 and 6. 4 does not divide 6, so 12 is in the sequence.

Why can't a number with more prime divisors have more such composite divisors?

• If a number has three prime factors, it has at most eight total divisors at all. – Elliot G Sep 2 '19 at 18:29
• Maybe I'm misunderstanding the question. Is $n$ any number such that there is no prime factor which appears three times? – Elliot G Sep 2 '19 at 18:30
• @Elliot G Does the example I added help? In the case of 12, 2*2*3 are the three primes. – jnthn Sep 2 '19 at 18:39
• So are you only considering number of the form $p_1p_2p_3$ or $p_1^2p_2$ for distinct primes $p_1,p_2,p_3$? – Elliot G Sep 2 '19 at 18:41
• If for (not necessarily distinct) primes $p_1,\ldots,p_4$ the product $p_1p_2p_3p_4$ divides $n$ then $p_1p_2$ and $p_1p_2p_3$ are composite divisors of $n$ and $p_1p_2 \mid p_1p_2p_3$. – WimC Sep 2 '19 at 18:43

## 2 Answers

Suppose $$n$$ has at least four prime factors. Then there are primes $$p,q,r,s$$ (not necessarily distinct) such that $$pqrs$$ is a divisor of $$n$$. Then $$pq$$ is a proper composite divisor of $$n$$, and so is $$pqr$$. Moreover, $$pq$$ divides $$pqr$$.

That is, if $$n$$ has at least four prime factors, we can always find two composite proper divisors of $$n$$ such that one is a multiple of the other. In other words, if we cannot find two such divisors, then $$n$$ can have at most three prime factors.

On the other hand, if $$n$$ has fewer than three prime factors, then $$n$$ has no proper composite divisors. So the condition you've given implies that $$n$$ has exactly three prime factors.

If $$n=pqr$$ where $$p,q,r$$ are prime, and $$p \ne q$$, then the numbers $$pr$$ and $$qr$$ are distinct composite proper divisors and not multiples of each other. But the only other possibility is that $$n=p^3$$, in which case $$n$$ has only the single proper composite divisor $$p^2$$.

So, if $$n$$ satisfies the following conditions:

• $$n$$ has at least two distinct composite proper divisors
• No two composite proper divisors of $$n$$ are multiples of each other.

then $$n$$ is the product of exactly three prime factors, and is not the cube of a prime. Conversely, any product of three prime factors which is not the cube of a prime has these properties.

If I understand you correctly, then it should easily be possible to construct such a number. But it's quite possible such a number is bigger than 500.000. A relatively small example is given by $$n = d_0 \cdot d_1 \cdot d_2 \cdot d_3$$ where

\begin{align} d_0 &= 3 \cdot 5 = 15 \\ d_1 &= 5 \cdot 7 = 35 \\ d_2 &= 7 \cdot 13 = 91 \\ d_3 &= 13 \cdot 17 = 221 \\ \end{align}

In other words, $$n = 10.558.275$$. You can easily extend the construction to an arbitrary number of divisors.

• Divisors of number 10558275: 1, 3, 5, 7, 13, 15, 17, 21, 25, 35, 39, 49, 51, 65, 75, 85, 91, 105, 119, 147, 169, 175, 195, 221, 245, 255, 273, 325, 357, 425, 455, 507, 525, 595, 637, 663, 735, 833, 845, 975, 1105, 1183, 1225, 1275,..., and 15 divides 75, among others. – jnthn Sep 2 '19 at 18:33