## Task A-2.4.

Determine all pairs of prime numbers $(p, q)$ for which $p^{q-1} + q^{p-1}$ is a square of a natural number.
## Solution.

Let $n$ be a natural number whose square is equal to the expression from the problem, i.e.,

$$
p^{q-1} + q^{p-1} = n^2
$$

We will divide the problem into separate cases based on the parity of the numbers $p$ and $q$. If both numbers are even, the only possibility is that both are 2. In this case, we get the solution $(p, q) = (2, 2)$ for $n = 2$.

If both numbers $p, q$ are odd, then by looking at the remainder when divided by 4, we conclude that there is no solution. Indeed, since $p, q$ are odd, the numbers $p-1, q-1$ are even, so the numbers $p^{q-1}, q^{p-1}$ are squares of odd numbers, which we know always give a remainder of 1 when divided by 4. Therefore, the left side gives a remainder of 2 when divided by 4, while $n^2$ gives a remainder of 1 or 0 when divided by 4.

The only remaining case is when one of the numbers $p, q$ is even, and the other is odd. Since the equation is symmetric, without loss of generality, we can assume that $p$ is odd, of the form $p = 2k + 1$ for a natural number $k$, and $q = 2$. Now we have the equation

$$
p + 2^{q-1} = n^2, \quad \text{i.e.,} \quad p = n^2 - 2^{2k} = (n - 2^k)(n + 2^k)
$$

The right side of the equation consists of two factors whose product is a prime number. This is only possible if one of the factors is $\pm 1$, and the other is $\pm p$. Also, note that $n + 2^k > 0$, and $n + 2^k > n - 2^k$, so it must be

$$
n - 2^k = 1 \quad \text{and} \quad n + 2^k = p
$$

Subtracting the last two equations, we get

$$
2^{k+1} + 1 = p = 2k + 1
$$

Let's prove that this equation has no solutions. The number $2^{k+1} + 1$, and thus the number $2k + 1$, gives a remainder of 1 when divided by 4, so $k$ must be an even number, i.e., $k = 2l$, for some non-negative integer $l$. In this case, the number

$$
p = 2^{k+1} + 1 = 2^{2l+1} + 1 = 2 \cdot 4^l + 1
$$

is divisible by 3 (since $4^l$ gives a remainder of 1 when divided by 3). Therefore, $p$ is divisible by 3, i.e., $p = 3$. Substituting into the original equation, we see that $p = 3$ and $q = 2$ is not a solution.

Thus, the only solution is $(p, q) = (2, 2)$.

Note: Another way to prove that the equation

$$
2^{k+1} + 1 = p = 2k + 1
$$

has no solutions is to show that the inequality $2^{k+1} + 1 > 2k + 1$, i.e., $2^k > k$ holds for all natural numbers $k$. This can be shown by mathematical induction or by repeated use of the inequality $2a \geqslant a + 1$:

$$
2^k = 2 \cdot 2^{k-1} \geqslant 2^{k-1} + 1 = 2 \cdot 2^{k-2} + 1 \geqslant 2^{k-2} + 2 \geqslant \cdots \geqslant 2^1 + k - 1 = k + 1 > k
$$

The inequality $2^k > k$ can also be proven by a combinatorial argument, noting that the total number of subsets is always greater than the number of one-element subsets of a $k$-element set.

The case when both prime numbers $p, q$ are odd can be resolved by noting that the numbers $p^{q-1}, q^{p-1}$ are squares, so $(p^{\frac{q-1}{2}}, q^{\frac{p-1}{2}}, n)$ is a Pythagorean triple where the first two numbers are odd, which is impossible. Alternatively, we can write

$$
p^{q-1} = (n - q^{\frac{p-1}{2}})(n + q^{\frac{p-1}{2}})
$$

Since we can show that the factors on the right side are relatively prime, similar arguments as in the solution conclude that $n = q^{\frac{p-1}{2}} + 1$. By swapping the roles of $p$ and $q$, we can conclude that $n = p^{\frac{q-1}{2}} + 1$, so we get the equality $p^{\frac{q-1}{2}} = n - 1 = q^{\frac{p-1}{2}}$. From this, it follows that $p = q$, and substituting this into the original equation, we get $2p^{p-1} = n^2$, which has no solutions for odd $p$.