Find all pairs $(a,b)$ of positive integers such that $a^2\mid b^3+1$ and $b^2\mid a^3+1$. Linus Tang
Problem
Source: ELMO Shortlist 2024/N4
Tags: Elmo, number theory
22.06.2024 19:26
IAmTheHazard wrote: Find all pairs $(a,b)$ of positive integers such that $a^2\mid b^3+1$ and $b^2\mid a^3+1$. Linus Tang It is special case of this problem (for $c=1$).
22.06.2024 20:44
Reminds me a lot of IMO SL 2019 N2, hopefully I have not made calculation errors. Clearly $a$ and $b$ are coprime and $a^2$ and $b^2$ both divide $a^3 + b^3 + 1$, so it is equivalent to investigate $a^2b^2$ dividing $a^3 + b^3 + 1$. Assume without loss of generality that $a\geq b$. Then $2a^3 + 1 \geq a^2b^2$, so $2a + \frac{1}{a^2} \geq b^2$, so $2a + 1 \geq b^2$, i.e. $a \geq \frac{b^2-1}{2}$. On the other hand, $a^2 \leq b^3 + 1$ now implies $(b^2-1)^2 \leq 4b^3 + 4$, that is, $b^2(b(b-4)-2) \leq 5$, implying $b\leq 4$. If $b=4$, then $a^2 \mid 65$, so $a=1$, but $b^3 \nmid a^2+1$. If $b=3$, then $a^2 \mid 28$ (so $a^2 \leq 4$) and $9 \mid a^3+1$, so $a=2$. If $b=2$, then $a^2 \mid 9$ and $4 \mid a^3+1$, so $a=3$. Finally, if $b=1$, then $a=1$. So all solutions are $(1,1)$, $(3,2)$, $(2,3)$.
23.06.2024 16:41
IAmTheHazard wrote: Find all pairs $(a,b)$ of positive integers such that $a^2\mid b^3+1$ and $b^2\mid a^3+1$. Linus Tang Soppuse that $a>=b$ $a^2b^2|a^3+b^3+1\Rightarrow a^2b^2\leqslant a^3+b^3+1$ $a^2|b^3+1$ If $a^2\leqslant \frac{b^3+1}{2}\Rightarrow b\geqslant a^{\frac{2}{3}}$ so $a^2b^2\leqslant a^3+b^3+1\Rightarrow b^2\leqslant a+\frac{b^3}{a^2}+\frac{1}{a^2}< a+b+1\leqslant 2a+1$ But $a^{\frac{4}{3}}\leqslant b^2\leqslant 2a+1$ from where we get that $a<10$ If $a^2=b^3+1$ we have that: $b^5+b^2=a^2b^2= a^3+b^3+1=(b^3+1)\sqrt{b^3+1}+b^3+1$ which gives that $b<3$ Cheking for $a\leqslant 9$ we get the sollution $(a,b)=(1,1)(2,3)(3,2)$
05.07.2024 00:44
The only solutions are $(1,1), (2,3), (3,2)$. These work. First we solve the cases where $\min(a,b) < 3$. WLOG $b = \min(a,b)$. If $b = 1$, then $a^2 \mid 2\implies a = 1$. If $b = 2$, then $a^2 \mid 9$, but $a = 1$ fails since $2^2 \nmid 1^3 + 1$, so we must have $a = 3$. It suffices to show there are no solutions where both $a$ and $b$ are at least $3$. WLOG that $a \ge b$. Notice that\[a^2 b^2 \mid (a^3 + 1)(b^3 + 1)\implies a^2b^2 \mid a^3 + b^3 + 1\]Therefore $a^2 b^2 \le a^3 + b^3 + 1$. Now, since $a^2 \mid b^3 + 1$, $a^2 \le b^3 + 1$, so $a^3 \le a(b^3 + 1)$. Hence\[ a^2b^2 \le a^3 + b^3 + 1 \le a(b^3 + 1) + b^3 + 1 = (a+1)(b^3 + 1) \]This implies $\frac{a^2}{a + 1} \le \frac{b^3 + 1}{b^2} $. Notice that the LHS is clearly greater than $a - 1$ (since $a^2 = (a-1)(a+1) + 1$) and the RHS is clearly less than $b + 1$ (since it equals $b + \frac{1}{b^2}$ ), so $a - 1 < b + 1\implies a - b < 2$. However, we assumed $a > b$, so $a - b \in \{0,1\}$. If $a = b $, then $a^2 \mid a^3 + 1 \implies a = 1$. If $a = b + 1$, then $b^2 \mid (b+1)^3 + 1\implies b^2 \mid 3b + 2$, so $b\mid 3b + 2\implies b \mid 2$, so $b = 1$ or $b = 2$. Hence there are no solutions where $a, b \ge 3$.
17.07.2024 11:35
IAmTheHazard wrote: Find all pairs $(a,b)$ of positive integers such that $a^2\mid b^3+1$ and $b^2\mid a^3+1$. Linus Tang This is Kazakhstan 2022 National Olympiad Regional stage 9th grade 3rd problem
14.08.2024 20:42
The only pairs are $(1,1)$, $(2,3)$ and $(3,2)$. We now show these are the only pairs. Clearly, $\gcd (a,b) = 1$, so we can combine $a^2 \mid a^3 + b^3 + 1$ and $b^2 \mid a^3 + b^3 + 1$ to get \[a^2 b^2 \mid a^3 + b^3 + 1 \implies a^2 b^2 \leq a^3 + b^3 + 1.\]WLOG, assume that $a < b$. We also have $a^3 +1 \geq b^2$, so altogether, we may assume $b^2-1 \leq a^3 < b^3$. This inequality, combined with the one above, is enough to get an upperbound on $b$: \begin{align*} (b^2-1)^2 & \leq a^6 \\ & < \left( \frac{a^3 + b^3 + 1}{b^2} \right)^3 \\ & < \left( \frac{2b^3 + 1}{b^2} \right)^3 \\ & < (2b+1)^3. \end{align*}So we have \[b^4 - 8b^3 - 14b^2 - 6b < 0.\]The largest root of this quartic is evidently less than $10$, so we must have $b < 10$. Checking all cases gives us the claimed solutions.
15.08.2024 15:19
If $a=b$, they must be equal to $1$ so suppose that $a>b$. By multiplying the relations we get: $$a^2b^2\mid a^3b^3+a^3+b^3+1 \Rightarrow a^2b^2\mid a^3+b^3+1$$ So we have $a^2b^2\le a^3+b^3+1 \le 2a^3\Rightarrow b^2\le 2a$ (where we used the inequality $(a-1)^3\le a^3-1$). Now we also have that $a^2\le b^3+1$ so putting these together we have $b^4\le 4b^3+4\Rightarrow b\le 4$. Checking these cases we find one more solution $(3,2)$ or $(2,3)$.
15.08.2024 16:28
SomeonesPenguin wrote: If $a=b$, they must be equal to $1$ so suppose that $a>b$. By multiplying the relations we get: $$a^2b^2\mid a^3b^3+a^3+b^3+1 \Rightarrow a^2b^2\mid a^3+b^3+1$$ So we have $a^2b^2\le a^3+b^3+1 \le 2a^3\Rightarrow b^2\le 2a$ (where we used the inequality $(a-1)^3\le a^3-1$). Now we also have that $a^2\le b^3+1$ so putting these together we have $b^4\le 4b^3+4\Rightarrow b\le 4$. Checking these cases we find one more solution $(3,2)$ or $(2,3)$. Why is it that: (and where did the first inequality come from?) $$(a-1)^3 \leq a^3-1 \iff b^2 \leq 2a$$ I see that: $$a^2b^2 \leq a^3 + b^3 +1 \leq a^3 + a^3 + 1 = 2a^3 + 1 \iff a^2b^2 \leq 2a^3 + 1$$Thanks.
15.08.2024 16:50
SZPAMO wrote: IAmTheHazard wrote: Find all pairs $(a,b)$ of positive integers such that $a^2\mid b^3+1$ and $b^2\mid a^3+1$. Linus Tang This is Kazakhstan 2022 National Olympiad Regional stage 9th grade 3rd problem Indeed, solved here
23.08.2024 14:06
Mufara07 wrote: SomeonesPenguin wrote: If $a=b$, they must be equal to $1$ so suppose that $a>b$. By multiplying the relations we get: $$a^2b^2\mid a^3b^3+a^3+b^3+1 \Rightarrow a^2b^2\mid a^3+b^3+1$$ So we have $a^2b^2\le a^3+b^3+1 \le 2a^3\Rightarrow b^2\le 2a$ (where we used the inequality $(a-1)^3\le a^3-1$). Now we also have that $a^2\le b^3+1$ so putting these together we have $b^4\le 4b^3+4\Rightarrow b\le 4$. Checking these cases we find one more solution $(3,2)$ or $(2,3)$. Why is it that: (and where did the first inequality come from?) $$(a-1)^3 \leq a^3-1 \iff b^2 \leq 2a$$ I see that: $$a^2b^2 \leq a^3 + b^3 +1 \leq a^3 + a^3 + 1 = 2a^3 + 1 \iff a^2b^2 \leq 2a^3 + 1$$Thanks. We have that $b<a$ so $b\le a-1$, hence $a^2b^2\le a^3+b^3+1\le a^3 +(a-1)^3+1\le 2a^3 \iff b^2\le 2a$