Prove that there doesn't exist positive integers $a$ and $b$ such that $a^2+b$ and $b^2+a$ are both powers of $5$.
Assume on the contrary. Let $$a^2+b=5^x, \quad a+b^2=5^y$$
With $x,y\ge 1$. WLOG assume $x\ge y$ which means $a\ge b$ and $$a+b^2\mid a^2+b\implies a^2+b\equiv 0\pmod{a+b^2}$$
Since $a\equiv -b^2\pmod {a+b^2}$ we get $$a^2+b\equiv b^4+b\equiv 0\pmod{a+b^2}$$
Claim $(a,5)=(b,5)=1$. Furthermore $(a,b)=1$.
Proof
Assume $5\mid a$ then immediately $5\mid b$. Let $a=5a_1,$ $ b=5b_1$ plugging this to the original equation $$5a_1^2+b_1=5^{x-1}$$
Now if $x=1$ we get a contradiction. So assume $x\ge 2$ clearly $5\mid b_1$ meaning $b_1=5b_2$. $$a_1^2+b_2=5^{x-2}$$
Again $x=2$ is impossible. So $a_1=5a_2…$ Cleary this can't go on forever hence $a_1=a_2=0$ a contradiction.
If $p\mid (a,b)$ then $p\mid 5$ meaning $p=5$ contradiction.
Back to our result $a+b^2\mid b(b^3+1)$ since $(a+b^2,b)=1$ we get $$a+b^2\mid b^3+1$$
We're pretty much done. we just need the following claim.
Claim $5\mid b+1$.
Proof We know $5\mid b^3+1$ Thus $$b^3\equiv -1\pmod 5\implies b^6\equiv 1\pmod 5$$
$\operatorname{ord}_5b\mid 6$ but $\operatorname{ord}_5b \mid 4$ so $\operatorname{ord}_5b=2$ or $1$. Surely it's not $1$.
$$b^2\equiv 1\pmod 5 \implies b\equiv -1 \pmod 5$$ So $5\mid b+1$.
All our work till now was in order to use the LTE lemma (Lifting the exponent). Since $5\nmid b$ and $5\mid b+1$ we get $$\nu_5(a+b^2)\le \nu_5(b^3+1)=\nu_5(b+1)+\nu_5(3)=\nu_5(b+1)$$
In fact since the LHS is a power of $5$ we get $a+b^2\mid b+1 \implies b+b^2\le a+b^2\le b+1$. Hence $b\le 0$ A contradiction.
I just need a verification and if you see a part where I could've used a better method to do it -especially the first claim- please tell me.
Best Answer
What you've done is mostly correct, but your proof of $\gcd(a,5)=\gcd(b,5)=1$ has a significant problem. In particular, with your result of $a_1^2+b_2=5^{x-2}$, you then wrote
However, you haven't proven, or even indicated, why we require $a_1=5a_2$ (e.g., since there's no indication or requirement that $5 \mid b_2$). Nonetheless, your claim is correct, with also using the other equation being one way to prove it. Starting as you did to first get
$$5a_1^2 + b_1 = 5^{x-1} \tag{1}\label{eq1A}$$
we can then use that same substitution of $a = 5a_1$ and $b = 5b_1$ in the second equation to obtain
$$a_1 + 5b_1^2 = 5^{y-1} \tag{2}\label{eq2A}$$
Next, as you did, we have $x \gt 1$ and $y \gt 1$, so \eqref{eq1A} shows $b_1 = 5b_2$ and \eqref{eq2A} shows $a_1 = 5a_2$. Using these in both equations and simplifying again gives
$$25a_2^2 + b_2 = 5^{x-2}, \; \; \; a_2 + 25b_2^2 = 5^{y-2} \tag{3}\label{eq3A}$$
This procedure can keep being repeated (actually, we could use that $25$ divides $a_2$ and $b_2$, with higher powers of $5$ later, but it's sufficient, as well as simpler & easier, to just use one factor of $5$ each time). After doing that $j$ times, we end up with
$$5^{j}a_j^2 + b_j = 5^{x-j}, \; \; \; a_j + 5^{j}b_j^2 = 5^{y-j} \tag{4}\label{eq4A}$$
which is clearly impossible for large enough $j$ (i.e., since $x \ge y$, once $j = \left\lceil\frac{y}{2}\right\rceil$).
As for potential improvements in the presentation of your proof, the only ones I suggest are with
First, instead of
ord_5bwhich becomes $ord_5b$, so the first part looks like the product of $3$ variables, I recommend using\operatorname{ord}_5binstead, with this becoming $\operatorname{ord}_5b$, and it also automatically adds some horizontal space before the $b$ (with this, to me at least, making it look a bit better). Second, you may wish to explain that the first two parts together means that $\operatorname{ord}_{5}b \mid (\gcd(6,4) = 2)$, so that's why $\operatorname{ord}_{5}b$ must be either $2$ or $1$.Finally, regarding any possibly better methods to use, with your claim that $5 \mid b + 1$, rather than using the multiplicative order, instead as Ross Millikan's answer indicates, use that $5 \nmid a$ so $a^2 \equiv 1 \text { or } 4 \pmod{5}$. Thus, from $a^2 + b \equiv 0 \pmod{5}$, we have $b \equiv 1 \text { or } 4 \pmod{5}$. If $b \equiv 1 \pmod{5}$ then, from $a + b^2 \equiv 0 \pmod{5}$, we have $a \equiv 4 \pmod{5}$. However, then $a^2 + b \equiv 1 + 1 \equiv 2 \pmod{5}$, so $b \not\equiv 1 \pmod{5}$. This means $b \equiv 4 \pmod{5}$ (and also $a \equiv 4 \pmod{5})$.
Second, note that $b^3 + 1 = (b + 1)(b^2 - b + 1)$. With $b \equiv 4 \pmod{5}$, we have $b^2 - b + 1 \equiv 1 - 4 + 1 \equiv 3 \pmod{5}$, so $\nu_5(b^3 + 1) = \nu_5(b + 1)$. This is basically what the lifting-the-exponent (LTE) lemma uses itself but, for something as relatively simple as in this case, it may be preferable to more directly prove it instead as I've explained.