Special Highly Composite Number/Examples/60

From ProofWiki
Jump to navigation Jump to search

Example of Special Highly Composite Number

$60$ 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, $60$ is highly composite.


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

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

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

As $60$ is not a divisor of $n$, it follows that while $3$ is a divisor of $n$, $5$ is not.

From Prime Decomposition of Highly Composite Number, no prime number greater than $5$ is a divisor of $n$.

Thus:

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

where $a \ge b \ge 1$.

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


$(1): \quad b = 1$

That is, $n = 2^a \times 3$.


We have that $n > 60$.

Therefore:

$(1 \text a): \quad a \ge 5$

as $2^4 \times 3^1 = 48$.


Then:

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


It follows by Proof by Contradiction that $b \ne 1$.

$\Box$


$(2): \quad b = 2$

That is, $n = 2^a \times 3^2$.


We have that $n > 60$.

Therefore:

$(2 \text a): \quad a \ge 3$

as $2^2 \times 3^2 = 36$.


Then:

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


It follows by Proof by Contradiction that $b \ne 2$.

$\Box$


$(3): \quad b \ge 3$

By Prime Decomposition of Highly Composite Number we have that $a \ge 3$.


Then:

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

$\Box$


By Proof by Cases it is seen that the existence of a highly composite $n$ not divisible by $60$ 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/60&oldid=624033"