Open this lesson in your favourite AI. It'll walk you through the why, explain the demo, and quiz you on the try-it list.
The greatest common divisor of two integers is the single number that captures their shared multiplicative structure, and it shows up everywhere downstream: when you reduce a fraction, when you check whether an element has a multiplicative inverse modulo , when you compute the order of an element in a cyclic group, when RSA picks a public exponent coprime to . The reason to define it carefully now — as 'the largest positive integer dividing both' — is that the next two tasks will give you a recursive identity and an algorithm that compute it without any factoring. That algorithm is the workhorse of computational number theory, and this definition is what it computes.
The greatest common divisor of two integers, not both zero, is the largest positive integer that divides both. By convention and . Two integers are coprime (or relatively prime) when .
math.gcd(1071, 462) and verify on paper that 21 divides both, and that no integer between 22 and 462 divides both.math.gcd(60, 84) == 12 matches the largest.gcd_naive(10**6, 10**6 - 1) and time it; then compute math.gcd(10**6, 10**6 - 1). The naive version should be visibly slower — that motivates Euclid's algorithm in the next task.Use these three in order. Each builds on the one before.
In one paragraph, explain what the greatest common divisor of two integers is and give two examples — one where the gcd is 1 (coprime) and one where it isn't. Why does it make sense to define $\gcd(a, 0) = |a|$?
Walk me through why the gcd, defined as 'largest common divisor,' is the *same* number as the smallest positive integer of the form $as + bt$ for integers $s, t$ (Bézout's identity, which we'll meet shortly). Sketch the argument both directions.
Why is computing $\gcd(a, b)$ via the definition (try every integer up to $\min(|a|, |b|)$) infeasible for the integers used in cryptography (e.g. 2048-bit RSA moduli)? Estimate the time complexity of the naive algorithm versus what we'll do next, in concrete numbers.
// main.go — run: go run main.go
package main
import (
"fmt"
"math/big"
)
func gcdNaive(a, b int) int {
if a < 0 {
a = -a
}
if b < 0 {
b = -b
}
if a == 0 && b == 0 {
return 0
}
smaller := a
if b < smaller {
smaller = b
}
result := 1
for d := 1; d <= smaller; d++ {
if a%d == 0 && b%d == 0 {
result = d
}
}
return result
}
func main() {
gcd := func(a, b int64) int64 {
return new(big.Int).GCD(nil, nil, big.NewInt(a), big.NewInt(b)).Int64()
}
fmt.Println(gcd(48, 18)) // 6
fmt.Println(gcd(1071, 462)) // 21
fmt.Println(gcd(13, 27)) // 1 -> 13 and 27 are coprime
fmt.Println(gcd(0, 17)) // 17
fmt.Println(gcd(-48, 18)) // 6 -> sign-insensitive
// Naive definition-based gcd (don't use this for big numbers)
fmt.Println(gcdNaive(48, 18)) // 6 — agrees with big.Int.GCD
}go run main.go