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/

```

• Prev by Date: Re: FullSimplify doesn't simplify
• Next by Date: finite fields
• Previous by thread: Re: Diophantic equations
• Next by thread: Re: Diophantic equations