I’ll summarize my approach so that it is more convenient for people to improve it, if someone is interested.
We are given positive integers a, b, c, d such that \gcd(a, b) = 1 and \gcd(c, d) = 1. We are trying to find smallest positive n>0 such that
n = i a + j b = k c + ld,
where i, j, k, l \in \mathbb{N} are non-negative variables.
My approach is based on finding natural solutions of the linear equations. Let’s first focus on the first one, n = ia + jb.
From the Bézout’s identity, we can find i_0, j_0 \in \mathbb{Z} such that
ai_0 + b j_0 = 1.
Multiplying by some n \in \mathbb{N}, we get
a (ni_0) + b(n j_0) = n.
Since either i_0 or j_0 is negative (unless a = b = 1), we don’t have a natural solution. Suppose i_0 is negative. We can write
a(n i_0 + b m) + b(n j_0 - am) = n,
where m \in \mathbb{N} is some number. The goal now is to find the smallest n \in \mathbb{N} such that there is some m \in \mathbb{N} that makes both ni_0 + bm and n j_0 - am non-negative. Formally:
n i_0 + bm \geq 0 \rightarrow m \geq -\frac{ni_0}{b}, \\
n j_0 - am \geq 0 \rightarrow m \leq \frac{nj_0}{a},
which gives together
n s \leq m \leq n t,
where s = -\frac{i_0}{b} and t = \frac{j_0}{a}. Now, if j_0 was negative, we would get s = -\frac{j_0}{a} and t = \frac{i_0}{b}.
So, our task transforms into finding the smallest n \in \mathbb{N} for which there is an m \in \mathbb{N} such that n s \leq m \leq n t. Subtract ns to get
0 \leq m - ns \leq n ( t - s ),
in which we set m = \lceil ns \rceil to satisfy the first inequality. It leads to finding the smallest n \in \mathbb{N} such that
\begin{aligned}
\lceil ns \rceil - ns &\leq n ( t - s) \\
\lceil ns \rceil &\leq n t
\end{aligned}
If we make the very same argument but for the equation n = kc + ld, we obtain
\lceil nu \rceil \leq nv,
where u = \begin{cases}
-k_0 / d & \text{if } k_0 < 0 \\
-l_0 / c & \text{if } l_0 < 0
\end{cases} and v = \begin{cases}
l_0 / c & \text{if } k_0 < 0 \\
k_0 / d & \text{if } l_0 < 0
\end{cases} with the Bézout’s coefficients k_0, l_0 such that c k_0 + d l_0 = 1.
So the algorithm is:
- Initialize n := 1
- Find smallest n_1 \geq n for which \lceil n_1 s \rceil \leq n_1 t holds
- Find smallest n_2 \geq n for which \lceil n_2 u \rceil \leq n_2 v holds
- Set n := \max\{ n_1, n_2 \}
- If n_1 \neq n_2, go to 2.
- Compute solution.
The solution can be computed as
\begin{aligned}
i &= i_0 n - \text{sign}(i_0) b m_1, \\
j &= j_0 n + \text{sign}(i_0) a m_1, \\
k &= k_0 n - \text{sign}(k_0) d m_2, \\
l &= l_0 n + \text{sign}(k_0) c m_2,
\end{aligned}
where m_1 = \lceil ns \rceil and m_2 = \lceil nu \rceil.
The problem with this approach is that for some inputs, we have to iterate over too many n before finding a match n_1 = n_2. We could improve that by initializing n with a value that is closer to the optimum. Another improvement could be in steps 2 and 3, where now I sequentially check if the condition holds (maybe we could do skip some values).
Code here:
Code
function next_lowest(u, v, n)
while n <= typemax(Int)
if n * v - ceil(n * u) ≥ 0
return n
end
# Improvement: do larger steps
n += 1
end
throw(ErrorException("not found"))
end
function solve(a, b, c, d)
_, i0, j0 = gcdx(a, b)
_, k0, l0 = gcdx(c, d)
s = ifelse(i0 < 0, -i0 // b, -j0 // a)
t = ifelse(i0 < 0, j0 // a, i0 // b)
u = ifelse(k0 < 0, -k0 // d, -l0 // c)
v = ifelse(k0 < 0, l0 // c, k0 // d)
# Improvement: Initialize better
n = 1
while true
n1 = next_lowest(s, t, n)
n2 = next_lowest(u, v, n)
n = max(n1, n2)
if n1 == n2
break
end
end
println("Solved for n=$n")
m1 = ceil(n * s)
m2 = ceil(n * u)
i = Int(i0 * n - sign(i0) * b * m1)
j = Int(j0 * n + sign(i0) * a * m1)
k = Int(k0 * n - sign(k0) * d * m2)
l = Int(l0 * n + sign(k0) * c * m2)
println("i=", i)
println("j=", j)
println("k=", k)
println("l=", l)
end
