Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.


quasi
Posts:
12,047
Registered:
7/15/05


Re: Small modulo problem
Posted:
Jul 23, 2013 3:58 PM


Allen Windhorn wrote: > >I'm looking for an algorithm to provide a closedform 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 = q1
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
7x + 18y = 1
First divide 18 by 7.
18 = 7*2 + 4 => 4 = 7*x1 + 18*y1 where (x1,y1) = (2,1)
Then divide 7 by 4.
7 = 1*4 + 3 => 3 = 7  1*4 = 7  1*(7*x1 + 18*y1) => 3 = 7*x2 + 18*y2 where (x2,y2) = (1  x1,y1) = (3,1)
Then divide 4 by 3.
4 = 1*3 + 1 => 1 = 4  1*3 = (7*x1 + 18*y1)  1*(7*x2 + 18*y2) => 1 = 7*x3 + 18*y3 where x3 = x1  x2 = 2  3 = 5 and y3 = y1  y2 = 1  (1) = 2
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 xvalue.
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 "closedform" 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
Working mod 7,
4^5 = 4 * (4^2)^2 = 4 * 16^2 = 4 * 2^2 = 4 * 4 = 16 = 2
so, still working mod 7,
g = 6 * 4^5 = 6 * 2 = 12 = 5
which matches your result.
But this socalled "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.
quasi



