Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Greatest common divisor.

  1. May 6, 2012 #1
    1. The problem statement, all variables and given/known data

    prove that: x^y=(5x+3y)^(13x+8y)

    2. Relevant equations



    3. The attempt at a solution

    Can I say that x^y divides both 5x+3y and 13x+8y and go on from there or what?

    Then in case one u could multiply 5x+3y by 13 and 13x+8y by 5 and do the difference and you'll get that x^y divides y

    Case 2: multiply 5x+3y by 8 and 13x+8y by 3 and then we get x^y divides x.

    And from case 1 and case 2 we can conclude that x^y=(5x+3y)^(13x+8y).

    Note that ^ stands for the greatest common divisor.
     
    Last edited: May 6, 2012
  2. jcsd
  3. May 6, 2012 #2

    HallsofIvy

    User Avatar
    Science Advisor

    I strongly recommend that you NOT try to prove things that are not true!

    Now, what is the problem really? For one thing, [itex]8^{21}[/itex] is not equal to 1.

    Are you trying to prove that [itex]x^y[/itex] is the greatest common divisor of [itex](5x+ 3y)^{13x+ 8y}[/itex]? Unfortunately, that's still not true. [itex]13^{34}]/itex] is not divisible by 2.
     
  4. May 6, 2012 #3
    So that is not true or what?
     
  5. May 6, 2012 #4
    Is this the question?:
    Prove that the greatest common divisor of 5x+3y and 13x+8y is the same as the greatest common divisor of x and y.

    or in notation I would understand:

    Prove that gcd(5x+3y,13x+8y) = gcd(x,y)

    And I suggest applying Euclid's algorithm to the polynomials on the left.
     
  6. May 7, 2012 #5
    Yes I've solved it already thank you.
     
  7. May 7, 2012 #6
    Good... I hope your solution looked something like:


    Since ##\text{gcd}(m,n) = \text{gcd}(m-n,n)##,
    [tex]
    \begin{align}
    \text{gcd}(13x+8y,5x+3y) &= \text{gcd}(8x+5y,5x+3y)\\
    &= \text{gcd}(3x+2y,5x+3y)\\
    &= \text{gcd}(5x+3y,3x+2y)\\
    &= \text{gcd}(2x+y,3x+2y)\\
    & \dots
    \end{align}
    [/tex]etc.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook