题解 P4549 【【模板】裴蜀定理】

· · 题解

看到机房dalao@liuzhihao的一篇好的证明题解，但他不想发出去(太强)所以我来转载一下

转载至：原文

PS：已经过本人同意

已知：∑_{i=1}^{n}a_ix_i=f 其中a_i,x_i,f∈Z

**求证：此方程有解的充要条件是$gcd(a_1,a_2,...,a_n) f ，其中n \in N^+∧n \in [2, + \infty )$.**

证：

1^o必要性.

设gcd(a_1,a_2,a_3,...,a_n)=k，则k|a_1,k|a_2...k|a_n

∴k|∑_{i=1}^na_ix_i=f

即gcd(a_1,a_2,...,a_n)|f

2^o充分性.

考虑数学归纳法

易证当n=2时成立

当x成立时考虑x+1的情况

设a_1+a_2+...+a_x=S,gcd(a_1,a_2,...,a_x)=k

则总存在一对整数(N,M)使得N*S+M*a_{x+1}=gcd(k,a_{x+1})

即总存在一对整数(N,M)使得N*(a_1+a_2+...+a_x)+M*a_{x+1}=gcd(a_1,a_2,...,a_{x+1})

∴存在一组解使得∑_{i=1}^{n}a_ix_i=gcd(a_1,a_2,...,a_n)，其中一组解为x_1=x_2=...=x_{n-1}=N,x_n=M(上文的N与M)

证毕.

Q.E.D