Results 1 to 6 of 6

Math Help - GCD Problem

  1. #1
    Junior Member star_tenshi's Avatar
    Joined
    Jan 2009
    Posts
    32

    Question GCD Problem

    I've been working on these two problems for the last few days, can't seem to get it. Any help would be very much appreciated.

    1. Prove that a|bc iff a/(a,b)|c
    So far I know that the denominator has to be a common multiple of both a & b, but I cannot prove that it has to be the gcd of a & b.

    2. Show that if (a,b)=1, then (a+b,a2-ab+b2)=1 or 3
    So far this is what I've come up with, using the theorems:
    a) (a,m)=1, (b,m)=1, then (ab,m)=1
    b) (a,b)=(a,b+na) that:

    (a(a+b),b) = (a2+ab,b) = 1
    (a,b(b-2a)) = (a,b2-2ab)=1

    but I can't seem to relate the two.

    Again, thanks for any help in advance.
    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
    1. a|bc \implies a|b \text{ or } a|c
    In the first case,  a|b \implies (a,b)=a \implies \frac{a}{(a,b)}=1|c
    In the second case,  a|c \implies (a,b) \text{ is at most } a \implies \frac{a}{(a,b)}|c because   \frac{a}{(a,b)} is a factor of a.
    2. You have (2,3) = 1 but 2+3=1
    Also (17,19) = 1 (19-17)^2 = 4
    The statement I not true as I understand it.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,407
    (1) Since it's an if and only if statement, we have to show the statement forward and its converse is true.

    (a) a \mid bc \ \Rightarrow \ \tfrac{a}{(a,b)} \mid c

    Let d = (a,b). For some x,y \in \mathbb{Z}, we have: ax + by = d \ \Leftrightarrow \ \tfrac{a}{d}x + \tfrac{b}{d}y = 1 \ \Leftrightarrow \ \tfrac{a}{d}cx + \tfrac{b}{d}cy = c

    Since \tfrac{a}{d} divides both terms on the left hand side (justify it), we can conclude \tfrac{a}{d} \mid c.

    (b) \tfrac{a}{(a,b)} \mid c \ \Rightarrow \ a \mid bc

    So we have: \tfrac{a}{(a,b)} \mid c \ \Rightarrow \ a \mid (a,b)c

    Since (a,b) \mid b by definition, then (a,b)c \mid bc.

    Put those 2 lines together and we have our conclusion.
    _______________________________

    You have (2,3) = 1 but 2+3=1
    Also (17,19) = 1 (19-17)^2 = 4
    The statement I not true as I understand it.
    The statement says that for all a, b \in \mathbb{Z} such that \gcd (a,b) = 1, then \gcd \left(a + b, a^2 - ab + b^2\right) = 1 \text{ or } 3

    For example, a = 2 and b = 3. Then: \gcd(2 + 3, \ 2^2 - (2)(3) + 3^2) = \gcd(5, 7) = 1

    And another: a = 10 and b = 11. Then: \gcd(10+11, 10^2 - (10)(11) + 11^2) = \gcd(21, 111) = 3
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member vincisonfire's Avatar
    Joined
    Oct 2008
    From
    Sainte-Flavie
    Posts
    469
    Thanks
    2
    Awards
    1
    I'm not totally sure but using euclidian algorythm we have
     a^2-ab+b^2=(a-2b)(a+b)+3b^2
    Now we have to search for common factors of a+b \text{ and } 3b^2
    It is not b since (a,b)=1. It can thus be 1 or 3.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member star_tenshi's Avatar
    Joined
    Jan 2009
    Posts
    32
    Thanks for your help with #1 o_O! (I can't believe I didn't see the obvious proof there... )

    vincisonfire, I just learned the Euclidean algorithm yesterday, so I'm still trying to understand your reply. Thanks for your help though!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by vincisonfire View Post
    1. a|bc \implies a|b \text{ or } a|c
    Thats not true in general!

    Choose a = 4, b = 2 , c = 2, to understand why...
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum