Results 1 to 5 of 5

Math Help - Another GCD Proof

  1. #1
    Newbie
    Joined
    Mar 2013
    From
    Canada
    Posts
    2

    Another GCD Proof

    Im new to the forum so im not sure if im posting in the right section but ive been stuck on this problem for days however im not sure on how to even go about it. I would at the very least need some advice on how to tackle this problem.


    Claim: For every pair of positive natural numbers (m, n), if m >= n, then gcd(m, n) = gcd(n, m-n)



    Thanks in advance
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Another GCD Proof

    If you show that the sets of common divisors of these two pairs of numbers coincide, you automatically show that the maximums of these sets also coincide.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Feb 2011
    Posts
    83
    Thanks
    2

    Re: Another GCD Proof

    If d = gcd(m,n), then d divides ANY linear combination of m and n.


    i.e d \;| \;mx + ny \;\forall\; x,y \in \mathbb{Z}
    Last edited by Jame; March 2nd 2013 at 06:58 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Mar 2013
    From
    Canada
    Posts
    2

    Re: Another GCD Proof

    So could I say

    let d be the common divisor that is a integer

    then let n = d*i and m = d*j; j, and i being any positive integers

    since n,m and m-n should be multiples of the same divisor.

    then m-n = d*j - d*i

    then m-n = d*(j-i) ; Then let k = j-i which also represents any integer

    hence d|n and d|m and d|m-n

    would this be right?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Another GCD Proof

    What you showed is that any common divisor of m and n (including the greatest one) is also a common divisor of n and m - n. This does not show that the GCD of m and n is also the greatest common divisor of n and m - n.

    As I said, prove that the sets of common divisors coincide. I.e., show that any divisor of m and n is also a divisor of n and m - n and vice versa. Since the sets are the same, their maximums are also the same.

    You can prove a couple of facts to make this more elegant. The first fact says that any divisor of m and n is also a divisor of a linear combination of m and n. Here a linear combination of m and n is a*m + b*n for some integers a and b. Therefore, if m' and n' are two linear combinations of m and n and if d is a common divisor of m and n, then d is also a common divisor of m' and n'. Now note that n and m - n are linear combinations of m and n, and, vice versa, m and n are linear combinations of n and m - n. That would mean that the sets of divisors of these pairs are the same.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [Abstract Algebra] Anyone care to proof-read a proof?
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: December 4th 2012, 02:13 PM
  2. Replies: 5
    Last Post: October 19th 2010, 11:50 AM
  3. Replies: 0
    Last Post: June 29th 2010, 09:48 AM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 02:20 PM
  5. proof that the proof that .999_ = 1 is not a proof (version)
    Posted in the Advanced Applied Math Forum
    Replies: 4
    Last Post: April 14th 2008, 05:07 PM

Search Tags


/mathhelpforum @mathhelpforum