Argument for why $a^2 + 1$ is never divisible by a $3 \mod 4$ integer

Question

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)$?

Answer 1

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.

Answer 2

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.

Answer 3

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$.