裴蜀定理

本文主要是介绍裴蜀定理，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

裴蜀定理

描述

对于任何整数 \(a\)、\(b\) 和 \(c\)，关于未知数 \(x\)、\(y\) 的不定方程 \(ax + by = c\) 有整数解时当且仅当 \(c\) 是 \(a\) 及 \(b\) 的最大公约数 \(d\) 的倍数。

即：不定方程 \(ax + by = c\) 有整数解的充分必要条件是 \(d \mid c\)。

裴蜀定理的一个重要推论是 \(a\) 与 \(b\) 互素的充分必要条件是存在整数 \(x\)、\(y\)，使 \(ax + by = 1\)。

证明

要证明裴蜀定理，需要分别证明它的充分性和必要性。

以下约定 \(d = \gcd(a, b)\)。

必要性

命题：若 \(ax + by = c\) 有整数解，\(d \mid c\)。

证明：
显然 \(d \mid a, d \mid b\)。因为 \(x\) 和 \(y\) 均为整数，可得 \(d \mid ax, d \mid by\)。
将等式两边同时除以 \(d\)，得 \(\frac{ax}{d} + \frac{by}{d} = \frac{c}{d}\)，
因为已证 \(d \mid ax, d \mid by\)，显然 \(\frac{ax}{d} + \frac{by}{d}\) 的值为整数。
所以要使等式成立，\(c\) 必然是 \(d\) 的倍数，即 \(d \mid c\)。

充分性

命题：若 \(d \mid c\)，则 \(ax + by = c\) 有整数解。

证明：
显然 \(d \mid a, d \mid b\)。可描述：\(a = ud, b = vd\)。
\(c\) 可替代为 \(ud \cdot x + vd \cdot y = d(ux + vy)\)。显然 \(d \mid c\)。

设 \(s\) 是 \(c\) 的最小正整数值。则 \(s\) 是 \(a\)、\(b\) 的线性组合。
设 \(r = a \bmod s\)，\(p = \lfloor \frac{a}{s} \rfloor\)。

由带余除法定理可得 \(r = a - ps = a - p(ax + by) = a(1 - px) - bqy\)。
显然 \(r\) 也是 \(a\)、\(b\) 的线性组合。

因为 \(r = a \bmod s\)，所以 \(0 \leq r < s\)。
若 \(0 < r < s\) 与 \(s\) 是 \(c\) 的最小正整数值矛盾。
所以 \(r = 0\)

因为 \(r = 0\) 且 \(r = a \bmod s\)，可得 \(s \mid a\)。

同理可证 \(s \mid b\)。
所以 \(s\) 是 \(a\) 和 \(b\) 的公约数。

因为 \(d\) 是 \(a\) 和 \(b\) 的最大公约数。
所以 \(d \geq s\)。

又因为已证 \(d \mid c\) 即 \(d \mid s\)。
所以 \(d \leq s\)。

联立两个不等式，解得 \(d = s\)。
即 \(ax + by\) 的最小整数解为 \(d\)。

显然当 \(c\) 为 \(d\) 的整数倍时 \(ax + by = c\) 依然有整数解。

推广

裴蜀定理可以从两个数推广到三个数及以上。

参考文献

• Cnblog：Mystical-W
• 洛谷博客：ADay
• 洛谷博客：本喵
• 百度百科：充分必要条件
• 百度百科：线性组合
• 百度百科：裴蜀定理
• 知乎：Pecco
• 维基百科：带余除法
• 维基百科：裴蜀定理

这篇关于裴蜀定理的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！