关于裴蜀定理推广的证明

· · 个人记录

已知：∑_{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