Results 1 to 4 of 4

Math Help - GCD Proof With Squares

  1. #1
    Newbie Reindeer Floatilla's Avatar
    Joined
    Oct 2009
    Posts
    2

    GCD Proof With Squares

    Prove:
    If gcd(a,b)=gcd(a,c)
    , then gcd(a^2,b^2)=gcd(a^2,c^2).

    My knowledge of the greatest common factor (GCD) is rather limited, but I'm thinking this will involve representing GCD expressions with linear combinations. Here is what I know:

    The greatest common divisor of the nonzero integers a
    and b is the least positive integer that is a linear combination of a and b.

    And the trivial assumption:
    gcd(a,b) implies there exists a number that is a common divisor of a and b.

    Assume
    gcd(a,b)=gcd(a,c).
    Let
    d=gcd(a,b)=gcd(a,c).
    Then
    d divides a, b, and c.
    So
    a=dk, b=dl, and c=dm for some integers k, l, and m.
    Let
    e=gcd(a^2,b^2).
    Then
    e divides a^2 and b^2.
    So a^2=ex and b^2=ey for some integers x and y.

    (Now what?)

    If this is even the correct start to this proof, I would be amazed. I imagine the next steps would involve substitution, but I'm not sure how to proceed. Any help would be appreciated!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Welcome to the forum!

    You are not completely on the wrong track. When you say

    a=dk,\ b=dl

    it is important to mention that (k,l)=1. But if (k,l)=1 then (k^2,l^2)=1 (Prove this! Hint : write k and l as products of prime powers. Then what does it mean for them to be relatively prime?)

    So (a^2,b^2)=(d^2k^2,d^2l^2)=d^2(k^2,l^2)=d^2.

    Setting d=(a,b)=(a,c) you have (a^2,b^2)=d^2 and (a^2, c^2)=d^2, so (a^2,b^2)=(a^2,c^2).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Aug 2009
    Posts
    170
    Thanks
    8
    a = kd => a^2 =(kd)^2 = ex ... similar for b ... does that help?

    Actually ... you can try showing this first (a,b)=d then (a^2,b^2)=d^2 so if (a,b)=(a,c), then (a^2,b^2)=(a^2,c^2) ...
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie Reindeer Floatilla's Avatar
    Joined
    Oct 2009
    Posts
    2
    Excellent! Your suggestions gave me what I needed to continue. Thank you!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. sum of squares proof
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: April 10th 2011, 06:24 PM
  2. proof latin squares and planes
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 20th 2010, 04:16 PM
  3. sum of two squares proof
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: August 4th 2009, 02:32 PM
  4. Sum of three squares of rationals (proof)
    Posted in the Algebra Forum
    Replies: 7
    Last Post: April 12th 2009, 08:26 AM
  5. Sum of two squares proof. Help please.
    Posted in the Algebra Forum
    Replies: 2
    Last Post: September 11th 2007, 01:10 PM

Search Tags


/mathhelpforum @mathhelpforum