Maths Olympiad Prep

Library / /2 of 9

Number theory Difficulty 5.8 AIME, harder Prove it United States

Find all pairs of positive integers (a,b)(a, b) satisfying the following conditions:
(i) aa divides b4+1b^4 + 1,
(ii) bb divides a4+1a^4 + 1,
(iii) a=b\lfloor\sqrt{a}\rfloor = \lfloor\sqrt{b}\rfloor.

Solution

The only solutions are (1,1)(1, 1), (1,2)(1, 2), and (2,1)(2, 1), which clearly work. Now we show there are no others.

Obviously, gcd(a,b)=1\gcd(a, b) = 1, so the problem conditions imply
ab(ab)4+1 ab \mid (a - b)^4 + 1
since each of aa and bb divide the right-hand side. We define
k=def(ba)4+1ab. k \stackrel{\text{def}}{=} \frac{(b - a)^4 + 1}{ab}.

Claim (Size estimate) — We must have k16k \le 16.

Proof. Let n=a=bn = \lfloor\sqrt{a}\rfloor = \lfloor\sqrt{b}\rfloor, so that a,b[n2,n2+2n]a, b \in [n^2, n^2 + 2n]. We have that
abn2(n2+1)n4+1(ba)4+1(2n)4+1=16n4+1 ab \ge n^2(n^2 + 1) \ge n^4 + 1 \\ (b-a)^4 + 1 \le (2n)^4 + 1 = 16n^4 + 1
which shows k16k \le 16. \square

Claim (Orders argument) — In fact, k=1k = 1.

Proof. First of all, note that kk cannot be even: if it was, then a,ba, b have opposite parity, but then 4(ba)4+14 \mid (b-a)^4 + 1, contradiction.
Thus kk is odd. However, every odd prime divisor of (ba)4+1(b-a)^4 + 1 is congruent to 1(mod8)1 \pmod{8} and is thus at least 1717, so k=1k = 1 or k17k \ge 17. It follows that k=1k = 1. \square

At this point, we have reduced to solving
ab=(ba)4+1 ab = (b - a)^4 + 1
and we need to prove the claimed solutions are the only ones. Write b=a+db = a + d, and assume WLOG that d0d \ge 0: then we have a(a+d)=d4+1a(a + d) = d^4 + 1, or
a2da(d4+1)=0. a^2 - da - (d^4 + 1) = 0.
The discriminant d2+4(d4+1)=4d4+d2+4d^2 + 4(d^4 + 1) = 4d^4 + d^2 + 4 must be a perfect square.

* The cases d=0d = 0 and d=1d = 1 lead to pairs (1,1)(1, 1) and (1,2)(1, 2).
* If d2d \ge 2, then we can sandwich
(2d2)2<4d4+d2+4<4d4+4d2+1=(2d2+1)2, (2d^2)^2 < 4d^4 + d^2 + 4 < 4d^4 + 4d^2 + 1 = (2d^2 + 1)^2,
so the discriminant is not a square.

The solution is complete.

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.