how can I minimise (n * y) (mod x) for known x and y, and for a given range of n?
How can I minimise (n.y) (mod x), for known x and y, and for a given range of n?
($x$ and $y$ are actually the components of a 2D vector for a line for which I'm trying to generate a set of bounding integer points)
So, for example, if x = 61, y = 17, and n must be in the range 0 < n < 12, then minimum value of the modulo operation is at n = 11, i.e. (11 * 17) (mod 61) = 4.
If we changed the range to 0 < n < 9, the minimum value is then at n = 4, i.e. (4 * 17) (mod 61) = 7.
I need to be able solve this for arbitrary values, but within a known range (around +/- 3000000).
This is a practical question so if there is no direct solution (or if a direct solution is very complicated) then a numerical method may be preferrable.