Maths Olympiad Prep

Library / /417 of 462

Number theory Difficulty 7.1 National Olympiad, round 2 Prove it Ireland

Let 1=d1<d2<d3<<dn=N1 = d_1 < d_2 < d_3 < \dots < d_n = N be the list of all positive divisors of the integer NN. Check that N=2020N = 2020 is a number for which
N=d3d4d7andd3d4<d7. N = d_3d_4d_7 \quad \text{and} \quad d_3d_4 < d_7.
Find all numbers NN satisfying these conditions.

Solution

The prime factorisation of 20202020 is 2020=451012020 = 4 \cdot 5 \cdot 101 and so a complete list of divisors of 20202020 is:
d1=1,d2=2,d3=4,d4=5,d5=10,d6=20,d7=101,d8=202,d9=404,d10=505,d11=1010,d12=2020. \begin{aligned} d_1 &= 1,\quad d_2 = 2,\quad d_3 = 4,\quad d_4 = 5,\quad d_5 = 10,\quad d_6 = 20,\quad d_7 = 101, \\ d_8 &= 202,\quad d_9 = 404,\quad d_{10} = 505,\quad d_{11} = 1010,\quad d_{12} = 2020. \end{aligned}
The required properties, 2020=d3d4d72020 = d_3d_4d_7 and d3d4<d7d_3d_4 < d_7, are now easy to check.

As N=d3d4d7N = d_3d_4d_7, the product d3d4d_3d_4 is a divisor of NN, which was assumed to be smaller than d7d_7. Hence d3d4=d5d_3d_4 = d_5 or d3d4=d6d_3d_4 = d_6. We first exclude that d3d4=d5d_3d_4 = d_5. In this case, N=d3d4d7=d5d7N = d_3d_4d_7 = d_5d_7 and the number of divisors of NN is equal to 1111. Because the number of positive divisors of N=pieiN = \prod p_i^{e_i} is equal to (ei+1)\prod (e_i + 1), any number with exactly 1111 divisors must be of the form N=p10N = p^{10} where pp is a prime number. But then d3=p2d_3 = p^2, d4=p3d_4 = p^3 and d5=p4d_5 = p^4 and so d3d4d5d_3d_4 \neq d_5. This shows that we must have d3d4=d6d_3d_4 = d_6. Then N=d3d4d7=d6d7N = d_3d_4d_7 = d_6d_7 and NN has 1212 divisors.
As 12=62=43=32212 = 6 \cdot 2 = 4 \cdot 3 = 3 \cdot 2 \cdot 2 we have to consider the following four cases: N=p11N = p^{11}, N=p5qN = p^5q, N=p3q2N = p^3q^2, N=p2qrN = p^2qr where p,q,rp, q, r are distinct primes.

N=p11N = p^{11}: In this case, d3=p2d_3 = p^2, d4=p3d_4 = p^3 and d7=p6d_7 = p^6, and we see that N=d3d4d7N = d_3d_4d_7 as well as d3d4<d7d_3d_4 < d_7 as required.

N=p5qN = p^5q: We have 1<p<p2<p3<p4<p51 < p < p^2 < p^3 < p^4 < p^5 and we can order the divisors of NN once we know the size of qq. There are six possibilities
Figure 1
and we easily check that d3d4<d7d_3d_4 < d_7 holds when 1<q<p1 < q < p and when p5<qp^5 < q.

N=p3q2N = p^3q^2: We will investigate all possibilities for d6d7=p3q2d_6d_7 = p^3q^2 and check if d3d4=d6d_3d_4 = d_6. The pairs {di,d13i}\{d_i, d_{13-i}\}, whose product is NN, are the following:
{1,p3q2},{p,p2q2},{p2,pq2},{p3,q2},{q,p3q},{pq,p2q}. \{1, p^3q^2\},\quad \{p, p^2q^2\},\quad \{p^2, pq^2\},\quad \{p^3, q^2\},\quad \{q, p^3q\},\quad \{pq, p^2q\}.
Because p3q2p^3q^2, p2q2p^2q^2 and p3qp^3q have more than 77 factors, these cannot be equal to d6d_6 or d7d_7, so we have only three options to consider for {d6,d7}\{d_6, d_7\}, namely {p2,pq2}\{p^2, pq^2\}, {p3,q2}\{p^3, q^2\} or {pq,p2q}\{pq, p^2q\}.
If {d6,d7}={p2,pq2}\{d_6, d_7\} = \{p^2, pq^2\}, then d6=pq2d_6 = pq^2 and d7=p2d_7 = p^2, because we cannot have d6=p2=d3d4d_6 = p^2 = d_3d_4 as d3>1d_3 > 1. From pq2=d6<d7=p2pq^2 = d_6 < d_7 = p^2, we get q2<pq^2 < p. Hence, the divisors of NN need to satisfy
1<q<q2<p<pq<pq2<p2<p2q<p2q2<p3<p3q<p3q2. 1 < q < q^2 < p < pq < pq^2 < p^2 < p^2q < p^2q^2 < p^3 < p^3q < p^3q^2.
We see now that d3d4=d6d_3d_4 = d_6 and we get a working solution.

If {d6,d7}={p3,q2}\{d_6, d_7\} = \{p^3, q^2\}, then d6=p3d_6 = p^3 and d7=q2d_7 = q^2, because we cannot have d6=q2=d3d4d_6 = q^2 = d_3d_4 as d3>1d_3 > 1. The equation p3=d6=d3d4p^3 = d_6 = d_3d_4 can only be achieved with d3=pd_3 = p and d4=p2d_4 = p^2. This implies d2=qd_2 = q and so 1<q<p<p21 < q < p < p^2. But then d3=p<pq<p2=d4d_3 = p < pq < p^2 = d_4, a contradiction.
If {d6,d7}={pq,p2q}\{d_6, d_7\} = \{pq, p^2q\}, then d6=pq<p2q=d7d_6 = pq < p^2q = d_7, and pq=d6=d3d4pq = d_6 = d_3d_4 could only be achieved with d3=p,d4=qd_3 = p, d_4 = q or d3=q,d4=pd_3 = q, d_4 = p. Both are impossible as there would be no option left for d2d_2.

N=p2qrN = p^2qr: We may assume that 1<q<r<qr1 < q < r < qr. Because p2qp^2q has six divisors and all other divisors of NN are multiples of rr, dk=rd_k = r for some 3k73 \le k \le 7.
If d7=rd_7 = r, then d6=p2qd_6 = p^2q and we automatically have d6=d3d4d_6 = d_3d_4 as p2qp^2q has six divisors. This case occurs precisely when p2q<rp^2q < r.
If d6=rd_6 = r, then d6=d3d4d_6 = d_3d_4 is impossible as d3>1d_3 > 1.
If d5=rd_5 = r, then d8=p2qd_8 = p^2q and d6,d7d_6, d_7 must form one of the pairs {p,pqr}\{p, pqr\}, {pq,pr}\{pq, pr\}, {p2,qr}\{p^2, qr\}. The first of these three is impossible, as p<pq<pr<pqrp < pq < pr < pqr. Secondly, when d6=pq<pr=d7d_6 = pq < pr = d_7, pq=d6=d3d4pq = d_6 = d_3d_4 could only be achieved with d3=p,d4=qd_3 = p, d_4 = q or d3=q,d4=pd_3 = q, d_4 = p. Both are impossible as there would be no option left for d2d_2. For the third option we first note that d6=p2d_6 = p^2 can be ruled out as before using d6=d3d4d_6 = d_3d_4. However, d6=qrd_6 = qr is impossible as well, because d5=rd_5 = r and we again get a problem with d6=d3d4d_6 = d_3d_4.
If d4=rd_4 = r, then d2=pd_2 = p or d3=pd_3 = p. In the first case we would have 1<p<q<r1 < p < q < r and so d6=d3d4=qrd_6 = d_3d_4 = qr, which implies d7=p2d_7 = p^2. However, we have p2<pq<prp^2 < pq < pr which would mean that both members of the pair {pq,pr}\{pq, pr\} are larger than d7d_7, contradiction. In the second case, we would have 1<q<p<r1 < q < p < r and so d6=d3d4=prd_6 = d_3d_4 = pr, which implies d7=pqd_7 = pq. But q<rq < r implies d7=pq<pr=d6d_7 = pq < pr = d_6, contradiction.
If d3=rd_3 = r, then d4=pd_4 = p because d6=d3d4d_6 = d_3d_4 cannot be divisible by r2r^2. We get d6=prd_6 = pr and d7=pqd_7 = pq. But q<rq < r implies d7=pq<pr=d6d_7 = pq < pr = d_6, a contradiction.

To summarise, the complete list of solutions is:

NNConditions
N=p11N = p^{11}where pp is a prime
N=p5qN = p^5qwhere p,qp, q are primes such that q<pq < p or p5<qp^5 < q
N=p3q2N = p^3q^2where p,qp, q are primes such that q2<pq^2 < p
N=p2qrN = p^2qrwhere p,q,rp, q, r are primes such that p2q<rp^2q < r.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.