Euclidean - Number Theory

Number Theory

• Euclidean division, the division with produces a quotient and a remainder
• Euclidean algorithm, a method for finding greatest common divisors
• Extended Euclidean algorithm, a method for solving the Diophantine equation ax + by = d where d is the greatest common divisor of a and b.
• Euclid's lemma: if a prime number divides a product of two numbers, then it divides at least one of those two numbers.
• Euclidean domain, a ring in which Euclidean division may be defined, which allows Euclid's lemma to be true and the Euclidean algorithm and the extended Euclidean algorithm to work