Argument for why $a^2 + 1$ is never divisible by a $3 \mod 4$ integer How do you show that $$a^2 + 1$$ is never divisible by a $3 \mod 4$ integer (which is equivalent to showing that it has no $3 \mod 4$ prime factor) for any non-negative integer $a$ by analysing the arithmetic series representation of $a^2$, $1 + 3 + 5 + ... + (2a-1)$?
 A: Suppose $a \in \mathbb{Z}$ is such that $p\mid (a^2+1)$, where $p$ is prime, and $p \equiv -1 \pmod 4$.

Since $p\mid (a^2+1)$, it follows that $p \not\mid a$, hence $\gcd(a,p)=1$.
\begin{align*}
\text{Then}\;\;&p\mid (a^2+1)\\[4pt]
\implies\;&a^2\equiv -1\pmod p\\[4pt]
\implies\;&(a^2)^\frac{p-1}{2}\equiv -1\pmod p
&&\text{[since $\small{\frac{p-1}{2}}$ is odd]}\\[4pt]
\implies\;&a^{p-1}\equiv -1\pmod p\\[4pt]
\implies\;&1\equiv -1\pmod p
&&\text{[by Fermat's little Theorem]}\\[4pt]
\implies\;&2\equiv 0\pmod p\\[4pt]
\end{align*}
contradiction.

Hmmm . . .

I didn't see the end of your question. It looks like you want a different kind of proof. In any case, the proof I gave above, using Fermat's little Theorem, is an easy way to prove the claim.
A: Use congruences:
$a^2+1$ divisible by $p$ means  $a^2\equiv -1\mod p$. In other words $-1$ is a square modulo $p$.
If you know the first supplementary law of the law of quadratic reciprocity, you know it is impossible if $p\equiv 3\mod 4$.
If you don't know it, here is a sketch:
If $-1\equiv a^2\mod p$, *Lil' Fermat says that $a^{p-1}\equiv 1\mod p$. However, as $p$ is odd,
$$a^{p-1}=\bigl(a^2\bigr)^\tfrac{p-1}2=(-1)^\tfrac{p-1}2\equiv 1\mod p,$$
and this is impossible as $\dfrac{p-1}2$ is odd if $p\equiv 3\mod 4$.
A: Not using the series: 


*

*Case 1: $a$ is even, say, $a=2k$. Then $a^2+1 = 4k^2 + 1$.

*Case 2: $a$ is odd, say, $a=2k+1$. Then $a^2+1 = 4k^2+4k+2$.


Using the series $a^2=1+3+5+...+(2a-5)+(2a-3)+(2a-1)$. 


*

*Note that consecutive terms add to multiples of $4$. 

*Therefore, $a^2$ is either $(1+3)+(5+7)+...+((2a-3)+(2a-1))$, which is a sum of multiples of 4, or $1 + (3+5)+(7+9)+...+((2a-3)+(2a-1))$, which is one more than a multiple of $4$.

*in any case, the result follows for $a^2+1$


Explicitly in $\mathbb{Z}_4$:


*

*$a$ is either 0, 1, 2 or 3. Therefore $a^2$ is either 0 or 1, so $a^2+1$ is 1 or 2.

