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

 

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

 

[CellCoree]

Your approach using the determinant is a good start. Another way to create a system of equations consisting only of integers is by using the concept of linear combinations. This means that you can take any two integers and create a linear equation using them. For example, let's say we have the integers 3 and 5. We can create the equation 3x + 5y = 2, where x and y are variables.

To ensure that the system can only be solved by integer answers, we can set the coefficients of x and y (3 and 5 in this case) to be relatively prime. This means that they have no common factors other than 1. This ensures that the only possible solutions for x and y will be integers.

You can also use this concept to create a system of two equations with two unknowns. For example, we can take the integers 2 and 7 and create the equations 2x + 7y = 5 and 4x + 14y = 10. This system will have integer solutions only because the coefficients of x and y are relatively prime.

In summary, to create a system of equations consisting only of integers, you can use the determinant method or the concept of linear combinations with relatively prime coefficients. These methods ensure that the system can only be solved by integer answers.