bs@faron.UUCP (Robert D. Silverman) (10/11/85)
Does anyone know of a simple way for solving the diophantine equation: Ax + By + xy = K with A,B,K given? By making the substitution x' = (x + B) and y' = (y + A) it can be transformed into the problem of factoring K + AB. Is there any other way of solving it???? Bob Silverman (they call me Mr. 9)
gjk@talcott.UUCP (John) (10/14/85)
In article <364@faron.UUCP>, bs@faron.UUCP (Robert D. Silverman) writes: > Does anyone know of a simple way for solving the diophantine equation: > > Ax + By + xy = K with A,B,K given? > > By making the substitution x' = (x + B) and y' = (y + A) it can > be transformed into the problem of factoring K + AB. > Is there any other way of solving it???? I don't think there is a better way. Not only is it true that if you factor K + AB, you get an x and a y, but also if you manage to get an x and a y (by some other means), you get a factorization of K + AB with little addi- tional computation. Therefore the problems are essentially equivalent. -- abcdefghijklmnopqrstuvwxyz ^ ^^
andrews@yale.ARPA (Thomas O. Andrews) (10/15/85)
In article <364@faron.UUCP> bs@faron.UUCP (Robert D. Silverman) writes: > >Does anyone know of a simple way for solving the diophantine equation: > > Ax + By + xy = K with A,B,K given? > >By making the substitution x' = (x + B) and y' = (y + A) it can >be transformed into the problem of factoring K + AB. > >Is there any other way of solving it???? > > >Bob Silverman (they call me Mr. 9) If,in fact, there was a nicer way to solve this problem, then one would also be able to quickly factor K+AB. If anyone out there has a fast algorythm for solving this equation, I'm sure the government would like to see it. :-) In any event, the two problems (solution of the equation and factorization) are basically equivalent, so there can't be a much better way to solve it .... -- Thomas Andrews 17? My dear, what worthless, superstitious nonsense!