greatest common divisor
Summary
Concept
Greatest common divisor(GCD)
- largest divisor of two integers
Euclidean invariance
- GCD is invariant under euclidean division
- basis for the euclidean algorithm
we generalise
to represent an arbitrary common divisor, essentially the set of divisors between and is identical, so we can ignore the max condition in the GCD
Bezout’s identity
- Common-divisor maximum under divisibility
- Positive generator of the ideal
in - Minimal positive integer representable as an integer linear combination