Results 1 to 4 of 4

Math Help - prove that c is negative if c = xa + yb < gcd(a, b)

  1. #1
    bbq
    bbq is offline
    Newbie
    Joined
    May 2008
    Posts
    2

    prove that c is negative if c = xa + yb < gcd(a, b)

    for a, b, c, x, y Є Z and a, b != 0

    How do I approach this question?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    May 2008
    Posts
    23
    It is very similar to the proof that shows for all d>0 where d is a common divisor of a,b\epsilon Z that d=gcd(a,b) if and only if  d=x*b*ya for some x,y \epsilon Z

    Prove that c is negative if c=xa+yb<gcd(a,b).

    Proof:

    Suppose c=xb+ya for some x,y \epsilon Z

    Any common divisor d of a,b divides xb+ya \implies d|c
    Since d|c we know that |d| is less than or equal to |c|. This means that gcd(a,b)=|c|<gcd(a,b). This means that c must be -gcd(a,b), and since gcd(a,b) is always positive, then c must be negative.

    Where gcd = greatest common divisor
    |c|= magnitude of c

    I am not guaranteeing its correctness but this is the basic idea... you may have to be more descriptive in areas.
    Last edited by SaxyTimmy; June 1st 2008 at 06:28 AM. Reason: Made a mistake or two grammarically.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2008
    Posts
    7
    Quote Originally Posted by SaxyTimmy View Post
    This means that gcd(a,b)=|c|<gcd(a,b).
    I think you've made a small mistake here. What I think you meant to say was:

    |c| = gcd(a,b)
    c < gcd(a,b) (What the question is asking to prove.)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    May 2008
    Posts
    23
    No, I am pretty sure that I answered the question as it was asked. I proved that c must be negative if it was less than gcd(a,b)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. problem in negative negative exponential distribution
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: July 4th 2011, 08:29 AM
  2. [SOLVED] Prove that y goes to negative infinity
    Posted in the Differential Equations Forum
    Replies: 0
    Last Post: June 11th 2011, 05:02 AM
  3. Replies: 2
    Last Post: March 26th 2009, 05:30 PM
  4. Replies: 5
    Last Post: March 26th 2009, 03:36 PM
  5. negative fractions to negative exponents
    Posted in the Algebra Forum
    Replies: 2
    Last Post: September 24th 2006, 06:02 PM

Search Tags


/mathhelpforum @mathhelpforum