|
又学了一种解二元一次不定方程的方法——辗转相除法
仍以第一题为例,通过8步辗转相除,8步还原得到了不定方程的通解和通解。
被除数 除数 商 余数 表达式
999983 3083 324 1091 999983/3083=324…1091
3083 1091 2 901 3083/1091=2…901
1091 901 1 190 1091/901=1…190
901 190 4 141 901/190=4…141
190 141 1 49 190/141=1…49
141 49 2 43 141/49=2…43
49 43 1 6 49/43=1…6
43 6 7 1 43/6=7…1
还原
1=43-6*7 1=43-6*7
6=49-43*1 1=43-(49-43*1)*7=43*8-49*7
43=141-49*2 1=(141-49*2)*8-49*7=141*8-49*23
49=190-141*1 1=141*8-(190-141*1)*23=141*31-190*23
141=901-190*4 1=(901-190*4)*31-190*23=901*31-190*147
190=1091-901*1 1=901*31-(1091-901*1)*147=901*178-1091*147
901=3083-1091*2 1=(3083-1091*2)*178-1091*147=3083*178-1091*503
1091=999983-3083*324 1=3083*178-(999983-3083*324)*503=3083*163150-999983*503
最终得到
1=3083*163150-999983*503
999983*503+1=3083*163150
999983*503-3083*163150=-1
特解x0=503, y0=163150
通解x=503-3083t, y=163150-999983t, t≤0的整数。
辗转相除法够繁杂的吧?
虽然此法可用于系数较大的不定方程,但系数还是不能太大,大于16位的数字照样不能处理。
对于第2题要用13步辗转相除和13步还原,它的特解和通解是:
x0=10952929
y0=52894765243042940=52894765*10^9+243042940
x=10952929-66380909*t
y='52894765243042940-'320572022166380909*t
或y=52894765*10^9+243042940-320572022*10^9*t+166380909*t
t≤0,(0和负整数)
|
|