Creating a system of equations consisting only of integers?

[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.

a₁₁x₁+a₁₂x₂=b₁
a₂₁x₁+a₂₂x₂=b₂
where a₁₁, a₁₂, a₂₁, a₂₂, x₁, x₂, b₁, b₂ are all integers.

The only thing I can think of is using a determinant which gives
x₁ = (a₂₂b₁-a₁₂b₂) / (a₁₁a₂₂-a₁₂a₂₁)
x₂ = (a₁₁b₂-a₂₁b₁) / (a₁₁a₂₂-a₁₂a₂₁)
and that the numerator must be a multiple of the denominator.

What do I do now? Am I even on the right path?

 

[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 similar, 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

 

[friedrice821]

Thanks! the Diophantine equations really helped.

 

[gsal]

By the way, I wish you hadn't used y₁ and y₂...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.