Results 1 to 3 of 3

Math Help - gcd proofs:

  1. #1
    Newbie
    Joined
    Dec 2007
    Posts
    4

    gcd proofs:

    I'm kinda just starting out in this sort of stuff, and i'm rather confused. The professor assigned us to prove these. Not really sure how to start it to be honest. If I could see how these things get solved I think i'll understand it much better.

    1. If a and b are 2 positive integers show that gcd(a,b) = gcd(a - b, b)

    2. if a and b are 2 positive integers show taht gcd(a,b) = gcd(a, a +b)

    3. show that gcd(fn,fn+1) = 1 for all natural numbers n.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by Mr.Obson View Post
    1. If a and b are 2 positive integers show that gcd(a,b) = gcd(a - b, b)
    Say a > b >0 . Let gcd(a,b) = d. Now we compute gcd(a - b, b), we claim d is a common divisor. Indeed, d|(a-b) because d|a and d|b. Now we claim that if d' is a larger divisor then d'|(a-b) and d'|b implies d'|(a-b + b) thus d'|a, so d'|a, so d' is a common divisor to a and b so d' <= d.
    2. if a and b are 2 positive integers show taht gcd(a,b) = gcd(a, a +b)
    Same ideal
    3. show that gcd(fn,fn+1) = 1 for all natural numbers n.
    Use induction.
    The inductive step if f_n+1 = f_n + f_n-1
    But gcd(f_n,f_n-1) = 1 so gcd (f_n+1,f_n)=1 by Euclid's algorithm .
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Dec 2007
    Posts
    4
    wow, thx it all makes a lot more sense now
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. proofs
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 2nd 2010, 04:54 AM
  2. lim sup and lim inf proofs
    Posted in the Differential Geometry Forum
    Replies: 6
    Last Post: February 24th 2010, 08:02 PM
  3. More Proofs
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: February 13th 2008, 08:05 PM
  4. Proofs
    Posted in the Calculus Forum
    Replies: 1
    Last Post: February 3rd 2008, 05:23 AM
  5. Replies: 3
    Last Post: October 6th 2007, 03:01 PM

Search Tags


/mathhelpforum @mathhelpforum