数论 麦乐鸡定理

251Sec · 2022-08-16 19:14:04 · 算法·理论

麦乐鸡定理

在写一道数论题的时候，我用到了这个定理，但我翻遍全网没找到它的中文证明……(英文的：Here，我觉得这个证明真的很难懂)。所以在大佬们的帮助下我决定写一篇证明。

感谢这个帖子里的大佬们。

感谢这位奆佬。

顺带，这定理名字取得真好。

第一部分

对于两个互质的正整数 a, b ，最大的不能用 ax+by 所表示的正整数为 ab-a-b 。其中 x,y 为非负整数。

(该证明来自P3951的题解区，Mzwuzad的题解)

假设不能用 ax+by 所表示的最大正整数为 m 。

若 m \equiv ax \pmod b(1 \leq x \leq b - 1) 。(因为 a \perp b ，显然存在一个 x 满足条件)

那么 m = ax + by(1 \leq x \leq b - 1) 。

显然，若 y \geq 0 ，那么 m 是可表示的。不符合题意。

而为了使 m 最大， x, y 应尽可能大，所以 x=b-1,y=-1 时， m 取最大值 (b-1)a-b=ab-a-b 。

第二部分

对于两个互质的正整数 a, b ，不能用 ax+by ( x, y 为非负整数)所表示的正整数恰好有 \dfrac{(a-1)(b-1)}{2} 个 。

假设 m(m < ab - a - b) 可以被表示成 ax+by ，其中 x, y 为非负整数。

而 ab - a - b - m 可以表示成 ax'+by' 。

那么 ab - a - b = a(x'+x) + b(y'+y) 。

与 ab - a - b 不可表示矛盾。

所以 m 与 ab - a - b - m 中，至多有一个是可表示的。

假设一个不可表示的数 m = ax+by(1 \leq x \leq b - 1, y < 0) ，那么 ab-a-b-m=ab-a-b-ax-by=a(b-1-x)+b(-y-1) ，而 b-1-x \geq 0, -y-1 \geq 0 。

所以 m 与 ab - a - b - m 中，至少有一个是可表示的。

综上， m 与 ab - a - b - m 刚好有一个是可表示的，而另一个是不可表示的。

所以不可表示的数量为 \dfrac{ab - a - b + 1}{2}=\dfrac{(a-1)(b-1)}{2} 。(为什么要 +1 ？因为 ab-a-b 以内包括 0 共有 ab - a - b + 1 个整数)