An Euclidean-algorithm type algorithm

In this article, we introduce an Euclidean-algorithm type algorithm for solving following problem

Extended Euclidean algorithm

We start with Extended Euclidean algorithm which computes coefficients of Bézout’s identity. Formally, for two nonnegative integers $a, b$ such that $a \le b$, the goal of the algorithm is to find an integer solution $(x, y)$ to the problem $$ ax + by = \text{gcd}(a, b). $$

Denote the above problem by $B(a, b)$.

Assume that $1 \le a \le b$ and $b = a q + r$ where $0 \le r < a$. If $x’, y’$ satisfy $a x’ + r y’ = \text{gcd}(a, r)$, then we have $a (x’ - q y’) + b y’ = \text{gcd}(a, r) = \text{gcd}(a, b - q a) = \text{gcd}(a, b)$.

That implies we can reduce the problem $B(a, b)$ to $B(a_1, b_1)$ such that $\text{gcd}(a_1, b_1) = \text{gcd}(a, b)$ and $\min\{a_1, b_1\} < \min\{a, b\}$.
If $\min\{a_1, b_1\} \ge 1$, then we also can reduce the problem $B(a_1, b_1)$ to another problem $B(a_2, b_2)$ such that $\text{gcd}(a_2, b_2) = \text{gcd}(a_1, b_1) = \text{gcd}(a, b)$ and $\min\{a_2, b_2\} < \min\{a_1, b_1\}$.
The procedure cannot proceed forever and will stop at step $t$ such that $\min\{a_t, b_t\} = 0$. Note that $a_t, b_t$ cannot be zero at the same time. Thus we can suppose that $a_t = 0, b_t > 0$. Note that $\text{gcd}(a, b) = \text{gcd}(a_t, b_t) = b_t$, and it is trivial to solve the problem $B(a_t, b_t)$.

We can implement the algorithm that is described above as follows.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def Bezout(a, b):
    # find x, y such that ax + by = gcd(a, b)
    # a >= 0, b >= 0
    # output: x, y, gcd(a, b)

    if a == 0 and b == 0:
        return 0, 0, 0

    elif a == 0:
        return 0, 1, b
    
    elif b == 0:
        return 1, 0, a

    else:
        x, y, d = Bezout(b % a, a)
        return y - x * (b // a), x, d

Algorithm for solving Problem (1)

Now let us consider Problem (1). Denote the problem by $P(A, M, L, R)$.

At first, we point out that there always exists a solution to the Problem (1). Suppose that integers $z, y$ satisfy $Az + My = 1$, and let $x = Lz(\mathrm{mod}\ M)$. Then we have $x \ge 0$ and $Ax \equiv LAz \equiv L (\mathrm{mod}\ M)$. Thus the set $\{ L \le Ax(\mathrm{mod}\ M) \le R \}$ is not empty.

Let discuss some special cases.

• If $M = 1$, then $L = R = 0$ and $A \in \{0, 1\}$.
• If $A = 0$, then $M = 1$.
  
• If $M = A$, then $M = A = 1$.
• If $A = 1$, then $L$ is the solution to the problem $P(A, M, L, R)$.
• If $A > M$, then according to $Ax(\mathrm{mod}\ M) = (A - M)x(\mathrm{mod}\ M)$, problem $P(A, M, L, R)$ and problem $P(A - M, M, L, R)$ share a same solution.

Thus we can assume that $2 \le A < M$.
Note that if $ \left\lfloor \frac{R}{A} \right\rfloor \ge \left\lceil \frac{L}{A} \right\rceil $, it is apparently that the $\left\lceil \frac{L}{A} \right\rceil$ is the solution to the problem $P(A, M, L, R)$. In fact, for $0 \le x < \left\lceil \frac{L}{A} \right\rceil$, there holds $0 \le Ax < L < M$. Hence we have $Ax(\mathrm{mod}\ M) = Ax < L$ and $x \notin \{ L \le Ax(\mathrm{mod}\ M) \le R \}$. On the other hand, we also have $L \le A \left\lceil \frac{L}{A} \right\rceil \le A \left\lfloor \frac{R}{A} \right\rfloor \le R$.

Now we suppose that $ \left\lfloor \frac{R}{A} \right\rfloor < \left\lceil \frac{L}{A} \right\rceil $. Observe that $$ \left\lfloor \frac{L}{A} \right\rfloor \le \left\lfloor \frac{R}{A} \right\rfloor < \left\lceil \frac{L}{A} \right\rceil \le \left\lfloor \frac{L}{A} \right\rfloor + 1 .$$ Therefore, we have $\left\lfloor \frac{L}{A} \right\rfloor = \left\lfloor \frac{R}{A} \right\rfloor$. Consequently, we also have $R - L < A$ and $L(\mathrm{mod}\ A) \le R(\mathrm{mod}\ A)$.

If $x_0$ is the solution to Problem (1), then exists $y_0$ such that $L \le A x_0 - M y_0 \le R$. It is apparently that $y_0 \ge 0$. Moreover, we claim that $y_0$ is the solution to the problem

Otherwise, suppose that $0 \le y_1 < y_0$ is the solution to above problem. We know there exists $x_1 \ge 0$ such that $L \le A x_1 - M y_1 \le R$. Note that $x_1 \in \{x \ge 0: L \le Ax(\mathrm{mod}\ M) \le R \}$ and $$ M \le M(y_0 - y_1) \le (A x_0 - L) - (A x_1 - R) = (R - L) + A (x_0 - x_1) < M + A (x_0 - x_1). $$ Hence, we have $x_1 < x_0$ which contradicts the fact that $x_0$ is the solution to the Problem (1).

Next, let $q, r$ satisfy $-M = q A + r$ where $0 \le r < A$. According to $\text{gcd}(A, M) = 1$, we know that $r \ge 1$. Then we have

where $L’ = L(\mathrm{mod}\ A)$, $R’ = R(\mathrm{mod}\ A)$, $p = \left\lfloor \frac{L}{A} \right\rfloor$. That implies we can reduce the problem $P(A, M, L, R)$ to Problem (3), which is the problem $P((-M)(\mathrm{mod}\ A), A, L(\mathrm{mod}\ A), R(\mathrm{mod}\ A))$, just like what we did in Extended Euclidean algorithm.

At last, We can implement above Euclidean-algorithm type algorithm as follows.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

def solve(A, M, L, R):
    # find minimum x such that L <= Ax(mod M) <= R
    # A >= 0, 0 <= L <= R < M, gcd(A, M) = 1

    if A >= M:
        A = A % M

    if A == 0:
        return 0

    t = (L - 1) // A + 1
    if t * A <= R:
        return t
    else:
        r = -M % A
        y = solve(r, A, L % A, R % A)
        x = (y * M + L - 1) // A + 1
        return x