Greatest Common Divisor

is the largest integer that is both a divisor of and a divisor of . GCD Definition: Let and be integers.

  1. If and are not both zero, an integer is the greatest common divisor of and , written , when
    • is a common divisor of and ,and
    • for all integers , if is a common divisor of and , then .
  2. If and are both zero, we define .

Coprime Definition: Two integers and are coprime if

Propositions and Theorems

Proposition 1 For all real numbers , we have

Bounds By Divisibility (BBD) For all integers and , if and then .

Division Algorithm (DA) For all integers and positive integers , there exist unique integers and such that

GCD With Remainders (GCD WR) For all integers , , and , if , then .

This is used with the Extended Euclidean Algorithm (EEA).

GCD Characterization Theorem (GCD CT) For all integers and , and non-negative integers , if

  • is a common divisor of and , and
  • there exist integers and such that ,

then .

Bézout/Bezout’s Lemma (BL) (IMPORTANT) For all integers and , there exist integers and such that , where . Linear Diophantine Equation

Common Divisor Divides GCD (CDD GCD) For all integers , and , if and , then .

Coprimeness Characterization Theorem (CCT) For all integers and , if and only if there exist integers and such that .

Division by the GCD (DB GCD) For all integers and , not both zero, , where

Coprimeness and Divisibility (CAD) For all integers , and , if and , then .