From 90dcb82a51653df4e0b5f41e7dcff0d17c7062fe Mon Sep 17 00:00:00 2001
From: ache <ache@ache.one>
Date: Mon, 4 Feb 2019 15:54:32 +0100
Subject: =?UTF-8?q?Add=20euclide=20=C2=AF\=5F(=E3=83=84)=5F/=C2=AF?=
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

---
 euclide.go | 36 ++++++++++++++++++++++++++++++++++++
 1 file changed, 36 insertions(+)
 create mode 100644 euclide.go

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)
+}
-- 
cgit v1.2.3