Results 1 to 2 of 2

Math Help - Greatest Common Divisor Proof

  1. #1
    Member
    Joined
    Nov 2010
    Posts
    86

    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)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Quote Originally Posted by jstarks44444 View Post
    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)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Greatest common divisor proof
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: September 25th 2011, 04:35 PM
  2. Greatest Common Divisor of (9m+8, 6m+5)
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: January 15th 2011, 05:43 AM
  3. [SOLVED] Least common multiple - Greatest common divisor
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: October 25th 2010, 05:45 AM
  4. Greatest common divisor
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: April 18th 2010, 03:16 PM
  5. Greatest common divisor Proof (very hard!)
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: August 26th 2009, 03:19 PM

Search Tags


/mathhelpforum @mathhelpforum