Maths Olympiad Prep

Library / /1 of 36

, 2023

Number theory Difficulty 7.1 National olympiad, round 2 Prove it Baltic Way

Call a pair of positive integers (a,b)(a, b) carroty if S(ab+1)=abS(a^{b+1}) = a^b, where S(m)S(m) is the digit sum of mm. Find all carroty pairs (a,b)(a, b).

Solution

Answer: (a,b){(1,b)bZ+}{(3,2),(9,1)}(a, b) \in \{(1, b) \mid b \in \mathbb{Z}^+\} \cup \{(3, 2), (9, 1)\}.

Let us consider the case where k2k \ge 2. Then k2(k1)k \le 2(k-1) and note that b+12bb+1 \le 2b as b1b \ge 1. Put (k1)b=:x(k-1)b =: x, then k(b+1)4(k1)b=4xk(b+1) \le 4(k-1)b = 4x. So 10x36x10^x \le 36x. It is obvious that the only solutions in nonnegative integers to this inequality are x=0x = 0 and x=1x = 1. Indeed, for x2x \ge 2, the left hand side grows faster. Therefore, either k=1k = 1 or k=2k = 2 and b=1b = 1.
Now we have only two cases left.

Case 1: b=1b = 1 and k=2k = 2. We are left with the equation S(a2)=aS(a^2) = a, for 10a<10010 \le a < 100. Then a2<104a^2 < 10^4, so a=S(a2)94=36a = S(a^2) \le 9 \cdot 4 = 36.
Moreover, taking into account the fact that the sum of digits does not change the number modulo 9, a2a(mod9)a^2 \equiv a \pmod{9}, i.e., a(a1)0(mod9)a(a - 1) \equiv 0 \pmod{9}, therefore a0(mod9)a \equiv 0 \pmod{9} or a1(mod9)a \equiv 1 \pmod{9}. So now we are left only with numbers a{10,18,19,27,28,36}a \in \{10, 18, 19, 27, 28, 36\}, which we can easily check by substitution and see that there are no solutions.

Case 2: k=1k=1. In the same way, by checking modulo 9, we get that ab+1ab(mod9)a^{b+1} \equiv a^b \pmod{9} implies ab(a1)0(mod9)a^b(a-1) \equiv 0 \pmod{9}. Therefore either a=1a=1 or aa is divisible by 3. a=1a=1 is an obvious solution with all bZ+b \in \mathbb{Z}^+.
Otherwise, a{3,6,9}a \in \{3, 6, 9\}. But then ab+1<10b+1a^{b+1} < 10^{b+1} and S(ab+1)9(b+1)S(a^{b+1}) \le 9(b+1). Therefore, 3bab=S(ab+1)9(b+1)3^b \le a^b = S(a^{b+1}) \le 9(b+1). But from 3b9(b+1)3^b \le 9(b+1), we can conclude b3b \le 3. Indeed, for b4b \ge 4, the left hand side increases faster. So we are left with a{3,6,9}a \in \{3, 6, 9\} and b3b \le 3. We check all these cases to determine that only (a,b)=(3,2)(a, b) = (3, 2) or (a,b)=(9,1)(a, b) = (9, 1) are 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 and solution reproduced as published; topic and difficulty added by this site.