Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Topic: Small modulo problem
Replies: 1   Last Post: Jul 23, 2013 3:58 PM

 Messages: [ Previous | Next ]
 quasi Posts: 12,054 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 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

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).

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

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

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.

quasi

Date Subject Author
7/23/13 Allen Windhorn
7/23/13 quasi