ユークリッドのアルゴリズム
l
入力:整数
a,b
⇒出力:整数
c, x ,y
l
a
と
b
の最大公約数
gcd (
a,b
) = c
l
c = ax + by
を満たす
x, y
l
高速に
計算
l
例
1
.
a =
5
, b =
3
の場合
l
1
=
5x + 3y
x = 2 , y =
‐
3
l
例
2
.
e
= a =
23
, m
= b =
192
の場合
l
1 = 23x + 192 y
x = 167 , y =
‐
20