Proving expressions mod 13

Question

Bob thinks of integer pairs $(a,b)$ such that $a^2+b^2\equiv 0\pmod {13}$

He notices that, curiously, for every pair, at least one of $2a+3b$ or $3b+2a$ is divisible by $13$.

I did a similar problem to prove that $13|2a+3b\iff 13|3a-2b$ using a special algebra trick.

I cannot find a trick here though to manipulate the expressions.

I can solve it by looking at all possible values of $a^2\pmod {13}$ and then verifying that these work.

But I want to know if there is a more elegant solution using an algebra trick.

Answer 1

Hint: If $a\equiv 0\pmod{13}$ then $b\equiv 0\bmod 13$ as well. Now, assume this is not the case. Then

$$a^2+b^2\equiv 0\bmod 13 \implies \left(\frac{a}{b}\right)^2+1\equiv 0\bmod 13.$$

See that the square roots of $-1\bmod 13$ are $5$ and $8$, or, if you prefer, $-2/3$ and $-3/2$...

Can you finish from here?

Answer 2

From $13|2a+3b\iff 13|3a-2b$, we can write \begin{align*} (3a-2b)(3a+2b) = 9a^2 - 4b^2 = -4(a^2+b^2) \mod 13 = 0 \mod 13 \end{align*} Hence either $3a-2b$ or $3a+2b$ is a multiple of 13. It follows that either $2a+3b$ or $3a+2b$ is a multiple of 13.