# Greatest Common Divisor Proof

• Mar 15th 2011, 03:49 PM
jstarks44444
Greatest Common Divisor Proof
Some help with the following proof would be appreciated:

Prove that for all k,m,n in the set of Integers,

gcd(km, kn) = |k|gcd(m, n)

We have the following propositions already at our disposal.
*Every integer >= 2 can be factored into primes.
*Let m,n be in the Integers:
- gcd(m, n) divides both m and n
- unless m and n are both 0, gcd(m, n) > 0
- every integer that divides both m and n also divides gcd(m, n)
• Mar 15th 2011, 04:00 PM
dwsmith
Quote:

Originally Posted by jstarks44444
Some help with the following proof would be appreciated:

Prove that for all k,m,n in the set of Integers,

gcd(km, kn) = |k|gcd(m, n)

We have the following propositions already at our disposal.
*Every integer >= 2 can be factored into primes.
*Let m,n be in the Integers:
- gcd(m, n) divides both m and n
- unless m and n are both 0, gcd(m, n) > 0
- every integer that divides both m and n also divides gcd(m, n)

$gcd(m,n)=am+bn$

$k\times gcd(m,n)=a(km)+b(kn)$

$k\times gcd(m,n)=gcd(km, kn)$