# How to prove $\gcd(m, n) = \gcd(-m, n)?$

Beginner question here:

For a quiz on Elementary Number Theory in my Discrete Math course I was asked to prove if $\gcd(m, n) = \gcd(-m, n)$. I used the Euclidean Algorithm to show that the two expressions simplify to $\gcd(n,\ m\pmod{n})$ and $\gcd(n,\ -m\pmod{n})$ respectively. Then I went on to show (well I tried... but that's another question) that $-m\pmod{n} = m\pmod{n}$.

If I was able to do this correctly, does this approach result in a valid proof? If not, is there a different/better way to do it?

Thanks!

-
definition is enough! – Ehsan M. Kermani Dec 18 '11 at 4:25
Note that $-1 \equiv 3 (mod 4)$ while $1 \equiv 1 (mod 4)$. So, $-m$ (mod n) $\neq$ $m$ (mod n) in general. – Rankeya Dec 18 '11 at 4:25
It's not generally true that for two non-zero integers $m,n$ the equivalence $m \equiv -m \mod n$ holds. Try 1 and 3 for example. – jspecter Dec 18 '11 at 4:27
Oh wow, I didn't even realize that! Thank you! – chandsie Dec 18 '11 at 15:43

HINT $\rm\ \ d\ |\ m,\:n\ \iff\ d\ |\ {-}m,\:n\:.\:$ Thus $\rm\ m,n\$ and $\rm\: -m,n\$ have the same set of common divisors $\rm\:d\:$ hence the same greatest common divisor. $\$ QED

Alternatively it's a special case $\rm\ k=-1\$ in $\rm\ (k\:m,\:n)\ =\ ((k,n)\:m,\:n)\$

Proof $\rm\quad\ \ (km,n)\ =\ (km,n(m,1))\ =\ (km,nm,n)\ =\ ((k,n)m,n)$

The above proof uses only basic gcd laws (associative, commutative, distributive) - see here.

Euclid's Lemma is the case $\rm\ (k,n) = 1\ \Rightarrow\ (k\:m,\:n)\ =\ (m,\:n)$

-

The easiest way is simply to observe that $m$ and $-m$ have exactly the same divisors: $d\mid m$ iff there is an integer $k$ such that $m=kd$ iff $-m=(-k)d$ iff $d\mid -m$, and $-k$ is an integer iff $k$ is an integer. Thus, the common divisors of $m$ and $n$ are exactly the same as the common divisors of $-m$ and $n$, and hence $\gcd(m,n)=\gcd(-m,n)$.

-

So here is really a simple answer that should follow by definition:

Let $d = \gcd(m, n)$ and $d' = \gcd(-m,n)$. By definition of a gcd, $d| m,n$. So, $d|-m,n$. Hence, $d|d'$. Similarly one can show that $d'|d$. Then $d= \pm d'$. But, GCDs in $\mathbb{Z}$ are positive. So, $d = d'$, because d, d' are both positive.

-
Actually, depending on how you choose to define the GCD, the assertion $d|d'$ may/may not be trivial. – Rankeya Dec 18 '11 at 4:35
In either case, Bill and Brian have better answers. So, take a look at their answers. – Rankeya Dec 18 '11 at 4:38