|
|
ユークリッドの互除法による
例 37x+32y=1
答え 互除法
1 | 37 32 | 6 1 | a b | 6
| 32 30 | | b 6(a-b) |
---------------- → --------------------------
2 | 5 2 | 2 | a-b -6a+7b |
| 4 | | 2(-6a+7b) |
---------------- --------------------------
| 1 | | 13a-15b |
↓
| 1 0 | -2
| -2 |
-----------------
-6 | 1 -2 | -1
| 12 -13 |
-----------------
| 13 -15 |
（終り）
答え 互除法の商+連立方程式の行基本変形の考え方
漸化式 [n行の係数]=[(n-2)行の係数]-[(n-1)行の係数×商] より、
商 x y
1 0
1 0 1
6 1-0×1=1 0-1×1=-1
2 0-1×6=-6 1-(-1)×6=7
1-(-6)×2=13 (-1)-7×2=-15
（終り）
CALL ExGCD(37,32,x,y,c)
PRINT x;y;c
END
EXTERNAL SUB ExGCD(A,B,x,y,c) !拡張ユークリッドの互除法
!A＞0,B＞0に対して、Ax+By=cとなるx,y,c=gcd(A,B)を求める
LET c=A
LET c1=B
LET x=1
LET x1=0
LET y=0
LET y1=1
DO WHILE c1>0
PRINT x;y; c !debug
!PRINT x1;y1; c1 !debug
LET Q=INT(c/c1)
LET R=MOD(c,c1)
PRINT Q;R !debug
LET x2=x-Q*x1
LET y2=y-Q*y1
LET c=c1
LET c1=R
LET x=x1
LET x1=x2
LET y=y1
LET y1=y2
LOOP
END SUB
実行結果
1 0 37
1 5
0 1 32
6 2
1 -1 5
2 1
-6 7 2
2 0
13 -15 1
その2 再帰呼び出し
CALL ExGCD2(37,32,x,y,c)
PRINT x;y;c
PRINT
END
EXTERNAL SUB ExGCD2(a,b, x,y,c) !拡張ユークリッドの互除法
!A＞0,B＞0に対して、Ax+By=cとなるx,y,c=gcd(A,B)を求める
IF b=0 THEN
LET x=1 !a×1+b×0=a
LET y=0
LET c=a
PRINT x;y !debug
ELSE
LET q=INT(a/b)
LET r=MOD(a,b)
PRINT a;b; q !debug
CALL ExGCD2(b,r, u,v,c)
LET x=v
LET y=u-v*q
PRINT x;y; q !debug
END IF
END SUB
実行結果
37 32 1
32 5 6
5 2 2
2 1 2
1 0
0 1 2
1 -2 2
-2 13 6
13 -15 1
13 -15 1
別解 互除法+連立方程式
A=Q*B+Rとして、(R+BQ)X+BY=RX+B(QX+Y)と変形する。
例 37x+32y=1
(5+32×1)x+32y =5x+32(x+y) =5x+(2+5×6)(x+y) =2(x+y)+5{x+6(x+y)}
すなわち、2(x+y)+5(7x+6y)と変形する。
ここで2×(-2)+5×1=1より、連立方程式x+y=-2, 7x+6y=1を得る。
これを解いて、x=13, y=-15
（終り）
|
|