Find all relatively prime integers $a,b$ such that $$a^2+a=b^3+b$$
Problem
Source: Swiss TST 2015. Problem 4
Tags: number theory, relatively prime
29.07.2017 17:09
$b=1\to a=1,-2$ Let $b>1$ $b|a+1 \to a=kb-1$ $k(kb-1)=b^2+1$ $k^2b-b^2=k+1 \to b|k+1 \to k=mb-1$ $(mb-1)^2=m+b \to b|m-1$ But $m-1 \geq -b-1 >-2b$ Case 1:$m=-b+1<0$ $mb-1=-1 \to mb=0 \to$ - contradiction. Case 2:$m\geq 1$ and so $m+b=(mb-1)^2 \geq mb-1 \to (m-1)(b-1)\leq 2 \to m=1$ or $b=2,3$ $a^2+a=10$ has sot solutions $a^2+a=30$ has solution $a=5$ Answer: $(-2,1),(1,1),(5,3)$
29.07.2017 17:24
Very beautifull problem! but sorry, what mean "relatively prime integers $a,b $"?
29.07.2017 17:27
LittleKesha wrote: Very beautifull problem! but sorry, what mean "relatively prime integers $a,b $"? $\gcd(a,b)=1$
29.07.2017 17:30
Ah ok thanks tchebytchev.
17.08.2017 07:00
We have that the $LHS$ is non negative for any integer value of $a$ (its absolute minimum is at $a=-0.5$, it has roots $0$ and $1$, and is concave up) and that the sign of $b^3+b$ is the same as the sign of $b$. Therefore, $b$ is a positive integer (we cannot take $b=0$ as $0$ is not coprime with any number). On the other hand, if we fix $b$, we get that there exists at most two values of $a$ that satisfy the equation (for $LHS$ is a second-degree polynomial). In fact, if $(a,b)$ works, then so does $(-1-a,b)$, so we may assume $WLOG$ that $a$ is a positive integer (as $a$ and $-1-a$ have different signs, and finding the positive solution will immediately give us the negative one). Now, time for some modulo magic, and also time to use the fact that $(a,b)=(a-b,b)=1$. $a^2+a \equiv b^3+b \pmod{b^2} \implies a^2-b^2+a \equiv b \pmod{b^2} \implies (a+b+1)(a-b) \equiv 0 \pmod{b^2} \implies b^2|a+b+1 \implies b^2-b-1 \leq a$ $a^2+a \equiv b^3+b \pmod{a} \implies a|b(b^2+1) \implies a|b^2+1$ We have two options: either $a$ is less than or equal to $\frac{b^2+1}{2}$, or it is exactly $b^2+1$. If $a \leq \frac{b^2+1}{2}$, then using our first inequality, we have that $b^2-b-1 \leq \frac{b^2+1}{2} \implies 2b^2-2b-2 \leq b^2+1 \implies (b-1)^2 \leq 4$. Therefore, we have three possibilities: $b=1$ (which gives $(1,1)$ and $(-2,1)$), $b=2$ (no valid solutions), and $b=3$ (which gives $(5,3)$ and $(-6,3)$, the latter of which does not work for $(-6,3) = 3$). If $a=b^2+1$, then by modulo magic and some replacements: $b^4+2b+1 + b+1 \equiv b^3+b \pmod{b} \implies b|2$. Therefore, we have two possibilities: $b=1$ and $a=1^2+1=2$ (doesn't work), or $b=2$ and $a=2^2+1=5$ (doesn't work). In conclusion, the only solutions are $(1,1)$, $(-2,1)$ and $(5,3)$.