Maths Olympiad Prep

Library / /270 of 462

Number theory Difficulty 6.0 AIME, harder Prove it Ireland

The integer NN has eight positive divisors 1=d1<d2<d3<<d8=N1 = d_1 < d_2 < d_3 < \dots < d_8 = N. Find the two smallest integers NN for which 2d2d5=d3d4+32d_2d_5 = d_3d_4 + 3.

Solution

The number of distinct positive divisors of an integer N=pieiN = \prod p_i^{e_i} with distinct primes pip_i is equal to (ei+1)\prod (e_i + 1). Because 88 has only the factorizations 88, 424 \cdot 2 and 2222 \cdot 2 \cdot 2, we have to consider three cases:

Case A: N=p7N = p^7
Case B: N=p3qN = p^3q
Case C: N=pqrN = pqr,
where p,q,rp, q, r are distinct primes. and these reduce to sub-cases.

In Case A we have dk=pk1d_k = p^{k-1} and 2d2d5=d3d4+32d_2d_5 = d_3d_4 + 3 is equivalent to p5=3p^5 = 3, which does not hold for any pp.

In Case B we consider the following four sub-cases
1) q<pq < p
2) p<q<p2p < q < p^2
3) p2<q<p3p^2 < q < p^3
4) p3<qp^3 < q.
These inequalities lead to identification of d2,d3,d4,d5d_2, d_3, d_4, d_5 in each case as follows:
1) d2=qd_2 = q, d3=pd_3 = p, d4=pqd_4 = pq, d5=p2d_5 = p^2
2) d2=pd_2 = p, d3=qd_3 = q, d4=p2d_4 = p^2, d5=pqd_5 = pq
3) d2=pd_2 = p, d3=p2d_3 = p^2, d4=qd_4 = q, d5=p3d_5 = p^3
4) d2=pd_2 = p, d3=p2d_3 = p^2, d4=p3d_4 = p^3, d5=qd_5 = q
These give rise to one solution from sub-case 4) with p=3p = 3 and q=41q = 41 leading to N=3341=1107N = 3^3 \cdot 41 = 1107. The first three cases would require 33 to be divisible by p2p^2, which is not possible.

In Case C, w.l.o.g., we can assume p<q<rp < q < r. We consider two sub-cases:
1) r<pqr < pq and 2) pq<rpq < r.

1) d2=pd_2 = p, d3=qd_3 = q, d4=rd_4 = r, d5=pqd_5 = pq

2p2q=qr+32p^2q = qr + 3, i.e. q(2p2r)=3q(2p^2 - r) = 3 and so q=3q = 3 and 2p2=r+12p^2 = r + 1. As p<qp < q we get p=2p = 2 and so r=7r = 7. However, we now have r=7>6=pqr = 7 > 6 = pq and no solutions arise.

2) d2=pd_2 = p, d3=qd_3 = q, d4=pqd_4 = pq, d5=rd_5 = r

2pr=pq2+32pr = pq^2 + 3, i.e. p(2rq2)=3p(2r - q^2) = 3. This gives p=3p = 3. We have a solution if r=(q2+1)/2r = (q^2 + 1)/2. Using q=5,7,11q = 5, 7, 11 gives r=13,25,61r = 13, 25, 61, respectively. As 13<pq=1513 < pq = 15 and 2525 is not prime, the smallest value of qq to yield a solution is q=11q = 11. This gives N=2013N = 2013.

Larger values of qq for which (q2+1)/2(q^2 + 1)/2 is a prime (greater than 6161) yield other values of NN which will be bigger than 11071107 and 20132013. Thus these are the two smallest solutions.

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.