GCD Definition and Properties

Number Theory · Axiom Academy

LESSON GCD Definition and Properties Understanding the greatest common divisor and its fundamental properties The greatest common divisor (GCD) of two integers a and b is the largest positive integer that divides both a and b. d divides both a and b (d | a and d | b) If c divides both a and b, then c divides d (c ≤ d) Common Notation: We write gcd(a,b) or sometimes (a,b) to denote the greatest common divisor. The GCD has several important algebraic properties that make it easier to work with: Commutativity: gcd(a,b) = gcd(b,a) Identity with zero: gcd(a,0) = |a| for a ≠ 0 Identity with one: gcd(a,1) = 1 for any integer a Scaling: gcd(ka, kb) = k · gcd(a,b) for k > 0 3. Coprime (Relatively Prime) Numbers Two integers are called coprime or relatively prime if their greatest common divisor is 1. 8 and 15 are coprime: gcd(8,15) = 1 21 and 35 are NOT coprime: gcd(21,35) = 7 Any two consecutive integers are coprime: gcd(n, n+1) = 1 4. GCD from Prime Factorizations When we know the prime factorizations of two numbers, we can find their GCD by taking the minimum exponent for each prime factor. Example: For 360 = 2³ · 3² · 5 and 504 = 2³ · 3² · 7, we have gcd(360,504) = 2³ · 3² = 72. Let's find gcd(48, 180) using prime factorizations: Step 2: Take minimum exponents for each prime For prime 2: min(4, 2) = 2, so 2² For prime 3: min(1, 2) = 1, so 3¹ For prime 5: min(0, 1) = 0, so 5⁰ = 1 (not included) gcd(48, 180) = 2² · 3¹ = 4 · 3 = 12

This is the written version of the interactive lesson above. See the full Number Theory course.