Creating a system of equations consisting only of integers?

  • #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:

Answers and Replies

  • #2
AlephZero
Science Advisor
Homework Helper
6,994
292
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
Thanks! the Diophantine equations really helped.
 
  • #4
1,065
54
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.
 

Related Threads on Creating a system of equations consisting only of integers?

  • Last Post
Replies
3
Views
6K
Replies
9
Views
919
  • Last Post
Replies
2
Views
835
  • Last Post
Replies
3
Views
1K
Replies
6
Views
1K
  • Last Post
Replies
7
Views
2K
  • Last Post
Replies
11
Views
4K
Replies
3
Views
5K
Replies
4
Views
1K
Top