Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
2  
definition is enough! –  Ehsan M. Kermani Dec 18 '11 at 4:25
1  
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
3  
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

3 Answers 3

up vote 3 down vote accepted

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

share|improve this answer

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

share|improve this answer

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.

share|improve this answer
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.