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!

Creating a system of equations consisting only of integers?

  1. Nov 2, 2011 #1
    I'm looking for an algorithm to create a very simple (2 equations, 2 unknowns) linear system of equations that consists purely of integers. Specifically, a way to create a system of equations of integers and knowing that it can only be solved by integer answers, without actually solving it.

    a11x1+a12x2=b1
    a21x1+a22x2=b2
    where a11, a12, a21, a22, x1, x2, b1, b2 are all integers.

    The only thing I can think of is using a determinant which gives
    x1 = (a22b1-a12b2) / (a11a22-a12a21)
    x2 = (a11b2-a21b1) / (a11a22-a12a21)
    and that the numerator must be a multiple of the denominator.

    What do I do now? Am I even on the right path?
     
    Last edited: Nov 2, 2011
  2. jcsd
  3. Nov 2, 2011 #2

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

    You don't say why you want to do this, but if you want to geerate "random" questions for an online test or something similiar, the easy way is to just pick a, b, c, d, x1 and x2, and then work out y1 and y2.

    If this is a more general question, look up "euclid's lemma" and linear Diophantine equations, e.g. http://en.wikipedia.org/wiki/Euclidean_algorithm
     
  4. Nov 2, 2011 #3
    Thanks! the Diophantine equations really helped.
     
  5. Nov 2, 2011 #4
    By the way, I wish you hadn't used y1 and y2...it just throws a curve ball as to they are supposed to be known constants or unknowns...maybe you should simply use a couple of more letters?

    ...just being picky.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Creating a system of equations consisting only of integers?
Loading...