前言
原来裴蜀是法国数学家QwQ
一、裴蜀定理
对于 x , y x,y x,y 的二元一次不定方程 a x + b y = c ax+by=c ax+by=c ，其有解的充要条件为 gcd ( a , b ) ∣ c \gcd(a,b)\mid c gcd(a,b)∣c
1.充分性证明
充分性：若 gcd ( a , b ) ∣ c \gcd(a,b)\mid c gcd(a,b)∣c ，则 a x + b y = c ax+by=c ax+by=c 有解
设 k k k 为 a , b a,b a,b 线性组合的最小非负解
令 q = ⌊ a k ⌋ q=\left\lfloor\dfrac{a}{k}\right\rfloor q=⌊ka⌋ ，则有 r = a m o d k = a − q k = a − q ( a x + b y ) = a ( 1 − q x ) + b ( − q y ) r=a \mod k = a-qk = a-q(ax+by) = a(1-qx)+b(-qy) r=amodk=a−qk=a−q(ax+by)=a(1−qx)+b(−qy)
显然 r r r 也为 a , b a,b a,b 线性组合的解，且 0 ≤ r ≤ k 0\le r \le k 0≤r≤k
∵ k \because k ∵k 为最小非负解
∴ r = 0 \therefore r=0 ∴r=0
∴ k ∣ a \therefore k\mid a ∴k∣a
同理 k ∣ b k\mid b k∣b
令 d = gcd ( a , b ) d=\gcd(a,b) d=gcd(a,b) ，则 s ∣ d s\mid d s∣d 且 d ≥ s d \ge s d≥s
∵ d ∣ a , d ∣ b \because d\mid a,d\mid b ∵d∣a,d∣b 且 s s s 为 a , b a,b a,b 线性组合的解
∴ d ∣ s \therefore d\mid s ∴d∣s
∵ s > 0 \because s>0 ∵s>0
∴ d = s \therefore d=s ∴d=s
则 a x + b y = c ax+by=c ax+by=c 的最小非负解为 gcd ( a , b ) \gcd(a,b) gcd(a,b)
显然 ∀ c = k gcd ( a , b ) , k ∈ Z + \forall c=k\gcd(a,b),k\in \Z^+ ∀c=kgcd(a,b),k∈Z+ 是原方程的解
2.必要性证明
必要性：若 a x + b y = c ax+by=c ax+by=c 有解，则 gcd ( a , b ) ∣ c \gcd(a,b)\mid c gcd(a,b)∣c
证明：
令 d = gcd ( a , b ) d=\gcd(a,b) d=gcd(a,b) ，则 d ∣ a , d ∣ b d\mid a,d\mid b d∣a,d∣b
∵ a x + b y = c \because ax+by=c ∵ax+by=c 有解
∴ d ∣ a x , d ∣ b y \therefore d\mid ax,d\mid by ∴d∣ax,d∣by
∴ d ∣ a x + b y = c \therefore d\mid ax+by=c ∴d∣ax+by=c
3.推广
对于不定方程 x 1 y 1 + x 2 y 2 + . . . + x n y n = k , ∀ y i ∈ Z x_1y_1+x_2y_2+…+x_ny_n=k, \forall y_i \in \Z x1y1+x2y2+...+xnyn=k,∀yi∈Z ，其有解的充要条件为 gcd { x i } ∣ k \gcd\{x_i\}\mid k gcd{
xi}∣k
证明略
二、裴蜀定理模板题
题目链接：P4549 【模板】裴蜀定理
即推广结论裸题
要注意负数要转成正数再算 gcd \gcd gcd
代码如下
#include
总结
本文简单介绍了裴蜀定理
转载请说明出处
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/208513.html原文链接：https://javaforall.net
