Extended Euclidean Algorithm in Go

eea.go

package main

import "fmt"
import "os"
import "strconv"

// extended euclidean algorithm
// Example: `go run eea.go 35 15`
func main() {
	if len(os.Args) != 3 {
		fmt.Println("Provide your input and modulator integers as command line arguments.")
		os.Exit(1)
	}
	i := os.Args[1]
	m := os.Args[2]

	input, err := strconv.Atoi(i) // e.g. 35
	if err != nil {
		fmt.Println("Input must be an integer.")
		os.Exit(1)
	}
	modulator, err := strconv.Atoi(m) // e.g. 15
	if err != nil {
		fmt.Println("Modulator must be an integer.")
		os.Exit(1)
	}

	gcd, inverse := gcdExtended(input, modulator, 1,0,0,1)

	fmt.Printf("gcd(%d, %d) = %d with %d's inverse being %d\n", input, modulator, gcd, input, inverse)
	// Example
	// input = 35
	// modulator = 15
	// gcd result = 5
	// s2 = 1
	// (1*35)%15 = 5
}

func gcdExtended(a int, b int, s1 int, s2 int, t1 int, t2 int) (gcd int, inverse int) {
	q := a / b
	r := a - q * b
	s3 := s1 - q * s2
	t3 := t1 - q * t2

	if r == 0 {
		return b, s2
	}

	return gcdExtended(b, r, s2, s3, t2, t3)
}