diff options
-rw-r--r-- | euclide.go | 36 |
1 files changed, 36 insertions, 0 deletions
diff --git a/euclide.go b/euclide.go new file mode 100644 index 0000000..77fd2d9 --- /dev/null +++ b/euclide.go @@ -0,0 +1,36 @@ +package main + +import "fmt" + +func main() { + + N := 55 + D := 13 + + n := N + d := D + + l := make([]int, 0) + + for d != 0 { + t := n/d + l = append(l, t) + r := n%d + n,d=d,r + } + + fmt.Printf("PGCD(%d, %d) = %d\n", N, D, n) + fmt.Println(l, len(l)) + gcd := n + + n,d = 1, l[len(l)-1] + for i := len(l) - 1 ; i >= 0 ; i-- { + t := n+d*l[i] + n,d = d,t + } + if len(l) & 1 == 1 { + n,d=-n,-d + } + + fmt.Printf("%d*%d - %d*%d = %d = %d\n", N, n, D, d, gcd, n*N-d*D) +} |