QQ网名大全

辗转相除法怎么解不定方程(初等数论)

不定方程ax+by=c有解,则(a,b)|c
如果(a,b) != 1 方程两边除以(a,b)
所以只需要讨论(a,b)=1的情形。
通过 a b的辗转相除法,求得au+bv=1
则(cu, cv)是一个特解。
从而得出通解。

例:求27x+16y=100的通解
27=16+11
16=11+5
11=5*2+1
1=11-5*2=11*3-16*2=3*27-5*16
所以(300,-500)是一个特解
通解:x=300+16t y=-500-27t
佚名
2024-06-08 02:30:58
最佳回答
类似问题(10)