<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] I like to write it this way: $p$ is assumed to be a prime that divides both $m^2 - n^2$ and $m^2 + n^2.$ Then $p$ divides their sum, so $p | 2 m^2$ and $p|2m.$ Either $p=2$ or $p |m.$
Also $p$ divides their difference, so $p | 2 n^2$ and $p|2n.$ Either $p=2$ or $p |n.$
If $p \neq 2,$ then $p$ divides both $m,n.$ We know this is a contradiction because $\gcd(m,n) = 1.$
Finally, try $p=2.$ This fails as well, because $m+n,$ and so $m-n,$ are odd, thence $m^2 - n^2$ is odd and not divisible by $2.$
There you have it, we have contradicted the assumption that there is any prime $p$ that divides both $m^2 - n^2$ and $m^2 + n^2,$ therefore $\gcd(m^2 - n^2, m^2 + n^2) = 1.$
</s>