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)
}