Baltic Way 2021 · Problem 16

If we use the Diophantus sum of squares equality

$$(a x-b y)^{2}+(a y+b x)^{2}=\left(a^{2}+b^{2}\right)\left(x^{2}+y^{2}\right)$$

then we can see that for a system

$$\left\{\begin{array}{l} a x-b y=s \\ a y+b x=t \end{array}\right.$$

to have a solution in positive integers the number $s^{2}+t^{2}$ must be a composite number.

The number corresponding to the equation, $16^{2}+1^{2}=257$, is a prime number. This shows that no solution can exist in non-zero integers, as it would give a factorisation of the prime with each factor $>1$.

Remark. Note that $(a+b i)(x+y i)=(a x-b y)+(a y+b x) i$. Finding a solution to the system of equations is therefore equivalent to finding a factorization of $s+t i$ in Gaussian integers $\mathbb{Z}[i]$ with non-negative real and imaginary component. It is known that the Gaussian integers form a Euclidean domain and hence a unique factorization domain. The form for primes in $\mathbb{Z}[i]$ has been thoroughly studied.