greatest common divisor

Work in Progress

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

Coprimality

Sources