Maths Olympiad Prep

Library / /24 of 87

Number theory Difficulty 5.8 AIME, harder Prove it Serbia

Problem:

Find all natural numbers aa and bb such that
ab2,ba2anda+1b2+1. a \mid b^{2}, \quad b \mid a^{2} \quad \text{and} \quad a+1 \mid b^{2}+1.

Solution

Solution:

Let b2=cab^{2}=c a. The conditions of the problem give b2=caa4b^{2}=c a \mid a^{4} and a+1ca+1a+1 \mid c a+1, and this is equivalent to
ca3anda+1c1. c \mid a^{3} \quad \text{and} \quad a+1 \mid c-1.
Let c=d(a+1)+1, dN0c=d(a+1)+1,\ d \in \mathbb{N}_{0}. Since a31(moda+1)a^{3} \equiv -1 \pmod{a+1}, we have a3c1(moda+1)\frac{a^{3}}{c} \equiv -1 \pmod{a+1}, i.e. a3c=e(a+1)1\frac{a^{3}}{c}=e(a+1)-1 for some eNe \in \mathbb{N}. It follows that a3=(d(a+1)+1)(e(a+1)1)a^{3}=(d(a+1)+1)(e(a+1)-1), which after multiplying out and cancelling a+1a+1 becomes a2a+1=de(a+1)+(ed)a^{2}-a+1=d e(a+1)+(e-d). From here we have eda2a+13(moda+1)e-d \equiv a^{2}-a+1 \equiv 3 \pmod{a+1}, hence
ed=k(a+1)+3andde=a2k(kZ). e-d=k(a+1)+3 \quad \text{and} \quad d e=a-2-k \quad (k \in \mathbb{Z}).
We distinguish the following cases:

(1) k{1,0}k \notin\{-1,0\}. In this case (*) implies de<ed1d e<|e-d|-1, which is possible only for d=0d=0. Now c=1c=1 and b2=ab^{2}=a, hence (a,b)=(t2,t)(a, b)=\left(t^{2}, t\right).

(2) k=1k=-1. From (*) we obtain a=d+1a=d+1. Now c=a2c=a^{2} and b2=a3b^{2}=a^{3}, hence (a,b)=(t2,t3)(a, b)=\left(t^{2}, t^{3}\right).

(3) k=0k=0. From (*) we obtain a=d2+3d+2a=d^{2}+3 d+2. Now c=d(a+1)+1=(d+1)3c=d(a+1)+1=(d+1)^{3} and b2=ca=(d+1)4(d+2)b^{2}=c a=(d+1)^{4}(d+2). It follows that d+2=t2d+2=t^{2} for some tNt \in \mathbb{N}, which gives (a,b)=(t2(t21),t(t21)2), t2(a, b)=\left(t^{2}(t^{2}-1), t(t^{2}-1)^{2}\right),\ t \geq 2.

Answer: These are the pairs (a,b)(a, b) of the form (t2,t), (t2,t3)\left(t^{2}, t\right),\ \left(t^{2}, t^{3}\right) and (t2(t21),t(t21)2)\left(t^{2}(t^{2}-1), t(t^{2}-1)^{2}\right), where tNt \in \mathbb{N}.

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 translated into English from sr; metadata (topic, difficulty) added by this project.