Results 1 to 2 of 2

Math Help - Clarification on gcd proofs

  1. #1
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3

    Clarification on gcd proofs

    Hey guys,

    So we all (hopefully ) know the definition of gcd. and so if we want to prove that an integer, d, is the gcd of two integers, a and b, then in general, we must show:

    (a) d \mid a and d \mid b, and,

    (b) If there exists c, such that c \mid a and c \mid b, then c \mid d.

    Now, I want clarification on proving (b). My professor last semester always did something like this. In problems where we were working with linear combinations, he would have the equation d = ma + nb for m,n \in \mathbb{Z}. No problem. But to show that d = (a,b), he would say: "suppose there is some c such that c \mid a and c \mid b. then a = kc and b = lc for k,l \in \mathbb{Z}. Thus, d = ma + nb = (mk)c + (nl)c = c(mk + nl) \implies c \mid d."

    now i always had a problem with that. why does this work? it seems like an underhanded trick to me, and that it could work for d's that are not the gcd.

    case in point: lets say i am thinking about (3,2), we know this is 1. and 1 = 3 + (-1)(2), so here a = 3,~b=2,~m = 1, \text{ and }n = -1. and i can run the proof above and it works for my d (= 1).

    but what if i was really imagining the combination 2(3) + (-2)(2) = 2, and so i took a = 3,~b=2,~m = 2, \text{ and }n = -2. and i can run the generic proof above for d = ma + nb and conclude that my d (which is 2) is the gcd of 3 and 2.

    of course if we know the values of a,~b, \text{ and } d, this would be absurd, but a lot of the proofs i am doing are with pure variables. how can i be confident that my linear combination is the optimal one for the gcd and thus can run this proof with a clear conscience.

    or am i imagining a problem that really isn't there?

    Thanks for listening to my rant... and oh, yeah, the question too,
    Jhevon
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello
    Quote Originally Posted by Jhevon View Post
    Hey guys,
    What about gals ?

    (a) d \mid a and d \mid b, and,

    (b) If there exists c, such that c \mid a and c \mid b, then c \mid d.

    Now, I want clarification on proving (b). My professor last semester always did something like this. In problems where we were working with linear combinations, he would have the equation d = ma + nb for m,n \in \mathbb{Z}. No problem. But to show that d = (a,b), he would say: "suppose there is some c such that c \mid a and c \mid b. then a = kc and b = lc for k,l \in \mathbb{Z}. Thus, d = ma + nb = (mk)c + (nl)c = c(mk + nl) \implies c \mid d."

    now i always had a problem with that. why does this work? it seems like an underhanded trick to me, and that it could work for d's that are not the gcd.
    I think he introduces c more for proving (b) than proving d=gcd(a,b).
    Let c be a common divisor of a and b. Thus he must divides gcd(a,b), since it's the least common factor of all common divisors of a and b.

    So we proved in (a) that d, the presumed gcd, divides a and b. Thus he divides the gcd. But we proved in (b) that if c is any of a and b's common divisors, then it divides d. So there is no common factor of a and b higher than d !

    case in point: lets say i am thinking about (3,2), we know this is 1. and 1 = 3 + (-1)(2), so here a = 3,~b=2,~m = 1, \text{ and }n = -1. and i can run the proof above and it works for my d (= 1).

    but what if i was really imagining the combination 2(3) + (-2)(2) = 2, and so i took a = 3,~b=2,~m = 2, \text{ and }n = -2. and i can run the generic proof above for d = ma + nb and conclude that my d (which is 2) is the gcd of 3 and 2.
    Does d divide a ?
    Plus, as soon as you can simplify the equaion am+bn=..., do it.


    of course if we know the values of a,~b, \text{ and } d, this would be absurd, but a lot of the proofs i am doing are with pure variables. how can i be confident that my linear combination is the optimal one for the gcd and thus can run this proof with a clear conscience.
    Because you make assumptions. It's better having an example right now
    By the way, you don't have to care about m and n. Because the gcd divides any linear combination of a and b.
    In proofs involving pure variables, you barely need the identity : there exist m and n such that am+bn=gcd(a,b). It is not interesting because it's not a reciprocity... Saying that the gcd divides a and b and any linear combination of them two is more interesting

    or am i imagining a problem that really isn't there?
    Prove it as it comes in your mind lol. No, I'm serious. There is a lot of intuition in my opinion.



    Are there unclear things ? (which wouldn't be surprising... not easy to explain this way )
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. clarification
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: January 8th 2011, 06:10 PM
  2. Clarification of PDE.
    Posted in the Differential Equations Forum
    Replies: 2
    Last Post: February 10th 2010, 03:35 PM
  3. I need some clarification
    Posted in the Calculus Forum
    Replies: 4
    Last Post: May 19th 2008, 10:59 AM
  4. Replies: 3
    Last Post: October 6th 2007, 02:01 PM

Search Tags


/mathhelpforum @mathhelpforum