Prove that $n = i^2 - j^2 \iff n \neq 2 \mod4$ hints

Question

I'm trying to prove that $n = i^2 - j^2 \iff n \neq 2 \mod4$ for all integers n, I'm running into issues getting much traction on this. I know that $n \neq 2 \mod4$ can just be split up into each case but I can't really get anywhere with that. Any tips would be appreciated.

Answer 1

Hint

$(\Rightarrow)$

Is enough to know that $i^2 \equiv \{0,1\} (\mod 4)$ then $i^2-j^2 \equiv \{-1,0,1\} (\mod 4)$.

$(\Leftarrow)$

Write $n=4k+\{0,1,3\}$ and show that you can always split $n$ as a product of two integer with the same parity (see that $i+j$ and $i-j$ have the same parity).

Answer 2

To be a little picky, there is a missing quantifier in the statement to be proved. It should be:

For all $n$, there exist integers $i$ and $j$ such that $n=i^2-j^2$ if and only if $n\not\equiv2$ mod $4$.

We need to prove both directions of the "if and only if."

For the "$\Rightarrow$" direction, we use the fact that squares are congruent to $0$ or $1$ mod $4$. So if $n\equiv2$ mod $4$, then $i^2\in\{0,1\}$ mod $4$, while $n+j^2\in\{2,3\}$ mod $4$. Consequently, if there exist integers $i$ and $j$ such that $n=i^2-j^2$, then $n\not\equiv2$ mod $4$.

For the "$\Leftarrow$" direction, we need to note that $n\not\equiv2$ mod $4$ implies $n$ is either odd or a multiple of $4$. If $n=2m+1$ then $n=(m+1)^2-m^2$. If $n=4m$ then $n=(2m+1)^2-(2m-1)^2$. Consequently, if $n\not\equiv2$ mod $4$ then there exist integers $i$ and $j$ such that $n=i^2-j^2$.

Answer 3

Well, for the "$\implies$" direction, you could always take the "brute-force" way:

• $[i\equiv0\pmod4]\wedge[j\equiv0\pmod4]\implies[i^2-j^2\equiv0-0\equiv0\not\equiv2\pmod4]$
• $[i\equiv0\pmod4]\wedge[j\equiv1\pmod4]\implies[i^2-j^2\equiv0-1\equiv3\not\equiv2\pmod4]$
• $[i\equiv0\pmod4]\wedge[j\equiv2\pmod4]\implies[i^2-j^2\equiv0-4\equiv0\not\equiv2\pmod4]$
• $[i\equiv0\pmod4]\wedge[j\equiv3\pmod4]\implies[i^2-j^2\equiv0-9\equiv3\not\equiv2\pmod4]$
• $[i\equiv1\pmod4]\wedge[j\equiv0\pmod4]\implies[i^2-j^2\equiv1-0\equiv1\not\equiv2\pmod4]$
• $[i\equiv1\pmod4]\wedge[j\equiv1\pmod4]\implies[i^2-j^2\equiv1-1\equiv0\not\equiv2\pmod4]$
• $[i\equiv1\pmod4]\wedge[j\equiv2\pmod4]\implies[i^2-j^2\equiv1-4\equiv1\not\equiv2\pmod4]$
• $[i\equiv1\pmod4]\wedge[j\equiv3\pmod4]\implies[i^2-j^2\equiv1-9\equiv0\not\equiv2\pmod4]$
• $[i\equiv2\pmod4]\wedge[j\equiv0\pmod4]\implies[i^2-j^2\equiv4-0\equiv0\not\equiv2\pmod4]$
• $[i\equiv2\pmod4]\wedge[j\equiv1\pmod4]\implies[i^2-j^2\equiv4-1\equiv3\not\equiv2\pmod4]$
• $[i\equiv2\pmod4]\wedge[j\equiv2\pmod4]\implies[i^2-j^2\equiv4-4\equiv0\not\equiv2\pmod4]$
• $[i\equiv2\pmod4]\wedge[j\equiv3\pmod4]\implies[i^2-j^2\equiv4-9\equiv3\not\equiv2\pmod4]$
• $[i\equiv3\pmod4]\wedge[j\equiv0\pmod4]\implies[i^2-j^2\equiv9-0\equiv1\not\equiv2\pmod4]$
• $[i\equiv3\pmod4]\wedge[j\equiv1\pmod4]\implies[i^2-j^2\equiv9-1\equiv0\not\equiv2\pmod4]$
• $[i\equiv3\pmod4]\wedge[j\equiv2\pmod4]\implies[i^2-j^2\equiv9-4\equiv1\not\equiv2\pmod4]$
• $[i\equiv3\pmod4]\wedge[j\equiv3\pmod4]\implies[i^2-j^2\equiv9-9\equiv0\not\equiv2\pmod4]$