Construct a singleton value

Make an interval given the start, end, and stride. Note that this will round up if (start - end) is not a multiple of the stride, i.e., @mkStr

Greatest lower bound. glb si1 si2 contains only those values which are in si1 and si2.

Returns the least b' s.t. exists i < n. b' = (b + i * q) mod m This is a little tricky. We want to find { b + i * q | i <- {0 .. n} } mod M Now, if we know the values in {0..q} we can figure out the whole sequence. In particular, we are looking for the new b --- the stride is gcd q M (assuming wrap)

Let q_w be k * q mod M s.t. 0 <= q_w < q. Alternately, q_w = q - M mod q

Assume wlog b0 = b < q. Take b1 = b0 + q_w b2 = b1 + q_w b3 = ...

i.e. bs = { b + i * q_w | i <- {0 .. n div ceil(m / q)} }

Now, we are interested in these value mod q, so take bs = { b0 + i * q_w } mod q

Thus, we get a recursion of (M, q) (q, q_w) (q_w, ...)

(M, q) (q, q - M mod q) (q - M mod q, (q - M mod q) - q mod (q - M mod q))

Base cases: Firstly, when q divides M, we can stop, or n == 0 Otherwise, for small M we can search for some i, that is the least 0 <= k < M s.t.

EX i. (b + i * q) mod M = k

Truncate an interval.