Maths Olympiad Prep

Library / /15 of 15

Number theory Difficulty 6.8 National olympiad Prove it Estonia

Consider a positive integer NN with exactly 6 positive divisors d1,,d6d_1, \ldots, d_6 such that 1=d1<d2<d3<d4<d5<d6=N1 = d_1 < d_2 < d_3 < d_4 < d_5 < d_6 = N. Call such an integer NN good if the sum d4+d5d_4 + d_5 is divisible by the sum d2+d3d_2 + d_3.

a) Find the smallest positive integer NN which has exactly 6 positive divisors and which is not good.

b) Prove that there are infinitely many positive integers NN all with exactly 6 positive divisors and all not good.

Solutions — 2

Solution 1

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 d4+d5=4+6d_4 + d_5 = 4 + 6 is divisible by the sum d2+d3=2+3d_2 + d_3 = 2 + 3 and similarly, for 18 the sum d4+d5=6+9d_4 + d_5 = 6 + 9 is divisible by d2+d3=2+3d_2 + d_3 = 2 + 3. However, for 20 the sum d4+d5=5+10d_4 + d_5 = 5 + 10 is not divisible by the sum d2+d3=2+4d_2 + d_3 = 2 + 4. Thus, the smallest non-good number with exactly 6 factors is 20.

b) Take N=4pN = 4p, where pp is an arbitrary prime number larger than 4. Then NN has exactly 6 different divisors: 1, 2, 4, pp, 2p2p, 4p4p, in increasing order. Indeed, as N=22p1N = 2^2p^1, where 2 and pp are two different prime numbers, all of its divisors can be expressed as 2ipj2^i p^j where i2i \le 2 and j1j \le 1. From here we obtain exactly 32=63 \cdot 2 = 6 choices: ii can be either 0, 1 or 2 and for every ii we have two choices for jj: 0 or 1.
Here, d4+d5=p+2p=3pd_4 + d_5 = p + 2p = 3p is odd because p>2p > 2 and thus is not divisible by an even number d2+d3=2+4=6d_2 + d_3 = 2 + 4 = 6. Therefore, none of the numbers expressed as N=4pN = 4p where p>4p > 4 is a prime is good. As there are infinitely many prime numbers, there must also be infinitely many such numbers NN.

Solution 2

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

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

2) Let NN have two different prime divisors, i.e. N=pkqlN = p^k q^l. For k2k \ge 2 and l2l \ge 2 we see that NN has at least 9 different divisors: 1, pp, p2p^2, qq, q2q^2, pqpq, p2qp^2q, pq2pq^2, and p2q2p^2q^2. For l=1l = 1, NN has the divisors 1, pp, ..., pkp^k, and qq, pqpq, ..., pkqp^kq, i.e. 2(k+1)2(k + 1) divisors in total. Thus, all N=p2qN = p^2q satisfy the requirement.

3) Let NN have at least three prime divisors pp, qq, rr. Then NN has at least 8 different divisors: 1, pp, qq, rr, pqpq, prpr, qrqr, and pqrpqr, and we get no more numbers.

Let us now consider N=p5N = p^5 and N=p2qN = p^2q in more detail.

i) If N=p5N = p^5, then di=pi1d_i = p^{i-1} and d4+d5=p3+p4=p3(1+p)d_4 + d_5 = p^3 + p^4 = p^3(1 + p) is divisible by d2+d3=p+p2=p(1+p)d_2 + d_3 = p + p^2 = p(1 + p). Thus they are all good.

ii) If N=p2qN = p^2q, where q<pq < p, then NN has the divisors 1,q,p,pq,p21, q, p, pq, p^2, and p2qp^2q, in increasing order, and d4+d5=pq+p2=p(q+p)d_4 + d_5 = pq + p^2 = p(q + p) is divisible by d2+d3=q+pd_2 + d_3 = q + p and thus, they are all good, too.

iii) If N=p2qN = p^2q, where p<q<p2p < q < p^2, then NN has the divisors 1,p,q,p2,pq1, p, q, p^2, pq, and p2qp^2q, in increasing order, and d4+d5=p2+pq=p(p+q)d_4 + d_5 = p^2 + pq = p(p + q) is divisible by d2+d3=p+qd_2 + d_3 = p + q. Thus, they are all good, too.

iv) Finally, let N=p2qN = p^2q, where q>p2q > p^2. Then NN has the divisors 1,p,p2,q,pq1, p, p^2, q, pq, and p2qp^2q, in increasing order and d4+d5=q+pq=q(1+p)d_4 + d_5 = q + pq = q(1 + p) is not divisible by d2+d3=p+p2=p(1+p)d_2 + d_3 = p + p^2 = p(1 + p) because the prime number qq cannot be divisible by another prime number pp. 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 pp and qq as small as possible, i.e. p=2p = 2 and q=5q = 5 (to achieve q>p2=4q > p^2 = 4). Then N=225=20N = 2^2 \cdot 5 = 20. Finally, there are infinitely many of these numbers NN because we have infinitely many choices for prime numbers pp and qq such that q>p2q > p^2. For example, we can take p=2p = 2 and qq an arbitrary prime number bigger than 5. As there are infinitely many prime numbers, we have proven the statement.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.