Systems with More Variables than Equations

Date: 12/11/2002 at 11:51:14
From: Sridar
Subject: Solving systems

Dr. Math. How do you solve this system?:

   187y + 98x + 45z = 48
   2y + 9x + 3z = 198

I tried solving it by trying to multiply equation 2 by 15 to eliminate 
Z, but do you multiply again by another number to eliminate another 
variable? I am totally stuck here.

P.S. I am in 4th grade but I am learning high school math! Isn't 
that cool?

Date: 12/11/2002 at 13:11:27
From: Doctor Greenie
Subject: Re: Solving systems

Hello, Sridar -

With three variables and only two equations, you can't do anything 
more than eliminate one variable. You will end up with a single 
equation with two variables; the graph of such an equation is a 
straight line, indicating that there are infinitely many solutions.

Usually, with problems like this, it is either stated or implied that 
the solutions should be integers; in that case, you can perform an 
analysis to determine the family of distinct solutions.

In your particular example, eliminating z gives you the equation

  37x - 157y = 2922

The standard approach to finding the integer solutions of an equation 
like this looks something like this:

  37x - 157y = 2922
  37x = 157y + 2922
  x = (157/37)y + (2922/37)
  x = 4y + (9/37)y + 78 + 36/37
  x = (4y + 78) + (9y + 36)/37

Now since x must be an integer, and since 4y + 78 is an integer, 
(9y + 36)/37 must also be an integer.

  9y + 36
  ------- = n  for some integer n
    37

  9(y + 4)
  -------- = n
     37

Since 9 and 37 are relatively prime, y + 4 must be a multiple of 37 
for this expression to have an integer value. The smallest positive 
value for which this is the case is y=33. So we have as our first 
solution in which both x and y are integers:

  y = 33

  x = (4y + 78) + (9y + 36)/37 = (132 + 78) + (333/37) = 210 + 9 = 219

  2y + 9x + 3z = 198
  66 + 1971 + 3z = 198
  3z = -1839
  z = -613

These integer values of x and y yield an integer value for z, so we 
have our first solution to the original pair of equations in integers.

For the family of solutions, we have

  9(y + 4)
  -------- = n
     37

where n is an integer. The general solution, for this expression to 
be an integer, is

  y = 33 + 37k

where k is any integer. To find the general solution, we then have

  y = 33 + 37k

  x = (4y + 78) + (9y + 36)/37
  x = (132 + 148k + 78) + (297 + 333k + 36)/37
  x = (148k + 210) + (9k + 9)
  x = 157k + 219

  2y + 9x + 3z = 198
  (66 + 74k) + (1413k + 1971) + 3z = 198
  3z = -1487k - 1839
  z = -(1487/3)k - 613

The coefficient 1487 is not divisible by 3; this tells us that only 
values of k which are multiples of 3 will yield integer values for z.

So now we can form the expressions for the family of integer solutions 
to your problem.  

  y = 33 + 37(3k)  where k is any integer (not the same k as above)
  y = 111k + 33

  x = (4y + 78) + (9y + 36)/37
  x = (444k + 132 + 78) + (999k + 297 + 36)/37
  x = (444k + 210) + (27k + 9)
  x = 471k + 219

  2y + 9x + 3z = 198
  (222k + 66) + (4239k + 1971) + 3z = 198
  4461k + 2037 + 3z = 198
  3z = -4461k -1839
  z = -1487k - 613

The family of integer solutions to your pair of equations is

  (x, y, z) = (471k + 219, 111k + 33, -1487k - 613)

where k is any integer.

Equations like these, where there are more variables than equations, 
and where solutions are to be integers, are called Diophantine 
equations.  You can find many pages in the Dr. Math archives where 
similar problems are discussed by performing a search of the archives 
using the keyword 

   diophantine

I hope all this helps.  If you have any questions about any of this, 
try looking at some more examples in the archives.  Then write back 
if you still have questions.

- Doctor Greenie, The Math Forum
  http://mathforum.org/dr.math/