MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

3 retagged
2 edited tags
1

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.