Special Highly Composite Number/Examples/2520

From ProofWiki
Jump to navigation Jump to search

Example of Special Highly Composite Number

$2520$ is a special highly composite number, being a highly composite number which is a divisor of all larger highly composite numbers.


Proof

By inspection of the sequence of highly composite numbers, $2520$ is highly composite.

For reference, the prime decomposition of $2520$ is:

$2520 = 2^3 \times 3^2 \times 5 \times 7$


Aiming for a contradiction, suppose $n > 2520$ is a highly composite number which is not divisible by $2520$.

We have that $60$ is a special highly composite number.

Therefore $60$ is a divisor of $n$.

It follows that $3$, $4$ and $5$ are all divisors of $n$.

But as $2520$ is not a divisor of $n$, it follows that at least one of $7$, $8$ and $9$ is not a divisor of $n$.


These will be investigated on a case-by-case basis.


$(1): \quad 7$ is not a divisor of $n$.


By Prime Decomposition of Highly Composite Number we have that:

$n = 2^a \times 3^b \times 5^c$

where $a \ge b \ge c \ge 1$.


Suppose that $a < 3$.

Then:

$n \le 2^2 \times 3^2 \times 5^2 = 900$

which is too small.

So we have that $a \ge 3$.


Then:

\(\ds 2^{a - 3} \times 3^b \times 5^c \times 7\) \(<\) \(\ds 2^a \times 3^b \times 5^c\) because $7 < 2^3 = 8$
\(\ds \leadsto \ \ \) \(\ds \map {\sigma_0} {2^{a - 3} \times 3^b \times 5^c \times 7}\) \(<\) \(\ds \map {\sigma_0} {2^a \times 3^b \times 5^c}\) as $2^a \times 3^b \times 5^c$ is highly composite
\(\ds \leadsto \ \ \) \(\ds \map {\sigma_0} {2^{a - 3} \times 7} \times \map {\sigma_0} {3^b \times 5^c}\) \(<\) \(\ds \map {\sigma_0} {2^a} \times \map {\sigma_0} {3^b \times 5^c}\) Divisor Count Function is Multiplicative
\(\ds \leadsto \ \ \) \(\ds \map {\sigma_0} {2^{a - 3} \times 7}\) \(<\) \(\ds \map {\sigma_0} {2^a}\) simplifying
\(\ds \leadsto \ \ \) \(\ds \paren {\paren {a - 3} + 1} \paren {1 + 1}\) \(<\) \(\ds \paren {a + 1}\) Definition of Divisor Count Function
\(\ds \leadsto \ \ \) \(\ds 2 \paren {a - 2}\) \(<\) \(\ds a + 1\)
\(\ds \leadsto \ \ \) \(\ds a\) \(<\) \(\ds 5\)


Now suppose that $b < 2$.

Then:

$n \le 2^5 \times 3 \times 5 = 480$

which is too small.

So we have that $b \ge 2$.

Then:

\(\ds 2^a \times 3^{b - 2} \times 5^c \times 7\) \(<\) \(\ds 2^a \times 3^b \times 5^c\) because $7 < 3^2 = 9$
\(\ds \leadsto \ \ \) \(\ds \map {\sigma_0} {2^a \times 3^{b - 2} \times 5^c \times 7}\) \(<\) \(\ds \map {\sigma_0} {2^a \times 3^b \times 5^c}\) as $2^a \times 3^b \times 5^c$ is highly composite
\(\ds \leadsto \ \ \) \(\ds \map {\sigma_0} {2^a \times 5^c} \times \map {\sigma_0} {3^{b - 2} \times 7}\) \(<\) \(\ds \map {\sigma_0} {2^a \times 5^c} \times \map {\sigma_0} {3^b}\) Divisor Count Function is Multiplicative
\(\ds \leadsto \ \ \) \(\ds \map {\sigma_0} {3^{b - 2} \times 7}\) \(<\) \(\ds \map {\sigma_0} {3^b}\) simplifying
\(\ds \leadsto \ \ \) \(\ds \paren {\paren {b - 2} + 1} \paren {1 + 1}\) \(<\) \(\ds \paren {b + 1}\) Definition of Divisor Count Function
\(\ds \leadsto \ \ \) \(\ds 2 \paren {b - 1}\) \(<\) \(\ds b + 1\)
\(\ds \leadsto \ \ \) \(\ds b\) \(<\) \(\ds 3\)


But $c \le b$ and so $c < 3$ as well.


Thus we have upper bounds on $a$, $b$ and $c$.

Since $2^a \times 3^b \times 5^c > 2520$, it must be the case that:

$n = 2^4 \times 3^2 \times 5^2$

which gives that $n = 3600$.


But:

from $\sigma_0$ of $3600$ we have that $\map {\sigma_0} {3600} = 45$
from $\sigma_0$ of $2520$ we have that $\map {\sigma_0} {2520} = 48$


This contradicts our hypothesis that $3600$ is highly composite.

By Proof by Contradiction it follows that $7$ must be a divisor of $n$.

$\Box$


$(2): \quad 9$ is not a divisor of $n$, but $7$ is.


By Prime Decomposition of Highly Composite Number we have that:

$n = 2^a \times 3^1 \times 5^1 \times 7^1 \times 11^e \times r$

where:

$e$ is either $0$ or $1$
$r$ is a possibly vacuous square-free product of prime numbers strictly greater than $11$.


Suppose $e = 1$.

Then:

\(\ds 2^a \times 3^3 \times 5 \times 7 \times r\) \(<\) \(\ds 2^a \times 3 \times 5 \times 7 \times 11 \times r\) because $9 = 3^2 < 11$
\(\ds \leadsto \ \ \) \(\ds \map {\sigma_0} {2^a \times 3^3 \times 5 \times 7 \times r}\) \(<\) \(\ds \map {\sigma_0} {2^a \times 3 \times 5 \times 7 \times 11 \times r}\) as $2^a \times 3 \times 5 \times 7 \times 11 \times r$ is highly composite
\(\ds \leadsto \ \ \) \(\ds \map {\sigma_0} {2^a \times 5 \times 7 \times r} \times \map {\sigma_0} {3^3}\) \(<\) \(\ds \map {\sigma_0} {2^a \times 5 \times 7 \times r} \times \map {\sigma_0} {3 \times 11}\) Divisor Count Function is Multiplicative
\(\ds \leadsto \ \ \) \(\ds \map {\sigma_0} {3^3}\) \(<\) \(\ds \map {\sigma_0} {3 \times 11}\) simplifying
\(\ds \leadsto \ \ \) \(\ds 3 + 1\) \(<\) \(\ds \paren {1 + 1} \paren {1 + 1}\) Definition of Divisor Count Function
\(\ds \leadsto \ \ \) \(\ds 4\) \(<\) \(\ds 4\) which is an absurdity

So $e = 0$ and so by Prime Decomposition of Highly Composite Number $r = 1$.


Thus:

$n = 2^a \times 3 \times 5 \times 7$

We have that $n > 2520$, so:

$(2 \text a): a \ge 5$

Then:

\(\ds 2^{a - 2} \times 3^2 \times 5 \times 7\) \(<\) \(\ds 2^a \times 3 \times 5 \times 7\) because $3 < 2^2 = 4$
\(\ds \leadsto \ \ \) \(\ds \map {\sigma_0} {2^{a - 2} \times 3^2 \times 5 \times 7}\) \(<\) \(\ds \map {\sigma_0} {2^a \times 3 \times 5 \times 7}\) as $2^a \times 3 \times 5 \times 7$ is highly composite
\(\ds \leadsto \ \ \) \(\ds \map {\sigma_0} {2^{a - 2} \times 3^2} \times \map {\sigma_0} {5 \times 7}\) \(<\) \(\ds \map {\sigma_0} {2^a \times 3} \times \map {\sigma_0} {5 \times 7}\) Divisor Count Function is Multiplicative
\(\ds \leadsto \ \ \) \(\ds \map {\sigma_0} {2^{a - 2} \times 3^2}\) \(<\) \(\ds \map {\sigma_0} {2^a \times 3}\) simplifying
\(\ds \leadsto \ \ \) \(\ds \paren {\paren {a - 2} + 1} \paren {2 + 1}\) \(<\) \(\ds \paren {a + 1} \paren {1 + 1}\) Definition of Divisor Count Function
\(\ds \leadsto \ \ \) \(\ds 3 \paren {a - 1}\) \(<\) \(\ds 2 \paren {a + 1}\) simplifying
\(\ds \leadsto \ \ \) \(\ds a\) \(<\) \(\ds 5\) which is a contradiction of $(2 \text a)$

It follows by Proof by Contradiction that $9$ is a divisor of $n$.

$\Box$


$(3): \quad 8$ is not a divisor of $n$, but $7$ and $9$ both are.


By Prime Decomposition of Highly Composite Number we have that:

$n = 2^2 \times 3^2 \times 5^c \times 7^d \times 11^e \times r$

where $r$ is a possibly vacuous product of prime numbers strictly greater than $11$.


Suppose:

$(3 \text a): \quad e > 0$

Then:

\(\ds 2^5 \times 3^2 \times 5^c \times 7^d \times 11^{e - 1} \times r\) \(<\) \(\ds 2^2 \times 3^2 \times 5^c \times 7^d \times 11^e \times r\) because $8 = 2^3 < 11$
\(\ds \leadsto \ \ \) \(\ds \map {\sigma_0} {2^5 \times 3^2 \times 5^c \times 7^d \times 11^{e - 1} \times r}\) \(<\) \(\ds \map {\sigma_0} {2^2 \times 3^2 \times 5^c \times 7^d \times 11^e \times r}\) as $2^2 \times 3^2 \times 5^c \times 7^d \times 11^e \times r$ is highly composite
\(\ds \leadsto \ \ \) \(\ds \map {\sigma_0} {2^5 \times 11^{e - 1} } \times \map {\sigma_0} {3^2 \times 5^c \times 7^d \times r}\) \(<\) \(\ds \map {\sigma_0} {2^2 \times 11^e} \times \map {\sigma_0} {3^2 \times 5^c \times 7^d \times r}\) Divisor Count Function is Multiplicative
\(\ds \leadsto \ \ \) \(\ds \map {\sigma_0} {2^5 \times 11^{e - 1} }\) \(<\) \(\ds \map {\sigma_0} {2^2 \times 11^e}\) simplifying
\(\ds \leadsto \ \ \) \(\ds \paren {5 + 1} \paren {\paren {e - 1} + 1}\) \(<\) \(\ds \paren {2 + 1} \paren {e + 1}\) Definition of Divisor Count Function
\(\ds \leadsto \ \ \) \(\ds 6 e\) \(<\) \(\ds 3 \paren {e + 1}\) simplifying
\(\ds \leadsto \ \ \) \(\ds e\) \(<\) \(\ds 1\) which is a contradiction of $(3 \text a)$

So $e = 0$ and so Prime Decomposition of Highly Composite Number $r = 1$.


Thus:

$n = 2^2 \times 3^2 \times 5^c \times 7^d$


Suppose $c = 2$.

Then:

\(\ds 2^4 \times 3^2 \times 5^1 \times 7^d\) \(<\) \(\ds 2^2 \times 3^2 \times 5^2 \times 7^d\) because $4 = 2^2 < 5$
\(\ds \leadsto \ \ \) \(\ds \map {\sigma_0} {2^4 \times 3^2 \times 5^1 \times 7^d}\) \(<\) \(\ds \map {\sigma_0} {2^2 \times 3^2 \times 5^2 \times 7^d}\) as $2^2 \times 3^2 \times 5^2 \times 7^d$ is highly composite
\(\ds \leadsto \ \ \) \(\ds \map {\sigma_0} {2^4 \times 5} \times \map {\sigma_0} {3^2 \times 7^d}\) \(<\) \(\ds \map {\sigma_0} {2^2 \times 5^2} \times \map {\sigma_0} {3^2 \times 7^d\) Divisor Count Function is Multiplicative
\(\ds \leadsto \ \ \) \(\ds \map {\sigma_0} {2^4 \times 5}\) \(<\) \(\ds \map {\sigma_0} {2^2 \times 5^2}\) simplifying
\(\ds \leadsto \ \ \) \(\ds \paren {4 + 1} \paren {1 + 1}\) \(<\) \(\ds \paren {2 + 1} \paren {2 + 1}\) Definition of Divisor Count Function
\(\ds \leadsto \ \ \) \(\ds 10\) \(<\) \(\ds 9\) which is an absurdity


The remaining possibility is that $c = 1$ and $d = 1$:

Thus:

$n = 2^2 \times 3^2 \times 5 \times 7 = 1260$

But this is a contradiction of our supposition that $n > 2520$.

It follows by Proof by Contradiction that $8$ is a divisor of $n$.

$\Box$


By Proof by Cases it is seen that the existence of a highly composite $n$ not divisible by $2520$ leads to a contradiction.


The result then follows by Proof by Contradiction.

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Special_Highly_Composite_Number/Examples/2520&oldid=623928"