Results 1 to 8 of 8

Math Help - gcd proofs

  1. #1
    Newbie
    Joined
    Jan 2009
    Posts
    8

    gcd proofs

    Edited to add:
    Prove that for every n, gcd(n+1, n^2-n+1) is either 1 or 3.



    I'm having a lot of difficulty with some of these proofs. I'm not quite sure where to begin...

    First, If (a,b)=d, then prove (a/d, b/d)=1 (where a/d is a fraction... I can't figure out how to get the cool math symbols in here like everyone else!)
    So far I have: d/a (d divides a) and d/b, so a=dv and b=dw where v,w belong to the set of intergers. Then I can plug that in, so (a/d, b/d) becomes (v,w) but that doesn't really get me anywhere... help?

    Also, If (a,c)=1 and (b,c)=1, prove that (ab,c)=1.
    So far I have 1=av+cw for some v,w belonging to the set of intergers. Similarly, 1=bx+cz, but that's as far as I've been able to get.
    Last edited by pirouette; January 20th 2009 at 07:51 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member vincisonfire's Avatar
    Joined
    Oct 2008
    From
    Sainte-Flavie
    Posts
    469
    Thanks
    2
    Awards
    1
    You can express the GCD as ua+vb = d . More over, it is the smallest positive integer of this form.
    Divide each side by d  u\frac{a}{d}+v\frac{b}{d} = 1 This looks like the expression of a GCD. You can be sure it is because 1 is the smallest positive integer you can get.
    For number 2 you can use the fact that they have no common factors.
    For the "cool" writting, you should learn Latex script. Double-click on the things other people wrote to see how it is. With some time you should learn.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by pirouette View Post
    Also, If (a,c)=1 and (b,c)=1, prove that (ab,c)=1.
    So far I have 1=av+cw for some v,w belonging to the set of intergers. Similarly, 1=bx+cz, but that's as far as I've been able to get.
    1 = (av+cw)(bx+cz) = ab(vx) + c(avz + bwx + cwz)
    Last edited by Isomorphism; January 19th 2009 at 04:59 PM. Reason: Thanks vincisonfire
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Jan 2009
    Posts
    8
    Thanks to both of you!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Jan 2009
    Posts
    8
    Ok, I have one more that I'm having a lot of trouble with.

    Prove that for every n, gcd(n+1, n^2-n+1) is either 1 or 3.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Look at  n \mod{3} :

    Suppose  n \equiv 0 \mod{3} , then  (n+1,n^2-n+1) = (0+1,0^2-0+1) = (1,1) = 1

    Suppose  n \equiv 1 \mod{3}  , then  (n+1,n^2-n+1) = (1+1,1^2-1+1) = (2,1) = 1

    Suppose  n \equiv 2 \mod{3}  , then  (n+1,n^2-n+1) = (2+1,2^2-2+1) = (3,3) = 3

    Hence either  1 or  3 .
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by pirouette View Post
    Edited to add:
    Prove that for every n, gcd(n+1, n^2-n+1) is either 1 or 3.
    Note that if a,b are positive integers then \gcd(a+b,b)=\gcd(a,b)

    Now n^2 - n + 1 = n^2 + 2n + 1 - 3n = (n+1)^2 - 3n

    Thus, \gcd(n+1, (n+1)^2 - 3n) = \gcd(n+1, - 3n) = \gcd(n+1, - 3n + 3(n+1)) = \gcd(n+1, 3)
    And so it is 1 or 3.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Directly follows from the observation: (n^2 - n + 1) - (n-2)(n+1) = 3
    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, 03:54 AM
  2. lim sup and lim inf proofs
    Posted in the Differential Geometry Forum
    Replies: 6
    Last Post: February 24th 2010, 07:02 PM
  3. More Proofs
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: February 13th 2008, 07:05 PM
  4. Proofs
    Posted in the Calculus Forum
    Replies: 1
    Last Post: February 3rd 2008, 04:23 AM
  5. Replies: 3
    Last Post: October 6th 2007, 02:01 PM

Search Tags


/mathhelpforum @mathhelpforum