From: "Leon galushko" <>
Newsgroups: comp.soft-sys.matlab
Subject: Re: linear equation with restrictions
Date: Sun, 20 Jul 2008 11:00:06 +0000 (UTC)
Organization: The MathWorks, Inc.
Lines: 103
Message-ID: <g5v5rm$iav$>
References: <g5sgla$b7r$> <g5sjfa$fbg$> <g5td8a$s9q$> <g5tep3$g7r$> <g5thqi$h7d$> <g5tj02$rj4$> <g5tleq$siu$> <g5ujb2$7c1$>
Reply-To: "Leon galushko" <>
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: 1216551606 18783 (20 Jul 2008 11:00:06 GMT)
NNTP-Posting-Date: Sun, 20 Jul 2008 11:00:06 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1183838
Xref: comp.soft-sys.matlab:480533

"Roger Stafford" <>
wrote in message <g5ujb2$7c1$>...
> "Leon galushko" <> wrote in
> <g5tleq$siu$>...
> > Well done!
> > my really last question to:
> > in case there are more variables than 2 in the equation
> > (a1 * b2 + a2 * b2 + a3 * b3 = c) the solving with refering
> > to GCD - Function of MATLAB falls down becaus gcd operates
> > only with 2 elements?
> > Thanks!
> > Leon
>   Leon, I understand that you wish to solve the equation
>  a1*b1 + a2*b2 + a3*b3 = c
> where a1, a2, a3, and c are known and without loss of
generality can be 
> assumed to be positive integers, and where b1, b2, and b3
are unknown but 
> are restricted to also being positive integers.
>   If
>  [g12,-,-] = gcd(a1,a2)
> is done, you already know how to find b1 and b2 which can make
>  a1*b1 + a2*b2
> equal to any desired multiple of g12.  If
>  [g123,-,-] = gcd(g12,a3)
> is done, you can then find from this a set of b1, b2, and
b3 values which can 
> make
>  a1*b1 + a2*b2 + a3*b3
> equal to any desired multiple of g123.  If c is not a
multiple of g123, then the 
> original equation above has no solution.  Otherwise b1,
b2, and b3 solutions 
> can always be found, but one or two of them will typically
be negative.
>   It is not hard to also show from the above reasoning
that b3 can be adjusted 
> up or down by any desired multiple of g12/g123 if
corresponding changes 
> are made to b1 and b2 that cause the left side of the
equation to remain 
> unchanged.  That is, if the multiple of g12 that
a1*b1+a2*b2 is equal to is 
> changed in the opposite direction by the same multiple of
>   This should then be done in such a way that b3 assumes
its minimum 
> possible positive value, and that will give c-a3*b3 its
maximum possible 
> value.  From what Bruno has told you, you already know how
to then look for 
> possible solutions to the two variable problem
>  a1*b1 + a2*b2 = c3 = c-a3*b3 
> where b3 has been so determined.  This will tell you if
any valid positive 
> solutions exist and if so, will give you one of them.
>   If b3 were to be increased from this minimum value, then
c-a3*b3 is 
> decreased and the number of possible positive b1 and b2
solutions can only 
> decrease.  If you also have an upper bound for your b's,
as in your first 
> article, the latter process of increasing b3 from its
minimum might 
> conceivably be necessary to keep all b's within upper
bounds simultaneously.
> Roger Stafford
thanks to your answer. I'm afraid i have but to clarify some
detail which Bruno almost tryed to satisfy.
(It's going about the same equation
(a1 * b2 + a2 * b2 + a3 * b3 = c) you understand rightly)
Say, if g1 and g2 through gcd(a1, a2) have been got
(output would be D1 and D2), then
to get g3 it's to state: gcd(g12,a3), where i understand
g12 to be Greatest Common Deviser for A1 and A1 (g12).

Where is have to be deduced g12 from?
Is it correct: 

            g12 = D1*A1 + D2*A2 ?