Let a and b be two distinct natural numbers. It is known that a2+b|b2+a and that b2+a is a power of a prime number. Determine the possible values of a and b.
Problem
Source: IV International Festival of Young Mathematicians Sozopol 2013, Theme for 10-12 grade
Tags: number theory, Prime number, power of number, Divisibility
30.01.2020 14:50
According to the given information a≠b are two natural numbers and there is a prime p and a natural number k satisfying (1)a2+b∣b2+a and (2)b2+a=pk. Combining conditions (1) and (2) we obtain a2+b∣pk, implying there is a natural number m≤k s.t. (3)a2+b=pm. Subtracting equation (3) from equation (2), the result is (4)(b−a)(b+a−1)=pm(pk−m−1). Hence a<b and m<k by equation (4). Assume pm∣b−a or pm∣b+a−1. Consequently, since b+a−1>b−a, we have pm≤b+a−1, which according to equation (3) yields b+a−1≥a2+b, i.e. a2−a+1≤0, which is impossible since a≥1. This contradiction combined with equation (4) give us (5)p∣b−a, (6)p∣b+a−1. Subtracting (5) from (6) and adding (5) and (6) we obtain p∣2a−1 and p∣2b−1 respectively. Hence p is odd, which according to equation (2) give us 0 \equiv 4p^k = (2b)^2 + 2 \cdot (2a) \equiv 1^2 + 2 \cdot 1 = 1 + 2 = 3 \pmod{p}, i.e. 3|p. Therefore p=3, which inserted in equation (2)-(4) give us (7) \;\; b^2 + a = 3^k, (8) \;\; a^2 + b = 3^m, (9) \;\; (b - a)(b + a - 1) = 3^m(3^{k-m} - 1). Observe that 3^k = b^2 + a \geq 2^2 + 1 = 4+1 = 5 > 3, yielding k \geq 2. Next assume 9 \mid b-a and 9 \mid b+a-1. Hence 9 \mid (b + a - 1) \pm (b - a), which means 9 \mid 2a - 1 and 9 \mid 2b - 1. Thus we have a \equiv b \equiv 5 \pmod{9}, which according to equation (7) (since k \geq 2) yields 0 \equiv 3^k = b^2 + a \equiv 5^2 + 5 = 25 + 5 = 30 \equiv 3 \pmod{9}, a contradiction implying 9 \nmid b-a or 9 \nmid b+a-1. Hence by equation (9) we obtain 3^{m-1} \mid b-a or 3^{m-1} \mid b+a-1. Hence there are two natural numbers s and t s.t. (10) \;\; b - a = 3^{m-1}s or (11) \;\; b+a-1 = 3^{m-1}t, where s,t \in \{1,2\} (we know that b-a < b+a-1 < p^m = 3^m). Thus we have the following two cases: Case 1: b-a=3^{m-1}s. If s=2, then b-a is even, yielding a^2 + b is even, contradicting equation (8). Consequently s=1, which give us b-a = 3^{m-1}, which combined with equation (8) yields 3(b - a) = 3^m = a^2 + b. This means 2b = a^2 + 3a, which according to equation (8) result in 2 \cdot 3^m = 2a^2 + 2b = 2a^2 + (a^2 + 3a) = 3a(a+1), i.e. (12) \;\; a(a+1) = 2 \cdot 3^{m-1}. Therefore, since GCD(a,a+1)=1, we have 3^{m-1} \mid a or 3^{m-1} \mid a+1, which combined with equation (12) yields a \leq 2. Thus we obtain 3^{m-1}=1 when a=1 and 3^{m-1}=3 when a=2. In other words, since 2b=a^2+3a, we obtain (a,b,m)=(1,2,1) or (a,b,m)=(2,5,2), yielding b^2+a=2^2+1=4+1=5 and b^2+a=5^2+2=25+2=27=3^3. Hence by equation (7) the only solution of equations (7)-(8) is (a,b,m,k)=(2,5,2,3). Case 2: b+a-1=3^{m-1}t. Then according to equation (8) (a^2 + b)t = 3^m \cdot t = 3(b + a - 1), i.e. (13) \;\; (3 - t)b = ta^2 - 3a + 3. If t=1, then a^2 - 3a + 3 is even by equation (13), which is impossible since a^2 - 3a is even. Consequently t=2 by contradiction, which inserted in equation (13) give us (14) \;\; b = 2a^2 - 3a + 3. Combining equations (8) and (14) we find that 3^m = a^2 + b = a^2 + (2a^2 - 3a + 3) = 3(a^2 - a + 1), i.e. (15) \;\; a^2 - a + 1 = 3^{m-1}. The fact that 9 \nmid a^2 - a + 1 combined with equation (15) yields m \leq 2. Thus (a,b)=(1,2) or (a,b)=(2,5) by equations (15) and (14). From case 1 we know that the only solution is (a,b)=(2,5) with (k,m)=(3,2). Conclusion: The only pair of distinct natural numbers (a,b) satisfying conditions (1) and (2) is (a,b)=(2,5).