What is the Solution to the Extended Euclidean Algorithm Homework?

In summary, the conversation discusses a problem involving equations and the attempt to solve them. The first two equations are easily solved using back-substitution, but the third equation does not have any solutions with integer values. This is because both 1001 and 520 are multiples of 13, making the third equation not of the correct form.
  • #1
Dalmighty
3
0

Homework Statement



There's a couple of questions that require the use of this, I'm having trouble with one of them, could anyone help?

Homework Equations



a) 520x - 1001y = 13
b) 520x - 1001y = -26
c) 520x - 1001y = 1

The Attempt at a Solution



The first two are easy to do,

where you set 1001 and 520 as a and b respectively.

so:

1001 = 1*520 + 481
520 = 1*481 + 39
481 = 12*39 + 13
39 = 3*13 + 0 for a)
39 = 26 + 13 for b)And you use back-substitution for the first two and change the signs accordingly, that's fine,
so you start with:
a) 13 = 481 - (12*39)
b) 26 = 39 - 13
c) 1 = ?

for c), I'm stumped. Do you use a fraction or something? or is there no solution? thanks for any help you can give me.
 
Last edited:
Physics news on Phys.org
  • #2
The problem is that both 1001 and 520 are multiples of 13 (1001= 13(77), 520= 13(40) so that for any integer x and y, 520x+ 1001y= 13(77)x+ 13(40)y= 13(77x+ 40y) is a multiple of 13. 520x+ 1001y= A has a solution only if A is also a multiple of 13.

In the first two problems, that is, of course, true and the first thing you would do is divide through by 13: 520x+ 1001y= 13==> 40x+ 77y= 1 and 520x+ 1001y= -26==> 40x+ 77y= -2.

The third equation, 520x+ 1001y= 1 is not of that form. There are no solutions with integer x and y.
 
  • #3
Oh good, thanks for clarifying that, I had this suspicion that c) wasn't meant to have an answer.
 

What is the Extended Euclidean Algorithm?

The Extended Euclidean Algorithm is a mathematical method for finding the greatest common divisor of two integers, as well as the coefficients that can be used to express the GCD as a combination of the two integers.

What is the purpose of the Extended Euclidean Algorithm?

The main purpose of the Extended Euclidean Algorithm is to find the greatest common divisor of two integers, which is useful in many applications such as cryptography, number theory, and computer science.

How does the Extended Euclidean Algorithm work?

The algorithm works by using a series of division and subtraction operations to iteratively find the GCD of two integers. The coefficients are also calculated during this process, allowing for the expression of the GCD as a linear combination of the two integers.

What is the time complexity of the Extended Euclidean Algorithm?

The time complexity of the Extended Euclidean Algorithm is O(log n), where n is the larger of the two input integers. This makes it a very efficient method for finding the GCD compared to other algorithms.

Can the Extended Euclidean Algorithm be used for more than two integers?

No, the Extended Euclidean Algorithm is specifically designed for finding the GCD of two integers. However, it can be extended to find the GCD of multiple integers by applying the algorithm iteratively.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
1
Views
463
  • Precalculus Mathematics Homework Help
Replies
16
Views
3K
  • Precalculus Mathematics Homework Help
Replies
2
Views
1K
  • Precalculus Mathematics Homework Help
Replies
6
Views
1K
  • Precalculus Mathematics Homework Help
Replies
11
Views
4K
  • Precalculus Mathematics Homework Help
Replies
4
Views
3K
  • STEM Educators and Teaching
Replies
24
Views
2K
  • Precalculus Mathematics Homework Help
Replies
8
Views
1K
Replies
3
Views
2K
  • Precalculus Mathematics Homework Help
Replies
8
Views
2K
Back
Top