Let $a, b$ be positive integers. Prove that if $a^b + b^a \equiv 3 \pmod{4}$, then either $a+1$ or $b+1$ can't be written as the sum of two integer squares. (Proposed by Orestis Lignos, Greece)
Problem
Source: 2024 Nepal TST P1
Tags: number theory, Parity, modular arithmetic
12.04.2024 17:35
First, let's consider when $a \neq 1, b \neq 1$. If $a \equiv 0\mod{2}$, we have $a^b \equiv 0\mod{4} \implies b^a \equiv 3\mod{4}$. Clearly, this means $b \equiv 3\mod{4}$, however $a$ is even which means $b^a \equiv 1\mod{4}$, so this is impossible. If $a \equiv 1\mod{2}$, $a^b \equiv 1\mod{4} \implies b^a \equiv 2\mod{4}$, which means $b \equiv 2\mod{4}$, however $a > 1$ so this impossible. Clearly $a = b= 1$ is impossible also, so let's consider when $a = 1$. This means $b \equiv 2\mod{4}$, so $b + 1 \equiv 3\mod{4}$, however all squares are $1, 0 \mod{4}$, so $x^2 + y^2 \equiv 0,1,2 \mod{4}$, hence this is not possible.
12.04.2024 19:13
We check cases. Firstly, observe that $a^b+b^a=4k+3\implies$ that it is odd. Therefore, both $a$ and $b$ cannot be odd, and neither can both of them be even. Thus we only need to check the case when one is odd and one even. Without loss of generality, let us assume that $a$ is odd, and $b$ is even. Then $a=2x+1$, $b=2y$ for some integers $x$ and $y$. Let us assume $a>1$. Then, $$a^b + b^a \equiv 3\pmod{4}\implies a^{2y}+b^{2x+1}\equiv 3 \pmod{4}$$As $a$ is odd, $a^{2x}\equiv 1\pmod{4}$ and as $b$ is even, $b^{2x+1}\equiv 0\pmod{4}$, (as $a>1)$. Then, $a^{2y}+b^{2x+1}\equiv 1 \pmod{4}$, which is a contradiction! Therefore, $a=1$. Then the problem reduces to $b+1\equiv 3\pmod{4}$. Let us assume $b+1$ can be written as a sum of two squares $p^2$ and $q^2$, i.e, $b+1=p^2+q^2$, where $p$ and $q$ are positive integers. A perfect square is $\equiv 0,1\pmod{4} \implies p^2+q^2\equiv 0,1,2\pmod{4}$. But the previous congruence gives us that $b+1\equiv 3\pmod{4}$. Contradiction! Therefore, either $a+1$ or $b+1$ cannot be written as a sum of two perfect squares.
23.04.2024 11:46
Solution: We know, that for all even integers $a$ and $b$, we have, $$a,b \equiv 0,2 \pmod{4}$$This means $a, b$ must be of different parity for them to satisfy $$a^b+b^a \pmod{4} \equiv 3$$Claim 1: One of $a, b$ must be $1$. WLOG, let $a$ is even and $b$ is odd, this means, for $b>1$, we have, $$a^b +b^a \equiv 2^bk^{b} + b^{2k} \equiv 1 \pmod{4}$$which is not what we want. So, this forces $b=1$. Proved. Claim 2: $a+1$ can't be written as the sum of two squares.. $$a^b+b^a \equiv a+1 \equiv 3 \pmod{4}$$This means for any $m,n \in \mathbb{Z}$, $m^2+n^2 \pmod{4} \equiv 3$, which is not possible since the quadratic residue of $4$ is $\{0,1\}$. Proved. $\blacksquare$
20.05.2024 08:07
Lemma : If $a \equiv 3 \pmod 4$, then $a$ cannot be written as the sum of two squares. Suppose by contradiction that it is possible and write $a = x^2 + y^2$ for some positive integers $x,y$. Since $x^2 \in {0,1} \pmod{4}$ (and similarly for y), then the sum $x^2 + y^2$ is at most $2 \pmod{4}$, which is a contradiction to our initial assumption. We know check cases on our initial problem, note that by symmetry we only have to go through 2 cases, rather than the 4 (For example, $a^b \equiv 3 \pmod 4$ and $b^a \equiv 0 \pmod 4$ is treated the same way as $b^a \equiv 3 \pmod 4$ and $a^b \equiv 0 \pmod 4$ Case 1 : $a^b \equiv 3 \pmod 4$ and $b^a \equiv 0 \pmod 4$ We actually show that this case is not possible, since $b^a \equiv 0 \pmod 4$, then $b$ is even. Write $b = 2k$, we thus have $a^b \equiv a^{2k} \equiv (a^k)^2 \equiv 3 \pmod 4$ which is not possible (Recall that $x^2 \in {0,1} \pmod{4}$, for any positive integer $x$) Case 2 : $a^b \equiv 1 \pmod 4$ and $b^a \equiv 2 \pmod 4$ $b^a \equiv 2 \pmod 4$ implies that $b$ is even, but is not divisible by 4 ! Hence $a = 1$, thus we have $b \equiv 2 \pmod 4$ and hence $b + 1 \equiv 3 \pmod 4$ which concludes by our above lemma.
26.07.2024 12:30
It is too obvious that one of $a$ or $b$ is even and the other is odd suppose $a=0 (mod2)$ we get $b^a=1 (mod4)$ then $a^b=2 (mod4)$ so $b=1$ so $a+1=3 (mod4)$ and any number $x=3 (mod 4)$ can't written as a sum of two squares and we are done