別解（繰り返し、MAT文による）

別解（繰り返し、MAT文による）

!拡張ユークリッド互除法

!「a*x+b*y=GCD(a,b)となるxとyが存在する」

!補助式
!　a*x1+b*y1=z1
!　a*x2+b*y2=z2
!を考える。
!z1/z2の商Q、余りRと置くと、z1=Q*z2+R。
!したがって、R=z1-Q*z2=a*x1+by1 - Q*(a*x2+b*y2)=a*(x1-Q*x2) + b*(y1-Q*y2)。
!ここでa*x3+by3=z3と比較して、
!x3=x1-Q*x2, y3=y1-Q*y2, z3=R=z1-Q*z2

INPUT PROMPT "２つの正の整数": a,b

DIM v1(3),v2(3),v3(3)
LET v1(1)=1 !x1
LET v1(2)=0 !y1
LET v1(3)=a !z1

LET v2(1)=0 !x2
LET v2(2)=1 !y3
LET v2(3)=b !z3

DO UNTIL v2(3)=0 !z2=0まで
LET Q=INT(v1(3)/v2(3)) !z1/z2の商

DIM t(3) !(x3,y3,z3)=(x1,y1,z1)-Q*(x2,y2,z2)
MAT t=Q*v2
MAT v3=v1-t

MAT v1=v2 !(x1,y1,z1)=(x2,y2,z2)

MAT v2=v3 !(x2,y2,z2)=(x3,y3,z3)
LOOP

PRINT "x,y,GCD(a,b)"
MAT PRINT v1

END

Re: 拡張ユークリッド互除法	返事を書くノートメニュー
山中和義 <drdlxujciw> 2008/01/10 16:10:41
別解（繰り返し、MAT文による） !拡張ユークリッド互除法 !「ax+by=GCD(a,b)となるxとyが存在する」 !補助式 !　ax1+by1=z1 !　ax2+by2=z2 !を考える。 !z1/z2の商Q、余りRと置くと、z1=Qz2+R。 !したがって、R=z1-Qz2=ax1+by1 - Q(ax2+by2)=a(x1-Qx2) + b(y1-Qy2)。 !ここでax3+by3=z3と比較して、 !x3=x1-Qx2, y3=y1-Qy2, z3=R=z1-Qz2 INPUT PROMPT "２つの正の整数": a,b DIM v1(3),v2(3),v3(3) LET v1(1)=1 !x1 LET v1(2)=0 !y1 LET v1(3)=a !z1 LET v2(1)=0 !x2 LET v2(2)=1 !y3 LET v2(3)=b !z3 DO UNTIL v2(3)=0 !z2=0まで LET Q=INT(v1(3)/v2(3)) !z1/z2の商 DIM t(3) !(x3,y3,z3)=(x1,y1,z1)-Q(x2,y2,z2) MAT t=Qv2 MAT v3=v1-t MAT v1=v2 !(x1,y1,z1)=(x2,y2,z2) MAT v2=v3 !(x2,y2,z2)=(x3,y3,z3) LOOP PRINT "x,y,GCD(a,b)" MAT PRINT v1 END