ax+by=c整数解通项公式

· · 个人记录

ax+by=c

将两边同时除以d=\gcd(a,b)

设\frac{a}{\gcd(a,b)}=\alpha,\frac{b}{\gcd(a,b)}=\beta

\alpha x+\beta y=\frac{c}{d}

只有当\frac{c}{d}为整数时方才有整数解

若使右侧=\gcd(\alpha,\beta)=1

则x=x'*\frac{d}{c},y=y'*\frac{d}{c}

\alpha x'+\beta y'=1

然后利用扩展欧几里得求出一组特解x''与y''

故方程解为x=x''+k\times\frac{b}{d},

~~~~~~~~~~~~~~~~y=y''-k\times\frac{a}{d}

若使其为正整数，-\frac{x''d}{b}\leq k\leq\frac{y''d}{a}\

代入得ax''+by''=c

得证