1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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