Results 1 to 4 of 4

Thread: GCD Proof With Squares

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

    GCD Proof With Squares

    Prove:
    If $\displaystyle gcd(a,b)=gcd(a,c)$
    , then $\displaystyle 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 $\displaystyle a$
    and $\displaystyle b$ is the least positive integer that is a linear combination of $\displaystyle a$ and $\displaystyle b$.

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

    Assume
    $\displaystyle gcd(a,b)=gcd(a,c)$.
    Let
    $\displaystyle d=gcd(a,b)=gcd(a,c)$.
    Then
    $\displaystyle d$ divides $\displaystyle a$, $\displaystyle b$, and $\displaystyle c$.
    So
    $\displaystyle a=dk$, $\displaystyle b=dl$, and $\displaystyle c=dm$ for some integers $\displaystyle k$, $\displaystyle l$, and $\displaystyle m$.
    Let
    $\displaystyle e=gcd(a^2,b^2)$.
    Then
    $\displaystyle e$ divides $\displaystyle a^2$ and $\displaystyle b^2$.
    So $\displaystyle a^2=ex$ and $\displaystyle b^2=ey$ for some integers $\displaystyle x$ and $\displaystyle 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

    $\displaystyle a=dk,\ b=dl$

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

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

    Setting $\displaystyle d=(a,b)=(a,c)$ you have $\displaystyle (a^2,b^2)=d^2$ and $\displaystyle (a^2, c^2)=d^2$, so $\displaystyle (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: Apr 10th 2011, 06:24 PM
  2. proof latin squares and planes
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Feb 20th 2010, 04:16 PM
  3. sum of two squares proof
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Aug 4th 2009, 02:32 PM
  4. Sum of three squares of rationals (proof)
    Posted in the Algebra Forum
    Replies: 7
    Last Post: Apr 12th 2009, 08:26 AM
  5. Sum of two squares proof. Help please.
    Posted in the Algebra Forum
    Replies: 2
    Last Post: Sep 11th 2007, 01:10 PM

Search Tags


/mathhelpforum @mathhelpforum