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!
Best Answer
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)$