Casio50 » fx-3x50P » Programs 祘Α栋 » Number Thoery 计阶 »

Extended GCD
耎程そ计

セΑ―ㄢ计 a, b ぇ程そ计 (a, b), ―ㄏ au + bv = (a, b) い u, v 俱计秆.

<SD>
? → A : ? → B :
1 → X : 0 → D : 0 → Y : 1 → C : Fix0 :
Lbl 1 : StatClear : A ÷ B – . 5 : Rnd : Ans DT :
B → M : A – B Σx → B : M → A :
D → M : X – D Σx → D : M → X :
C → M : Y – C Σx → C : M → Y :
B => Goto 1 :
Norm1 : A ◢ X ◢ Y
100 Bytes

巨よ猭

巨 ㄒ
―ㄢ计 a, b ぇ程そ计 (a, b), ―ㄏ au + bv = (a, b) い u, v 俱计秆. ― 12345, 67890 ぇ程そ计,
―ㄏ 12345u + 67890v = (12345, 67890) い u, v 俱计秆.
币笆祘Α Prog 1
块戈
a EXE b EXE 		12345 EXE 67890 EXE
陪ボ氮
GCD EXE
u EXE v 		15 EXE
11 EXE -2
( (12345, 67890) = 15;
12345 × 11 + 67890 × -2 = 15)

癘拘砰

A GCD
B 0
C v'
D u'
X u
Y v
M v

闽祘Α

  1. Greatest Common Divisor / 程そ计