Euclidean Array problem

1. Feb 10, 2010

scottstapp

1. The problem statement, all variables and given/known data

Find a positive integer solution to 1234x-4321y=1, both x and y will be positive.

2. Relevant equations

3. The attempt at a solution

I created this array

4321 1234 619 615 4 3 1
3 1 1 153 1
1082 309 155 154 1 1 0

When plugging these (positive) values in I never get 1 I only get -1 when using x=1082 and y=309. Does this mean that no positive solution exists?

Thanks

2. Feb 10, 2010

HallsofIvy

You may just have an arithmetic error. I get x= 1182, not 1082.

3. Feb 10, 2010

scottstapp

Can you explain to me how you got 1182? Is my entire bottom row incorrect?

4. Feb 10, 2010

HallsofIvy

Oh, how embarassing! Your 1082 is completely correct. Apparently I made a silly arithmetic error myself.

You are correct, then, that 1082(1234)- 309(4321)= -1.

Multiplying through by -1 gives (-1082)(1234)- (-309)(4321)= 1.

But x= -1082 and y= -309 is not the only solution. If we were to add any multiple of 4321 to x and add the same multiple of 1234 to y, so that we have x+ 4321k and y- 1234k, then 1234(x+ 4321k)- 4321(y+ 1234k)= 1234x- 4321y+ ((1234)(4321)k- (4321)(1234)k)= 1234x- 4321y.

So just find k such that -1082+ 4321k and -309+ 1234k are positive. There are plenty of such solutions. Can you find the smallest?

5. Feb 10, 2010

scottstapp

In this problem can I actually just multiply through by -1 though? I am supposed to have a positive x and a positive y. So doesn't that mean that there does not exist any positive x and y such that 1234x-4321y=1? I know this seems to be a very elementary question but by the terms of this problem I am not sure if that is a "legal" move.

6. Feb 11, 2010

HallsofIvy

Multiplying by -1 gives negative solutions but my point was that you can then add any multiple of 4321 to the x value and 1234 to the y value and make the solutions positive.