Results 1 to 3 of 3

Math Help - another gcd property

  1. #1
    Newbie
    Joined
    Jul 2011
    Posts
    10

    another gcd property

    Let a, b be integers, not both equal to zero, d = min\{ax + by|x, y \in Z\}. Prove d = gcd(a, b)

    Attempt: I can do final part of proof: If d | a and d | b, then d | gcd(a, b). From \exists x_0, y_0, s.t. d = ax_0 + by_0 we have gcd(a,b) | d. From gcd(a,b) | d and d | gcd(a,b) finally d = gcd(a,b).

    But I can't prove that d | a and d | b.

    Can anyone help please? Thank you!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773

    Re: another gcd property

    Assume that a gives a remainder 0 < r < d when divided by d and prove that r is a linear combination of a and b smaller than d.

    You need to make a restriction that some numbers are positive in this problem because d = min{ax + by | x, y in Z} does not exist.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jul 2011
    Posts
    10

    Re: another gcd property

    thanks very much! This forum is great!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] gcd property
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: July 22nd 2011, 04:02 AM
  2. Mean Value Property Implies "Volume" Mean Value Property
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: March 16th 2011, 08:13 PM
  3. set property help
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: June 28th 2010, 04:09 AM
  4. One-To-One Property
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: September 28th 2009, 02:59 PM
  5. property
    Posted in the Calculus Forum
    Replies: 1
    Last Post: July 12th 2008, 08:32 PM

/mathhelpforum @mathhelpforum