Results 1 to 5 of 5

Math Help - GCD Question

  1. #1
    Junior Member
    Joined
    Jan 2009
    Posts
    27

    GCD Question

    The problem:
    Let a,b,n be integers. n >0, such that n | (a-b) [n divides (aib)].
    Show that (n,a) = (n,b) [(x,y) <==> the GCD of x and y].

    Definitions
    a | b means that b = ak + r for some integer r,k k=0;

    Lemmas
    Let a,b be integers. If a = bq+r, then (a,b) = (b,r).

    Proof:
    Since n | (a-b)
    a-b = nk for some integer k.
    a = nk + b
    Using Lemma, (a,n) = (n,b).

    I'm just wondering if there are any flaws in this proof, given I can use the lemma? I just want to make sure, seems a bit easy but my teacher is very strict and was just wondering if any of you could spot some possible criticisms.

    Thanks
    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 Th3sandm4n View Post
    The problem:
    Let a,b,n be integers. n >0, such that n | (a-b) [n divides (aib)].
    Show that (n,a) = (n,b) [(x,y) <==> the GCD of x and y].

    Definitions
    a | b means that b = ak + r for some integer r,k k=0;

    Lemmas
    Let a,b be integers. If a = bq+r, then (a,b) = (b,r).

    Proof:
    Since n | (a-b)
    a-b = nk for some integer k.
    a = nk + b
    Using Lemma, (a,n) = (n,b).

    I'm just wondering if there are any flaws in this proof, given I can use the lemma? I just want to make sure, seems a bit easy but my teacher is very strict and was just wondering if any of you could spot some possible criticisms.

    Thanks
    Look at the first problem here.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jan 2009
    Posts
    27
    Yeah that is a more rock solid proof.

    Just out of curiosity though, was there anything wrong in the way I used the Lemma or my manipulation? Did it prove it?
    I always get really excited when I seem to figure out a good way to use things, and was just wondering if I was correct in thinking that?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by Th3sandm4n View Post
    Yeah that is a more rock solid proof.

    Just out of curiosity though, was there anything wrong in the way I used the Lemma or my manipulation? Did it prove it?
    I always get really excited when I seem to figure out a good way to use things, and was just wondering if I was correct in thinking that?
    Your proof looks good.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Jan 2009
    Posts
    27
    Sweet, I'm going to use that one since it's more personal.
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum