Maths Olympiad Prep

Library / /37 of 42

Number theory Difficulty 7.2 National olympiad, round 2 Prove it Romania

For a positive integer mm denote S(m)S(m) the sum of its natural divisors, and if nn and pp are positive integers, denote Q(n,p)Q(n, p) the sum of the quotients of the division of nn by the natural divisors of pp (for instance, Q(18,10)=18+9+3+1=31Q(18, 10) = 18 + 9 + 3 + 1 = 31).
Let aa and bb be two positive integers.
a) Prove that, if S(a)=Q(a,b)S(a) = Q(a, b) and S(b)=Q(b,a)S(b) = Q(b, a), then a=ba = b.
b) Is it always true that, if S(a)+S(b)=Q(a,b)+Q(b,a)S(a) + S(b) = Q(a, b) + Q(b, a), then a=ba = b?

Solution

a) If d1,d2,,dpd_1, d_2, \dots, d_p are the positive divisors of a positive integer nn, then {d1,d2,,dp}={nd1,nd2,,ndp}\{d_1, d_2, \dots, d_p\} = \{\frac{n}{d_1}, \frac{n}{d_2}, \dots, \frac{n}{d_p}\}.
Let b1,b2,,bqb_1, b_2, \dots, b_q be the positive divisors of bb. Then
Q(a,b)ab1++abq=ab(bb1++bbq)=abS(b)=abQ(b,a),(1) Q(a, b) \le \frac{a}{b_1} + \dots + \frac{a}{b_q} = \frac{a}{b}\left(\frac{b}{b_1} + \dots + \frac{b}{b_q}\right) = \frac{a}{b}S(b) = \frac{a}{b}Q(b, a), \quad (1)
therefore Q(a,b)aQ(b,a)b\frac{Q(a,b)}{a} \le \frac{Q(b,a)}{b}.

Since the statement is symmetrical with respect to aa and bb, Q(b,a)bQ(a,b)a\frac{Q(b,a)}{b} \le \frac{Q(a,b)}{a}, hence Q(b,a)b=Q(a,b)a\frac{Q(b,a)}{b} = \frac{Q(a,b)}{a}, which shows that (1) is an equality.
This shows that aa is divisible with all the divisors of bb and bb is divisible with all the divisors of aa, so a=ba = b.

b) It is not true. For instance, if a=2a = 2 and b=5b = 5, then S(2)+S(5)=(1+2)+(1+5)=9S(2) + S(5) = (1 + 2) + (1 + 5) = 9 and Q(2,5)+Q(5,2)=2+(5+2)=9Q(2, 5) + Q(5, 2) = 2 + (5 + 2) = 9, but aba \neq b.

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.