Capstok — learn by doing

Why this matters

The least common multiple is the multiplicative dual of the gcd: where the gcd captures the largest shared factor, the lcm captures the smallest shared multiple. The reason it earns its own task is the identity $\mathrm{lcm}(a, b) \cdot \gcd(a, b) = |ab|$ , which lets you compute the lcm without ever factoring. That's the same algorithmic trick used in the rest of the course: phrase a 'multiplicative' question in terms of the gcd, then apply Euclid. The lcm itself shows up when synchronising periodic events (clock signals, polling intervals), in the Chinese remainder theorem's modulus, and in the order of products in a group — useful tools you'll meet in later modules.

Demo

The least common multiple $\mathrm{lcm}(a, b)$ is the smallest positive integer that is a multiple of both $a$ and $b$ . The fundamental identity ties it to the gcd: $\mathrm{lcm}(a, b) \cdot \gcd(a, b) = |a \cdot b|$ . So once you can compute gcd, lcm is one division away.

\mathrm{lcm}(a, b) = \frac{|ab|}{\gcd(a, b)}, \quad \mathrm{lcm}(a, 0) = 0

Try it yourself

Compute $\mathrm{lcm}(12, 18)$ by hand: list multiples of 12 ( $12, 24, 36, \ldots$ ) and 18 ( $18, 36, 54, \ldots$ ), find the smallest in both. Confirm it equals $\frac{12 \cdot 18}{\gcd (12, 18}$ .

Prompt your AI

Use these three in order. Each builds on the one before.

1. Basics & terminology

In one paragraph, define the least common multiple and contrast it with the greatest common divisor — what is each one capturing about two integers? Give a real-world example of when you'd want lcm (hint: gears, periodic signals, scheduling).

2. Why it works (the mechanism)

Walk me through *why* the identity $\mathrm{lcm}(a, b) \cdot \gcd(a, b) = |ab|$ holds. The cleanest proof uses unique prime factorisation (which we'll meet in task 7) — sketch it, prime by prime.

3. Advanced — application & what's next

Generalise the gcd–lcm identity to three or more integers. Is it true that $\gcd(a, b, c) \cdot \mathrm{lcm}(a, b, c) = |abc|$? Test it on $(2, 3, 4)$. If not, what's the correct identity?

References

)

=

\frac{216}{6}

=

36

\frac{12 \cdot 18}{\gcd(12, 18)} = \frac{216}{6} = 36

// main.go — run: go run main.go
package main

import "fmt"

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

func lcm(a, b int) int {
	if a == 0 || b == 0 {
		return 0
	}
	if a < 0 {
		a = -a
	}
	if b < 0 {
		b = -b
	}
	return a / gcd(a, b) * b
}

// n-ary lcm via fold
func lcmAll(nums ...int) int {
	result := nums[0]
	for _, n := range nums[1:] {
		result = lcm(result, n)
	}
	return result
}

func main() {
	fmt.Println(lcm(4, 6))        // 12
	fmt.Println(lcm(21, 6))       // 42
	fmt.Println(lcm(1071, 462))   // 23562 = 1071*462 / 21

	// n-ary lcm
	fmt.Println(lcmAll(4, 6, 8, 9)) // 72
}

Run: go run main.go

Least common multiple