system of equations with integer solution

hermit · 2010-02-16 18:59:19

x(a,b) + y(c,d) = (s, t)

What conditions do (a,b) and (c,d) have to satisfy for this to have solution in integers? Of course a,b,c,d,s,t are fixed integers.

I turned this to two equations ax + cy =s, and bx + dy = t. I use y = (sc-ax)/c to substitute into second equation. This gives x = (tc-ds)/(bc-ad). Does this mean that bc-ad can not be zero? Or just that bc-ad has to divide tc-ds? Both? Do I have to give conditions in terms of ordered pairs, or just state relations regarding a,b,c,d?

bobbym · 2010-02-16 20:50:10

Hi;

This is what you have done:

This yields:

Yes it does mean that bc - ad ≠ 0 and (bc - ad) must divide ct - ds, when c ≠ 0 then c must divide s - ax.

Unfortunately this is not much help in determining a,b,c,d,s,t.

hermit · 2010-02-16 21:14:50

First, thank you very much. I thought more after seeing your reply. Here is what I have now:

Using matrix form you provided,

I used formula for inverse of 2x2 matrix and call them A and A^-1, and multiply on both sides with the inverse so that there is x,y on left, and A^-1 * s,t on right of equality. I think this means for there to be integer solution x,y to the original equation that the determinant of A must evenly divide each of the entries a, b, c, and d.

The exercise asks to find conditions on a,b,c,d so that integers x,y always can be found to satisfy original equation for any s,t. Would this condition be a sufficient answer to this question?

bobbym · 2010-02-16 21:19:42

Hi hermit;

Check this and see if it helps, in the meantime I will look at your idea.

A long time ago in Mathematics Magazine vol 69 no. 4 1996 I came across a similar question by Felix Lazebnik. It is now on the internet, it provides the van der Waerden theorem which is supposed to cover this. I have never been able to get that theorem to work.

http://docs.google.com/viewer?a=v&q=cac … oHVFkKRbEQ

If you can get his theorem to actually do a single example correctly please explain it to me.

bobbym · 2010-02-16 21:30:37

Hi hermit;

hermit wrote:

I think this means for there to be integer solution x,y to the original equation that the determinant of A must evenly divide each of the entries a, b, c, and d.

That does not hold.

The matrix eqtn.

Has a solution of x = -2 and 9 while the det of A is -11 which does not divide a or b or c or d

2121044 · 2010-02-16 23:05:40

HELP ME TO DO FRACTIONS AND PERCENTAGES

bobbym · 2010-02-16 23:10:14

Hi 2121044;

Please post your problem in a new thread, this one is for a different subject.

Go here:

http://www.mathisfunforum.com/viewforum.php?id=2

On the upper right hand corner you will see post new topic.

hermit · 2010-02-17 05:36:57

bobbym wrote:

Hi hermit;
hermit wrote:
I think this means for there to be integer solution x,y to the original equation that the determinant of A must evenly divide each of the entries a, b, c, and d.
That does not hold.
The matrix eqtn.
Has a solution of x = -2 and 9 while the det of A is -11 which does not divide a or b or c or d

I see what you mean but think I misexplained the question. I will try to rephrase. What conditions must a,b,c,d satisfy so that the equation A(x,y)=(s,t) has integer solutions for all (s,t). I think what this counterexample shows is for a particular (s,t). In the question I am looking at, a,b,c,d are fixed, but s,t are not fixed integers.

I have not had time to look at link you gave yet, but will soon. Thank you again.

bobbym · 2010-02-17 05:49:37

Hi hermit;

I don't believe that you can find a,b,c,d that will always have an integer solution for x,y for any s,t. I wouldn't think that is possible. Can you tell me where this problem is from?

Math Is Fun Forum

#1 2010-02-16 18:59:19

system of equations with integer solution

#2 2010-02-16 20:50:10

Re: system of equations with integer solution

#3 2010-02-16 21:14:50

Re: system of equations with integer solution

#4 2010-02-16 21:19:42

Re: system of equations with integer solution

#5 2010-02-16 21:30:37

Re: system of equations with integer solution

#6 2010-02-16 23:05:40

Re: system of equations with integer solution

#7 2010-02-16 23:10:14

Re: system of equations with integer solution

#8 2010-02-17 05:36:57

Re: system of equations with integer solution

#9 2010-02-17 05:49:37

Re: system of equations with integer solution

Board footer