[proofplan]
We prove the contrapositive obstruction: modulo a prime $q \equiv 3 \pmod 4$, no integer $x$ satisfying $q \nmid x$ can solve the congruence $x^2 \equiv -1 \pmod q$. This follows from the elementary Fermat congruence $x^{q-1} \equiv 1 \pmod q$, proved here by permuting nonzero residue classes modulo $q$. If either $a$ or $b$ were not divisible by $q$, the hypothesis $q \mid a^2+b^2$ would produce such a square root of $-1$ modulo $q$, giving a contradiction.
[/proofplan]
[step:Show that $-1$ has no square root modulo a prime $q \equiv 3 \pmod 4$]
We first prove the auxiliary fact that if $x \in \mathbb{Z}$ and $q \nmid x$, then $x^{q-1} \equiv 1 \pmod q$. Since $q$ is prime and $q \nmid x$, multiplication by $x$ permutes the nonzero residue classes $1,2,\dots,q-1$ modulo $q$. Hence
\begin{align*}
x \cdot 2x \cdots (q-1)x \equiv 1 \cdot 2 \cdots (q-1) \pmod q.
\end{align*}
Equivalently,
\begin{align*}
x^{q-1}(q-1)! \equiv (q-1)! \pmod q.
\end{align*}
Because no integer among $1,\dots,q-1$ is divisible by $q$, the product $(q-1)!$ is invertible modulo $q$, so cancellation gives
\begin{align*}
x^{q-1} \equiv 1 \pmod q.
\end{align*}
Now suppose, toward a contradiction, that there exists $x \in \mathbb{Z}$ with $q \nmid x$ and
\begin{align*}
x^2 \equiv -1 \pmod q.
\end{align*}
Since $q \equiv 3 \pmod 4$, there exists $m \in \mathbb{Z}$ such that $q = 4m+3$, so
\begin{align*}
\frac{q-1}{2} = 2m+1
\end{align*}
is odd. Raising the congruence $x^2 \equiv -1 \pmod q$ to the power $(q-1)/2$ gives
\begin{align*}
x^{q-1} \equiv (-1)^{(q-1)/2} = -1 \pmod q.
\end{align*}
This contradicts the previously proved congruence $x^{q-1} \equiv 1 \pmod q$. Therefore no such integer $x$ exists.
[guided]
The key obstruction is that a square root of $-1$ modulo $q$ would force two incompatible values for $x^{q-1}$. First we prove the elementary Fermat congruence needed for this comparison. Let $x \in \mathbb{Z}$ satisfy $q \nmid x$. Because $q$ is prime, $x$ is invertible modulo $q$, so the map on nonzero residue classes
\begin{align*}
r \mapsto xr \pmod q
\end{align*}
is a permutation of the set $\{1,2,\dots,q-1\}$ modulo $q$. Multiplying all entries in this permuted list gives
\begin{align*}
x \cdot 2x \cdots (q-1)x \equiv 1 \cdot 2 \cdots (q-1) \pmod q,
\end{align*}
and therefore
\begin{align*}
x^{q-1}(q-1)! \equiv (q-1)! \pmod q.
\end{align*}
The integer $(q-1)!$ is not divisible by $q$, since each factor $1,\dots,q-1$ is nonzero modulo the prime $q$. Thus $(q-1)!$ has a multiplicative inverse modulo $q$, and cancellation gives
\begin{align*}
x^{q-1} \equiv 1 \pmod q.
\end{align*}
Now assume that $x^2 \equiv -1 \pmod q$ for some $x \in \mathbb{Z}$ with $q \nmid x$. The congruence condition $q \equiv 3 \pmod 4$ means that $q = 4m+3$ for some $m \in \mathbb{Z}$, hence
\begin{align*}
\frac{q-1}{2} = 2m+1
\end{align*}
is odd. Raising $x^2 \equiv -1 \pmod q$ to this odd power yields
\begin{align*}
x^{q-1} = (x^2)^{(q-1)/2} \equiv (-1)^{(q-1)/2} = -1 \pmod q.
\end{align*}
This contradicts the Fermat congruence $x^{q-1} \equiv 1 \pmod q$. Therefore $-1$ is not a square modulo $q$ among residue classes represented by integers not divisible by $q$.
[/guided]
[/step]
[step:Rule out the possibility that $b$ is not divisible by $q$]
Assume $q \mid a^2+b^2$. Suppose, toward a contradiction, that $q \nmid b$. Since $q$ is prime and $q \nmid b$, there exists $c \in \mathbb{Z}$ such that
\begin{align*}
bc \equiv 1 \pmod q.
\end{align*}
From $q \mid a^2+b^2$ we have
\begin{align*}
a^2+b^2 \equiv 0 \pmod q.
\end{align*}
Multiplying this congruence by $c^2$ gives
\begin{align*}
(ac)^2 + (bc)^2 \equiv 0 \pmod q.
\end{align*}
Since $bc \equiv 1 \pmod q$, this becomes
\begin{align*}
(ac)^2 \equiv -1 \pmod q.
\end{align*}
Also $q \nmid ac$, because $q \mid ac$ together with $bc \equiv 1 \pmod q$ would imply $0 \equiv ac \cdot b \equiv a \pmod q$, and the congruence above would then give $0 \equiv -1 \pmod q$, impossible. Thus $ac$ is a square root of $-1$ modulo $q$ represented by an integer not divisible by $q$, contradicting the previous step. Therefore $q \mid b$.
[guided]
We now use the hypothesis $q \mid a^2+b^2$ to manufacture a square root of $-1$ modulo $q$, assuming that $b$ is invertible modulo $q$. Suppose $q \nmid b$. Since $q$ is prime, this is equivalent to $\gcd(b,q)=1$, so there exists $c \in \mathbb{Z}$ with
\begin{align*}
bc \equiv 1 \pmod q.
\end{align*}
This integer $c$ is a multiplicative inverse of $b$ modulo $q$.
The divisibility assumption gives
\begin{align*}
a^2+b^2 \equiv 0 \pmod q.
\end{align*}
Multiplying by $c^2$ is valid because congruences may be multiplied by any integer. We obtain
\begin{align*}
(ac)^2 + (bc)^2 \equiv 0 \pmod q.
\end{align*}
Since $bc \equiv 1 \pmod q$, the second term satisfies $(bc)^2 \equiv 1 \pmod q$, and hence
\begin{align*}
(ac)^2 \equiv -1 \pmod q.
\end{align*}
This is exactly the forbidden type of congruence from the previous step, provided the integer $ac$ is not divisible by $q$. If $q \mid ac$, then multiplying by $b$ gives $q \mid abc$. But $bc \equiv 1 \pmod q$, so $abc \equiv a \pmod q$, and hence $q \mid a$. Then $q \mid a$ and $q \mid b^2$ would follow from $a^2+b^2 \equiv 0 \pmod q$, contradicting $q \nmid b$ because $q$ is prime. Thus $q \nmid ac$. Therefore $(ac)^2 \equiv -1 \pmod q$ contradicts the result that $-1$ has no square root modulo $q$. We conclude that the assumption $q \nmid b$ is impossible, so $q \mid b$.
[/guided]
[/step]
[step:Use the original congruence to force $q \mid a$]
Since $q \mid b$, there exists $k \in \mathbb{Z}$ such that $b = qk$, and therefore $q \mid b^2$. From $q \mid a^2+b^2$ and $q \mid b^2$, subtracting divisibilities gives $q \mid a^2$. Because $q$ is prime, $q \mid a^2$ implies $q \mid a$. Together with $q \mid b$, this proves the desired conclusion.
[/step]
