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