Path: news.mathworks.com!not-for-mail
From: "Leon galushko" <leonid.galushko@rwth-aachen.de>
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$1@fred.mathworks.com>
References: <g5sgla$b7r$1@fred.mathworks.com> <g5sjfa$fbg$1@fred.mathworks.com> <g5td8a$s9q$1@fred.mathworks.com> <g5tep3$g7r$1@fred.mathworks.com> <g5thqi$h7d$1@fred.mathworks.com> <g5tj02$rj4$1@fred.mathworks.com> <g5tleq$siu$1@fred.mathworks.com> <g5ujb2$7c1$1@fred.mathworks.com>
Reply-To: "Leon galushko" <leonid.galushko@rwth-aachen.de>
NNTP-Posting-Host: webapp-03-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1216551606 18783 172.30.248.38 (20 Jul 2008 11:00:06 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Sun, 20 Jul 2008 11:00:06 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1183838
Xref: news.mathworks.com comp.soft-sys.matlab:480533


"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid>
wrote in message <g5ujb2$7c1$1@fred.mathworks.com>...
> "Leon galushko" <leonid.galushko@rwth-aachen.de> wrote in
message 
> <g5tleq$siu$1@fred.mathworks.com>...
> > 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
a3/g123.
> 
>   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
> 
Roger, 
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 ?
Thanks
Leon