# Creating a system of equations consisting only of integers?

1. Nov 2, 2011

### friedrice821

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. Nov 2, 2011

### AlephZero

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

3. Nov 2, 2011

### friedrice821

Thanks! the Diophantine equations really helped.

4. Nov 2, 2011

### gsal

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.