algorithm - 使用欧几里德算法查找 2 个变量

Question

我有 ab-cd = 1，其中 a、b、c、d 是整数，我得到了 a 和 c。有人告诉我可以使用欧几里德算法找到 b 和 d，但我不知道如何应用它。

Answer 1

你只需追踪它。

欧几里得算法以一对数字开始，并用一对新数字替换它。像这样:

(x, y) -> (y, x - (x//y) * y)

您从 (a, c) 开始并重复执行此操作，直到您得到一对，其中一个将另一个分开。

但我们可以并行地将每个数字视为原始两个数字的线性组合。所以如果 x = i*a + j*c 我们可以用 (i, j) 表示。同上 y 可以用 (k, l) 表示。但是现在我们可以将操作表示如下...

((i, j), (k, l)) -> ((k, l), (i - (x//y) * k, j - (x//y) * l))

在这个并行表示中，我们从 ((1, 0), (0, 1)) 开始。当我们最终达到 1 时，我们现在知道了答案!

这可能看起来有点抽象，让我们举一个真实的例子。让我们做 a = 15 和 c = 11。

(15, 11) -> (11,  4) | x//y = 1 | (( 1,  0), ( 0,  1)) -> (( 0,  1), ( 1, -1))
(11,  4) -> ( 4,  3) | x//y = 2 | (( 0,  1), ( 1, -1)) -> (( 1, -1), (-2,  3))
( 4,  3) -> ( 3,  1) | x//y = 1 | (( 1, -1), (-2,  3)) -> ((-2,  3), ( 3, -4))

所以我声称 3 * 15 + (-4) * 11 = 1。事实上，它确实如此。

你只需要对数字进行运算，对有序对进行正确的并行运算，最后一个就是你的答案。