<s>[INST] Greatest Common Divisor Proof: $\gcd(m^2-n^2, m^2+n^2) = 1$ Prove that if $\gcd(m,n) = 1$ and $m+n \equiv 1 (\text{mod} ~2)$ then $\gcd(m^2-n^2, m^2+n^2) = 1$
Workings:
Suppose that $\gcd(m,n) = 1$ and $m+n \equiv 1 (\text{mod} ~2)$
$\gcd(m^2-n^2, m^2+n^2)$
$= gcd((m-n)(m+n), (m-n)(m+n)+2n^2)$
Now I know that $m+n=1 (\text{mod} ~2)$ means that one of $m$ or $n$ is odd or even
But now I'm not too sure on what to do.
Any help will be appreciated.
 [/INST] If $m+n\equiv 1 \bmod 2$, then $m-n\equiv 1 \bmod 2$, so $m^2-n^2\equiv 1 \bmod 2$, and $m^2+n^2=m^2-n^2+2n^2\equiv 1\bmod 2$.
If $d\mid m^2-n^2$ and $d\mid m^2+n^2$, then $d\mid 2m^2$ and $d\mid 2n^2$.
Since both $m^2+n^2$ and $m^2-n^2$ are odd, $d$ is not even, so $d\mid m^2$ and $d\mid n^2$, which implies $d\mid m$ and $d\mid n$, so $d=1$.
</s>