裴蜀定理及其证明「建议收藏」

裴蜀定理及其证明「建议收藏」证明还蛮简单(

大家好,欢迎来到IT知识分享网。

前言

原来裴蜀是法国数学家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=aqk=aq(ax+by)=a(1qx)+b(qy)

显然 r r r 也为 a , b a,b a,b 线性组合的解,且 0 ≤ r ≤ k 0\le r \le k 0rk

∵ k \because k k 为最小非负解

∴ r = 0 \therefore r=0 r=0

∴ k ∣ a \therefore k\mid a ka

同理 k ∣ b k\mid b kb

d = gcd ⁡ ( a , b ) d=\gcd(a,b) d=gcd(a,b) ,则 s ∣ d s\mid d sd d ≥ s d \ge s ds

∵ d ∣ a , d ∣ b \because d\mid a,d\mid b da,db s s s a , b a,b a,b 线性组合的解

∴ d ∣ s \therefore d\mid s ds

∵ 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),kZ+ 是原方程的解

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 da,db

∵ 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 dax,dby

∴ d ∣ a x + b y = c \therefore d\mid ax+by=c dax+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,yiZ ,其有解的充要条件为 gcd ⁡ { x i } ∣ k \gcd\{x_i\}\mid k gcd{
xi}
k

证明略


二、裴蜀定理模板题

题目链接:P4549 【模板】裴蜀定理

即推广结论裸题

要注意负数要转成正数再算 gcd ⁡ \gcd gcd

代码如下

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define R register
int n,ans,a[25];
int gcd(R int a,R int b)
{ 
   return b==0?a:gcd(b,a%b);}
signed main()
{ 
   
	scanf("%lld",&n);
	for(R int i=1; i<=n; i++)
	{ 
   
		scanf("%lld",&a[i]);
		a[i]=a[i]>0?a[i]:-a[i];
		ans=gcd((i==1?a[1]:ans),a[i]);
	}
	printf("%lld\n",ans);
	return 0;
}

IT知识分享网


总结

本文简单介绍了裴蜀定理

转载请说明出处

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/7544.html

(0)

相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注微信