Kuṭṭaka 法
| Kuṭṭaka法 | |
|---|---|
| 术语名称 | Kuṭṭaka法 |
| 英语名称 | Kuṭṭaka |
| 别名 | Kuttaka法, 库塔卡法, Kuttaka |
本条目没有一致可信的中文译名。
Kuṭṭaka 法（梵 कुट्टक, kuṭṭaka ，意为“粉碎”）/Kuttaka 法，也音译为库塔卡法，是印度数学中用于求解一次不定方程 [math]\displaystyle{ ax + by = c, \operatorname{gcd}(a,b)=1 }[/math] 的算法。算法本质是将辗转相除法得到的部分商序列看作连分数的渐近分数形式，从而获得方程的特解。其本质等价于扩展 Euclid 算法。
这一算法本身是为了解决源自天文问题的同余方程组 [math]\displaystyle{ \begin{cases}x\equiv a\pmod m \\ x\equiv b\pmod n \end{cases} }[/math] 。原始方法中将这一方程组化为 [math]\displaystyle{ \begin{cases}x=mu+a\\x=nv+b\end{cases} }[/math] 的不定方程组，并通过求解满足 [math]\displaystyle{ mu - nv = a - b }[/math] 完成。
算法
原理
对于互质的正整数 [math]\displaystyle{ a, b }[/math]（设 [math]\displaystyle{ a \gt b }[/math]），将分数 [math]\displaystyle{ a/b }[/math] 展开为有限连分数 [math]\displaystyle{ \frac{a}{b} = [a_0; a_1, a_2, \dots, a_n] = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{\ddots + \cfrac{1}{a_n}}}} }[/math]，则其中不完全商 [math]\displaystyle{ a_0, a_1, \dots, a_n }[/math] 正是对 [math]\displaystyle{ a, b }[/math] 进行辗转相除所得的各次商。
考虑渐近分数列 [math]\displaystyle{ p_k / q_k }[/math]（[math]\displaystyle{ k = -2, -1, 0, 1, \dots, n }[/math]），其中 [math]\displaystyle{ \begin{cases} p_{-2} &= 0,\quad p_{-1} = 1; \\ q_{-2} &= 1,\quad q_{-1} = 0; \\ p_k &= a_k p_{k-1} + p_{k-2}, \\ q_k &= a_k q_{k-1} + q_{k-2}. \end{cases} }[/math]
则最终 [math]\displaystyle{ p_n / q_n = a / b }[/math]，且连分数的基本性质保证 [math]\displaystyle{ p_n q_{n-1} - p_{n-1} q_n = (-1)^{n-1} }[/math] 。
将上式代入 [math]\displaystyle{ p_n = a, q_n = b }[/math] 得到 [math]\displaystyle{ a \cdot q_{n-1} - b \cdot p_{n-1} = (-1)^{n-1} }[/math] ， 因此， [math]\displaystyle{ (-1)^{n-1} a q_{n-1} + (-1)^{n} b p_{n-1} = 1 }[/math] 。
于是方程 [math]\displaystyle{ ax + by = 1 }[/math] 的一组特解为 [math]\displaystyle{ x_0 = (-1)^{n-1} q_{n-1}, y_0 = (-1)^n p_{n-1} }[/math] 。通过乘以 [math]\displaystyle{ c }[/math] 并调整可得到一般方程 [math]\displaystyle{ ax + by = c }[/math] 的特解。
伪代码
过程 Kuttaka法
别名 kuttaka_algorithm
参数 a, b : 正整数
返回 : x, y : 整数 // 满足 a x + b y = 1
// 辗转相除，记录部分商列表 q₀ 、 q₁ 、……、 qₖ
令 r₀ ← a
令 r₁ ← b
循环 k ← 1
执行
记 qₖ, rₖ₊₁ ← rₖ divmod rₖ₋₁
继续循环 k ← k + 1
直到 rₖ = 0 为止
此时记 n ← k
// 回代过程，也就是“粉碎”的过程
令 s₋₂ ← 0 ， s₋₁ ← 1
令 t₋₂ ← 1 ， t₋₁ ← 0
循环 k ← 1
执行
记 sₖ ← rₖ sₖ₋₁ + sₖ₋₂
记 tₖ ← rₖ tₖ₋₁ + tₖ₋₂
继续循环 k ← k + 1
直到 k = n 为止
// 调整符号得到特解
令 x₀ = (-1)ⁿ⁻¹tₙ₋₁ ， y₀ = (-1)ⁿsₙ₋₁
返回 x₀ ， y₀
琐事
历史
在印度古代天文学中，行星位置计算常归结为求解一次同余方程，等价于不定方程 [math]\displaystyle{ ax + by = c }[/math]。 Kuṭṭaka 法最早见于印度数学家阿耶波多（आर्यभट, Āryabhaṭa ，约公元 499 年）的《阿耶波多书》（आर्यभटीय, Āryabhaṭīya），后由婆罗摩笈多（ब्रह्मगुप्त, Brahmagupta）、婆什迦罗（भास्कर, Bhāskara）等人加以完善。
其名称 kuṭṭaka 意为“粉碎”或“研磨”，指算法中系数被辗转相除过程“碾碎”为更小的数，直到可以目测求解。