Extended Euclidean Algorithm

  • Thread starter Dalmighty
  • Start date
  • #1
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:

Answers and Replies

  • #2
HallsofIvy
Science Advisor
Homework Helper
41,833
962
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
3
0
Oh good, thanks for clarifying that, I had this suspicion that c) wasn't meant to have an answer.
 

Related Threads on Extended Euclidean Algorithm

  • Last Post
Replies
5
Views
1K
Replies
0
Views
2K
Replies
4
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
1
Views
2K
Replies
2
Views
1K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
1
Views
2K
Top