Olympiad Maths Prep

Library / /4 of 14

Number theory Difficulty 5.9 AIME, harder Prove it Czech Republic

Let nn be a natural number whose all positive divisors are denoted as d1,d2,,dkd_1, d_2, \dots, d_k in such a way that d1<d2<<dkd_1 < d_2 < \dots < d_k (thus d1=1d_1 = 1 and dk=nd_k = n). Determine all the values of nn for which both equalities d5d3=50d_5 - d_3 = 50 and 11d5+8d7=3n11d_5 + 8d_7 = 3n hold. (Matúš Harminc)

Solutions — 2

Solution 1

We distinguish whether nn is odd or even.

i) The case of nn odd. Since all the did_i's are odd too, it follows from 11d5+8d7=3n11d_5+8d_7 = 3n that d711d5d_7 \mid 11d_5 as well as d58d7d_5 \mid 8d_7, hence d5d7d_5 \mid d_7. In view of d7>d5d_7 > d_5, the relations d5d711d5d_5 \mid d_7 \mid 11d_5 imply that d7=11d5d_7 = 11d_5. Substituting this into 11d5+8d7=3n11d_5 + 8d_7 = 3n, we obtain 99d5=3n99d_5 = 3n or 33d5=n33d_5 = n. Thus the four numbers 1, 3, 11 and 33 are divisors of nn, more exactly all its divisors smaller than 50, since the fifth divisor d5d_5 satisfies d5=d3+50>50d_5 = d_3 + 50 > 50. Consequently, it holds that d1=1d_1 = 1, d2=3d_2 = 3, d3=11d_3 = 11, d4=33d_4 = 33, d5=d3+50=61d_5 = d_3 + 50 = 61, and thus n=33d5=3361=2013n = 33d_5 = 33 \cdot 61 = 2013. The number 2013 is satisfactory indeed, because its first small divisors as indicated in the last sentence and moreover, the subsequent divisors are d6=613d_6 = 61 \cdot 3 and d7=6111d_7 = 61 \cdot 11; hence d7=11d5d_7 = 11d_5 as required.

ii) The case of nn even. Now the equality 11d5+8d7=3n11d_5 + 8d_7 = 3n implies that 2d52 \mid d_5 and hence 2d550=d32 \mid d_5 - 50 = d_3 as well. Since d1=1d_1 = 1, d2=2d_2 = 2 and d33d_3 \neq 3, we conclude that either d3=4d_3 = 4, or d3=2td_3 = 2t, with some integer t>2t > 2. But the last is impossible (otherwise tt is a divisor of nn with d2<t<d3d_2 < t < d_3, a contradiction), Therefore, we have d3=4d_3 = 4, d5=d3+50=54d_5 = d_3 + 50 = 54 and hence 3 is a divisor of nn between d2d_2 and d3d_3, a contradiction. In this way, the nonexistence of any satisfactory even nn is proven.

Answer. The problem has the only solution n=2013n = 2013.

Solution 2

The divisors d5d_5 and d7d_7 of nn, with d5<d7d_5 < d_7, can be represented as d5=n/xd_5 = n/x and d7=n/yd_7 = n/y, where xx and yy (x>yx > y) are some positive divisors of nn again. Substituting this into 11d5+8d7=3n11d_5 + 8d_7 = 3n, we obtain (after cancelling nn) an equation 11/x+8/y=311/x + 8/y = 3 which can be solved in a standard way, for example by a simple factorization:
8x=y(3x11)8(3x11)+88=3y(3x11)(3x11)(3y8)=88. 8x = y(3x - 11) \Leftrightarrow 8(3x - 11) + 88 = 3y(3x - 11) \Leftrightarrow (3x - 11)(3y - 8) = 88.
The first equation implies that 3x11>03x - 11 > 0 and hence 3y8>03y - 8 > 0 as well. Note that xy+1x \ge y + 1 yields 3x113y8>03x - 11 \ge 3y - 8 > 0. Taking into account the prime factorization 88=231188 = 2^3 \cdot 11, we conclude that the ordered pair (3x11,3y8)(3x - 11, 3y - 8) of factors must belong to the following set
{(88,1),(44,2),(22,4),(11,8)}. \{(88, 1), (44, 2), (22, 4), (11, 8)\}.
However, congruences modulo 3 imply the only two pairs (88, 1) and (22, 4) are admissible. The corresponding pairs (x,y)(x, y) are (33, 3) and (11, 4), respectively.

If (x,y)=(33,3)(x, y) = (33, 3), then d5=n/33d_5 = n/33 (and d7=n/3d_7 = n/3), thus 1, 3, 11 and 33 are divisors of nn which leads (as in the above solution) to the solution n=2013n = 2013.
If (x,y)=(11,4)(x, y) = (11, 4), then d5=n/11d_5 = n/11 and d7=n/4d_7 = n/4, thus 1, 2, 4, 11, 22 and 44 are divisors of nn, which contradicts d5>50d_5 > 50.

Looking for a route rather than 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.