4
$\begingroup$

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!

  • 0
    Oh wow, I didn't even realize that! Thank you!2011-12-18

3 Answers 3

0

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.

  • 0
    In either case, Bill and Brian have better answers. So, take a look at their answers.2011-12-18
3

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

3

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