1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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


    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)##,
    \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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook