Greatest common divisor.

  • Thread starter mtayab1994
  • Start date
  • #1
584
0

Homework Statement



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

Homework Equations





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:

Answers and Replies

  • #2
HallsofIvy
Science Advisor
Homework Helper
41,847
964
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.
 
  • #3
584
0
I strongly recommend that you NOT try to prove things that are not true!

So that is not true or what?
 
  • #4
473
13
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
584
0
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.
 
  • #6
473
13
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.
 

Related Threads on Greatest common divisor.

  • Last Post
Replies
2
Views
893
  • Last Post
Replies
24
Views
3K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
19
Views
5K
Replies
11
Views
4K
Replies
0
Views
1K
  • Last Post
Replies
8
Views
1K
Replies
7
Views
2K
Top