Greatest Common Divisor Proof: $\gcd(m^2-n^2, m^2+n^2) = 1$

Question

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.

Answer 1

Euclid's algorithm gives: \begin{align*} \gcd(m^2 - n^2, m^2 + n^2) &= \gcd(m^2 - n^2, (m^2 + n^2) - (m^2 - n^2)) \\ &= \gcd(m^2 - n^2, 2n^2) \end{align*} Since $m + n \equiv 1 \pmod{2}$, $m^2 - n^2 \equiv 1 \pmod{2}$, so we can forget about the $2$. We get \begin{align*} &= \gcd(m^2 - n^2, n^2) \\ &= \gcd(m^2, n^2) \\ &= 1. \end{align*}

Answer 2

We can make use of the fact that $\gcd(a, b) = \gcd(a, b-ka)$ for any integer $k$. Note that $\gcd(m^2 - n^2, m^2 + n^2) = \gcd(m^2 - n^2, 2n^2).$ You noted that one of $m, n$ is odd and one is even, so $2 \nmid m^2 -n ^2$. So $$\gcd(m^2 - n^2, 2n^2) = \gcd(m^2 - n^2, n^2) (\text{why?}) = \gcd(m^2, n^2).$$

From there, you can argue that this gcd must be 1.

Answer 3

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

Answer 4

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