ユークリッドの互除法

1func gcd(m, n int) int {
2	for n != 0 {
3		m, n = n, m%n
4	}
5	return m
6}
7

 1func extgcd(m, n int) (int, int, int) {
 2	x, y := 1, 0
 3	u, v := 0, 1
 4	for n != 0 {
 5		k := m / n
 6		m, n = n, m-k*n
 7		x, u = u, x-k*u
 8		y, v = v, y-k*v
 9	}
10	return m, x, y
11}
12