# Homework Help: Greatest common divisor.

1. May 6, 2012

### mtayab1994

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. May 6, 2012

### HallsofIvy

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

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

Are you trying to prove that $x^y$ is the greatest common divisor of $(5x+ 3y)^{13x+ 8y}$? Unfortunately, that's still not true. [itex]13^{34}]/itex] is not divisible by 2.

3. May 6, 2012

### mtayab1994

So that is not true or what?

4. May 6, 2012

### Joffan

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.

5. May 7, 2012

### mtayab1994

Yes I've solved it already thank you.

6. May 7, 2012

### Joffan

Good... I hope your solution looked something like:

Since $\text{gcd}(m,n) = \text{gcd}(m-n,n)$,
\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}etc.