# Greatest common divisor.

## Homework Statement

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

## 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:

HallsofIvy
Homework Helper
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.

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

So that is not true or what?

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.

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.

Yes I've solved it already thank you.

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.