# 拡張ユークリッドの互除法
（拡張されたユークリッドの互除法）
## 定義
> $x, y$ を $0$ でない自然数とし、 $c = \mathrm{GCD}(x,y)$ とする。このとき
>
> $
> ax + by = c
> $
>
> となる整数 $a,b$ が存在する。そして、この $a,b$ は実際に計算することが出来る。
## ユークリッドの互除法から
[[ユークリッドの互除法]] からの導出
$
\begin{align}
&\mathrm{GCG}(13, 5) \\
\\
13 &= 2 \times 5 + 3 \tag{1} \\
5 &= 1 \times 3 + 2 \tag{2} \\
3 &= 2 + 1 \tag{3} \\
2 &= 2 \times 1 \\
\\
&\mathrm{CCG}(13, 5) = 1
\end{align}
$
$(1),(2),(3)$ を移項
$
\begin{align}
13 - 2 \times 5 &= 3 \tag{4} \\
5 - 1 \times 3 &= 2 \tag{5} \\
3 - 1 \times 2 &= 1 \tag{6}
\end{align}
$
$(5)$ を $(6)$ に代入
$
\begin{align}
1 &= 3 - 1 \times 2 \\
1 &= 3 - 1 \times (5 - 1 \times 3) \\
1 &= 2 \times 3 - 1 \times 5 \tag{7}
\end{align}
$
$(4)$ を $(7)$ に代入。 13 と 5 に注目してくくる
$
\begin{align}
1 &= 2 \times 3 - 1 \times 5 \\
1 &= 2 \times (13 - 2 \times 5) - 1 \times 5 \\
1 &= 2 \times 13 - 5 \times 5
\end{align}
$
$
2 \times 13 - 5 \times 5 = 1
$
（13 リットルの升と 5 リットルの升を使って 1 リットルを測ることができる）
定式化すると、冒頭の拡張ユークリッド互除法になる。
## Go による実装
### 再帰 ver
```go
package main
import "fmt"
// ax + by = GCD(a, b)
func extGCD(a, b int) (int, int, int) {
if b == 0 {
return a, 1, 0
}
gcd, x1, y1 := extGCD(b, a%b)
x := y1
y := x1 - (a/b)*y1
return gcd, x, y
}
func main() {
a := 119
b := 544
gcd, x, y := extGCD(a, b)
fmt.Printf("GCD: %d, x: %d, y: %d\n", gcd, x, y)
}
```
### 非再帰 ver
「[[mod 逆元を求める]]」のコードを参照。
### 逆元を求める
[[mod 逆元を求める]]
```go
func main() {
for i := 1; i < 13; i++ {
_, x, _ := extGCD(i, 13)
if x < 0 {
x += 13
}
fmt.Printf("%2d => %2d\n", i, x)
}
}
```