Results 1 to 3 of 3

Math Help - Suppose that m,n,q,r are integers satisfying n=mq+r. Then gcd(m,n)=gcd(m,r).

  1. #1
    Newbie
    Joined
    Mar 2013
    From
    United States
    Posts
    2

    Suppose that m,n,q,r are integers satisfying n=mq+r. Then gcd(m,n)=gcd(m,r).

    Suppose that m,n,q,r are integers satisfying the identity n=mq+r. Then gcd(m,n)=gcd(m,r).

    Let gcd(m,n)=k where k is some integer, then k|m and k|n. n=mq+r can be expressed as r=n-mq=k|n+k|m. Therefore k|r.
    Let gcd(m,r)=p where p is some integer, then p|m and p|r. n=mq+r=p|m+p|r. Therefore p|n.

    Therefore, p|m,n,r and k|m,n,r.

    Next step is where my notes do not make sense for me.

    If k|m and p|m then kx=m and py=m for some integers x and y. Therefore kx=py and k=p. Q.E.D.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778

    Re: Suppose that m,n,q,r are integers satisfying n=mq+r. Then gcd(m,n)=gcd(m,r).

    Quote Originally Posted by mokaro View Post
    n=mq+r can be expressed as r=n-mq=k|n+k|m.
    One cannot write k | n + k | m. Indeed, k | n is not a number; it is either true or false depending on whether k divides n. Addition is not defined on Boolean values (true and false). Instead, you could write, "Since k | n and k | m, we have k | (mq) and therefore k | (n - mq)".

    Quote Originally Posted by mokaro View Post
    Next step is where my notes do not make sense for me.

    If k|m and p|m then kx=m and py=m for some integers x and y. Therefore kx=py and k=p. Q.E.D.
    The conclusion k = p does not make sense to me either. Your proof showed that every common divisor (not just GCD) of n and m is a also a common divisor of m and r and vice versa, i.e., the sets of common divisors of (n, m) and (m, r) are the same. Therefore, the maximums of these sets are also the same, i.e., the gcd(n, m) = gcd(m, r).

    More generally, call r a linear combination of n and m if r = an + bm for some integers a and b. So, if r is a linear combination of n and m, then every common divisor of n and m is also a divisor of r. Similarly, if r and p are two linear combinations of n and m, then every common divisor of n and m is also a common divisor of r and p. Therefore, if r, p are linear combinations of n, m and, vice versa, n, m are linear combinations of r, p, then gcd(n, m) = gcd(r, p). Now, if n = mq + r, then m = 0 * n + 1 * m and r = 1 * n + (-q) * m are linear combinations of n and m. Conversely, n and m are linear combinations of m and r. By the claim above, their GCDs are the same.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2013
    From
    United States
    Posts
    2

    Re: Suppose that m,n,q,r are integers satisfying n=mq+r. Then gcd(m,n)=gcd(m,r).

    Love it. Thanks buddy. Very thorough and clear.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: March 22nd 2012, 08:45 PM
  2. measure of set satisfying ~CH
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: July 1st 2011, 09:26 PM
  3. Replies: 6
    Last Post: March 2nd 2011, 12:36 AM
  4. Replies: 7
    Last Post: August 3rd 2010, 01:31 PM
  5. Replies: 1
    Last Post: August 1st 2010, 08:40 PM

Search Tags


/mathhelpforum @mathhelpforum