Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Euclidean Array problem

  1. Feb 10, 2010 #1
    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?

  2. jcsd
  3. Feb 10, 2010 #2


    User Avatar
    Science Advisor

    You may just have an arithmetic error. I get x= 1182, not 1082.
  4. Feb 10, 2010 #3
    Can you explain to me how you got 1182? Is my entire bottom row incorrect?
  5. Feb 10, 2010 #4


    User Avatar
    Science Advisor

    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?
  6. Feb 10, 2010 #5
    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.
  7. Feb 11, 2010 #6


    User Avatar
    Science Advisor

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook