7
$\begingroup$

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.

$\endgroup$
0

2 Answers 2

4
$\begingroup$

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

Again $x=2$ is impossible. So $a_1=5a_2...$

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

$ord_5b\mid 6$ but $ord_5b \mid 4$ so $ord_5b=2$ or $1$

First, instead of ord_5b which becomes $ord_5b$, so the first part looks like the product of $3$ variables, I recommend using \operatorname{ord}_5b instead, 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.

$\endgroup$
0
1
$\begingroup$

Let be by contradiction $a^2+b=5^x$ and $a+b^2=5^y$ with $x\lt y$ (one has $x\ne y$ necessarily) so we have $a^2+b\equiv0\pmod{5^k}$ for $k=1,2,\cdots, x$ and similarly $a+b^2\equiv0\pmod{5^k}$.

For $k=1$ we have the table of the function $f(x,y)=x^2+y$ modulo $5$ where one can see that the only $(a,b)$ and $(b,a)$ giving zero is $(4,4)$. Explaining we have $(x,y)=(1,4),(2,1),(3,1)$ makes $0$ modulo $5$ but $(4,1),(1,2),(1,3)$ does not.

$$\begin{array}{|c|c|}\hline &1 & 2 & 3 & 4 &0 \\\hline 1 & 2 & 3 &4&0&1\\\hline 2 &0&1&2&3&4 \\\hline 3&0&1&2&3&4\\\hline4&2&3&4&0&1\\\hline0&1&2&3&4&0\\\hline\end{array}$$ It follows that $a=5A-1$ and $b=5B-1$ (because $4=-1\pmod5$). Come back to the beginning we have $$\begin{cases}a^2+b=5^x\\a+b^2=5^y\end{cases}\Rightarrow\begin{cases}5^2A^2-10A+5B=5^x\\5^2B^2-10B+5A=5^y\end{cases}\Rightarrow\begin{cases}5A^2-2A+B=5^{x-1}\\5B^2-2B+A=5^{y-1}\end{cases}$$ from which $$(B-A)\left[5(B+A)-3\right]=5^{y-1}-5^{x-1}=5^{x-1}(5^{y-x}-1)$$ so we have $$B-A=5^{x-1}\\5(B+A)=5^{y-x}+2\hspace1cm(*)$$ The second equation $(*)$ leads to the absurd $2\equiv0\pmod5$ or $3\equiv0\pmod5$. This finishes the proof.

$\endgroup$
2
  • $\begingroup$ Good solution. But this method only works because we have $a^2$. The higher the power the harder solving the problem becomes to this method. $\endgroup$
    – PNT
    Commented Dec 1, 2022 at 19:43
  • $\begingroup$ Actually this problem is just a weak version of India TST 2019. You can try solving it using this approach. $\endgroup$
    – PNT
    Commented Dec 1, 2022 at 19:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .