Re: Diophantic equations
- To: mathgroup at smc.vnet.net
- Subject: [mg32771] Re: [mg32746] Diophantic equations
- From: Andrzej Kozlowski <andrzej at tuins.ac.jp>
- Date: Sat, 9 Feb 2002 05:11:42 -0500 (EST)
- Sender: owner-wri-mathgroup at wolfram.com
Here is how to do it in your case. You can use this method to solve more
general linear cases.
First eliminate one variable from the equations:
In[1]:=
eqs={a+b+10 c==100,5 a+2 b+c==100}
In[2]:=
Eliminate[eqs,{c}]
Out[2]=
900-19 b==49 a
Clearly we only need to find all integer solutions of the equation 49
a + 19 b == 900, since c will then be given by c=100-a-2b.
The next step is to find just a single integer solution. The general way
to do this is to use the Euclidean algorithm.
In[3]:=
ExtendedGCD[49,19]
Out[3]=
{1,{7,-18}}
This tells us that:
In[4]:=
7*49-18*19
Out[4]=
1
From this we see at once that a solution will be given by:
In[7]:=
a=900*7
Out[7]=
6300
In[8]:=
b=900*-18
Out[8]=
-16200
indeed
In[9]:=
49 a+19 b
Out[9]=
900
Now that we have one solution (a,b) all the other solutions are given by
(a+m 19,b-m 49) = (6300+ m*19,-16200-m*49) where m is any integer.
Indeed:
In[11]:=
{6300+m*19,-16200-m*49}.{49,19}//Simplify
Out[11]=
900
On Friday, February 8, 2002, at 05:49 PM, Max Ulbrich wrote:
> Hi,
>
> I try to solve equations where only integers are allowed, like
>
> a + b + 10 c = 100
> 5 a + 2 b + c = 100
>
> a, b, c should be integers and positve.
>
> How can I do this?
>
> Max
>
>
>
>
>
Andrzej Kozlowski
Toyama International University
JAPAN
http://platon.c.u-tokyo.ac.jp/andrzej/