Allen Windhorn wrote: > >I'm looking for an algorithm to provide a closed-form solution >to the following equation: > >b = (1+g*n)/q > >for positive integer g, n, q, where n and q are known, and are >relatively prime (else there's no integer solution). The >desired result is to find the smallest value of g for which b >is an integer. > >Example: for n = 18 and q = 7, b = (1+5*18)/7 = 91/7 = 13, >so g = 5 > >Best I've come up with so far is g<q and g*n mod q = q-1
The conditions you came up with _uniquely_ determine the least positive integer g for which b is an integer.
A fast method for finding g is the Euclidean algorithm.
For example, using n = 18, q = 7, use the Euclidean algorithm to solve the linear diophantine equation
Thus, the equation 7x + 18y = 1 has the particular solution (x,y) = (-5,2).
Readjusting the signs, the equation
7x - 18y = 1
has the particular solution (x,y) = (-5,-2), and the general solution
x = -5 + 18*t y = -2 + 7*t
For g we want the smallest positive integer y from the general solution above, and for b the corresponding x-value.
Thus, y > 0 => t > 2/7 => t >= 1.
Using t = 1,
b = x = -5 + 18*1 = 13 g = y = -2 + 7*1 = 5
In almost any elementary Number Theory textbook, you can typically find a more complete description and analysis of the method of using the Euclidean algorithm to solve linear diophantine equations in 2 variables.
As far as a "closed-form" solution, you can use
g = ((q - 1) * n^(phi(q) - 1)) mod q
where phi is Euler's phi function.
For example, using n = 18, q = 7,
g = ((q - 1) * n^(phi(q) - 1)) mod q = ((7 - 1) * 18^(6 - 1)) mod 7 = (6 * 18^5) mod 7 = (6 * 4^5) mod 7
But this so-called "closed form" method is not really closed form since the formula for phi(q) requires knowing the prime factorization of q. If q is large, 100 digits say, finding the prime factorization of q is, in general, too hard, so the method is not practical, whereas the Euclidean algorithm method still works well.