Selected Problems from Open Contests

a) Considering the numbers from 1 to 20 we see that exactly three of them have 6 divisors: 12 (the divisors are 1, 2, 3, 4, 6, 12), 18 (1, 2, 3, 6, 9, 18), and 20 (1, 2, 4, 5, 10, 20). For 12 the sum $d_4+d_5=4+6$ is divisible by the sum $d_2+d_3=2+3$ and similarly, for 18 the sum $d_4+d_5=6+9$ is divisible by $d_2+d_3=2+3$. However, for 20 the sum $d_4+d_5=5+10$ is not divisible by the sum $d_2+d_3=2+4$. Thus, the smallest non-good number with exactly 6 factors is 20.

b) Take $N=4p$, where $p$ is an arbitrary prime number larger than 4. Then $N$ has exactly 6 different divisors: 1, 2, 4, $p$, $2p$, $4p$, in increasing order. Indeed, as $N=2^2{p}^1$, where 2 and $p$ are two different prime numbers, all of its divisors can be expressed as $2^i{p}^j$ where $i\le 2$ and $j\le 1$. From here we obtain exactly $3\cdot 2=6$ choices: $i$ can be either 0, 1 or 2 and for every $i$ we have two choices for $j$: 0 or 1. Here, $d_4+d_5=p+2p=3p$ is odd because $p>2$ and thus is not divisible by an even number $d_2+d_3=2+4=6$. Therefore, none of the numbers expressed as $N=4p$ where $p>4$ is a prime is good. As there are infinitely many prime numbers, there must also be infinitely many such numbers $N$.

---

Alternative solution.

Let us find all $N>1$ which have exactly 6 divisors.

1) If $N=p^k$, where $p$ is a prime, then it has the divisors 1, $p$, ..., $p^k$, i.e. $k+1$ divisors overall. Thus, all $N=p^5$ satisfy this requirement.

2) Let $N$ have two different prime divisors, i.e. $N=p^k{q}^l$. For $k\ge 2$ and $l\ge 2$ we see that $N$ has at least 9 different divisors: 1, $p$, $p^2$, $q$, $q^2$, $pq$, $p^{2}q$, $p{q}^2$, and $p^2{q}^2$. For $l=1$, $N$ has the divisors 1, $p$, ..., $p^k$, and $q$, $pq$, ..., $p^{k}q$, i.e. $2(k+1)$ divisors in total. Thus, all $N=p^{2}q$ satisfy the requirement.

3) Let $N$ have at least three prime divisors $p$, $q$, $r$. Then $N$ has at least 8 different divisors: 1, $p$, $q$, $r$, $pq$, $pr$, $qr$, and $pqr$, and we get no more numbers.

Let us now consider $N=p^5$ and $N=p^{2}q$ in more detail.

i) If $N=p^5$, then $d_i=p^{i-1}$ and $d_4+d_5=p^3+p^4=p^3(1+p)$ is divisible by $d_2+d_3=p+p^2=p(1+p)$. Thus they are all good.

ii) If $N=p^{2}q$, where $q<p$, then $N$ has the divisors $1,q,p,pq,p^2$, and $p^{2}q$, in increasing order, and $d_4+d_5=pq+p^2=p(q+p)$ is divisible by $d_2+d_3=q+p$ and thus, they are all good, too.

iii) If $N=p^{2}q$, where $p<q<p^2$, then $N$ has the divisors $1,p,q,p^2,pq$, and $p^{2}q$, in increasing order, and $d_4+d_5=p^2+pq=p(p+q)$ is divisible by $d_2+d_3=p+q$. Thus, they are all good, too.

iv) Finally, let $N=p^{2}q$, where $q>p^2$. Then $N$ has the divisors $1,p,p^2,q,pq$, and $p^{2}q$, in increasing order and $d_4+d_5=q+pq=q(1+p)$ is not divisible by $d_2+d_3=p+p^2=p(1+p)$ because the prime number $q$ cannot be divisible by another prime number $p$. Thus all these numbers have exactly 6 different divisors and they all are non-good. To get the smallest of these numbers, we have to take $p$ and $q$ as small as possible, i.e. $p=2$ and $q=5$ (to achieve $q>p^2=4$). Then $N=2^2\cdot 5=20$. Finally, there are infinitely many of these numbers $N$ because we have infinitely many choices for prime numbers $p$ and $q$ such that $q>p^2$. For example, we can take $p=2$ and $q$ an arbitrary prime number bigger than 5. As there are infinitely many prime numbers, we have proven the statement.