Finding the GCD and LCM (the Euclidean Algorithm)

In this lesson you will learn how to find the greatest common divisor and least common multiple in Go with the Euclidean algorithm, and understand a mathematical algorithm built on recursion. This is for anyone searching for "Go GCD LCM implementation".

The Euclidean algorithm is an ancient, efficient way to find the greatest common divisor (GCD) of two numbers. You repeat "divide the larger by the smaller and carry on with the remainder" until the remainder reaches zero.

The sample code has gcd() call itself as gcd(b, a%b) until b == 0. From the relationship a * b / gcd(a, b), lcm() then reuses that result to find the least common multiple.

A common stumbling block for beginners is not knowing the relationship between the GCD and the LCM. Once you have the GCD, one multiplication and one division give you the LCM.

It is a famous algorithm that packs in the fundamentals of both mathematics and programming, and a very popular subject for practising recursion. For three or more numbers, apply gcd to them two at a time.

📖 Reference code

package main

import "fmt"

func gcd(a, b int) int {
    if b == 0 {
        return a
    }
    return gcd(b, a%b)
}

func lcm(a, b int) int {
    return a * b / gcd(a, b)
}

func main() {
    fmt.Println("GCD:", gcd(12, 18))
    fmt.Println("LCM:", lcm(4, 6))
}

✍️ Your code

Type your code, then press "Run"

🧪 This site can't compile or run Go directly, so it checks on the spot whether what you typed matches the reference code (scoring happens entirely in your browser — nothing is sent anywhere).