What is the Solution to the Extended Euclidean Algorithm Homework?

[Dalmighty]

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.

 

[HallsofIvy]

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.

 

[Dalmighty]

Oh good, thanks for clarifying that, I had this suspicion that c) wasn't meant to have an answer.