GCD, LCM, and Euclid's Algorithm

Things to be discussed in this article
  • Greatest Common Divisor
    • Introduction
    • Properties of GCD
    • Algorithm to find GCD
      • Basic
      • Euclid's Algorithm ( Find's GCD in O( log( min(a,b) ) ) time Complexity ).
  • Least Common Multiple
  • Practice Problems
Greatest Common Divisor ( GCD )
  • Introduction:
    • The greatest common divisor of two integers a and b, that are not both zero is the largest integer which divides both a and b.
    • The GCD of a and b is written as (a,b).
      • (4,8) = 4
      • (3,5) = 1
    • Note: The integers a and b are called relatively prime if a and b have GCD = 1.
Some note before we proceed further,
  • Proposition 1:
    • If a, b, m, and n are integers, and if c|a and c|b, then c|(ma + nb).
      • a|b means ( a divides b ) 
    • Proof:
      • Since c|a and c|b, there are integers e and f such that a=ce and b=cf. Hence ma + nb = mce + ncf = c(me + nf). Consequently, we see that c | (ma + nb ).
  • Division Algorithm
    • If a and b are integers such that b>0 , then there are unique integers q and r such that a = bq + r with 0 ≤ r < b.
We will be using the above Proposition 1 to prove the Properties of GCD.
  • Properties of GCD
    • Let a, b, and c be integers with (a,b)=d, then
      • ( a/d, b/d ) = 1
        • We are given that (a,b)=d, we need to show that a/d and b/d have no common positive divisors other than 1. Assume that e is a positive integer such that e|(a/d) and e|(b/d). Then, there are integers k and l with a/d=ke and b/d = le, such that a=dek and b=del. Hence, de is a common divisor of a and b. Since d is the greatest common divisor of a and b, e must be 1. Consequently, (a/d,b/d)=1.
      • ( a + cb, b ) = ( a, b )
        • Let e be a common divisor of a and b, then by Proposition 1, we see that e|(a+cb). So e is a common divisor of a+cb and b. If f is common divisor of a+cb and b, then by Proposition 1, we see that f divides (a+cb) - cb = a, so f is common  divisor of a and b, Hence (a+cb)=(a,b)
  • Algorithms to find GCD
    • Basic Algorithm
      • Let us understand this through an example. Let a=12 and b=4, write factors of a and b.
      • 12 = 1, 2, 3, 4, 6 , 12
      • 4 = 1, 2, 4
      • Pick the largest factor which is common to both 12 and 4 that will be the GCD.
      • Here it is 4.
    • Euclid's Algorithm
      • The idea behind Euclid's algorithm is (a, b) = (b, a%b ). It will recurse until a%b = 0.
      • Example: a=24 and b=5
        • STEP1; 24 = 4*5 + 4
        • STEP2: 5   = 1*4 + 1
        • STEP3: 4   = 2*1 + 0   // GCD( 24, 5 ) = 1
      • This is Long Division method approach to find GCD/ HCF ( Highest Common Factor ).
  • Euclid's Algorithm Implementation in C++
  • Built-in Functions.
    • C/ C++
      • We can use __gcd(a,b) to find (a,b).
    • C++17
      • Here we can simply use gcd(a,b) to find (a,b).
      • Data type in both cases should be an integer.
Least Common Multiple ( LCM )
  • Least Common Multiple
    • The least common multiple of two integers a and b is the lowest positive integer which is multiple of both a and b.
    • LCM(a,b) = a*b / GCD(a,b)  // We will prove this in folowing articles.
      • Example: let a=4 and b=12
      • Write factors of a and b
      • 4  = 1, 2, 4
      • 12= 1, 2, 3, 4, 6, 12
      • GCD(4,12) = 4
      • LCM = 4*12 / GCD (4, 12 ) = 48/4 = 12
    • In C++17 we have built-in function to find LCM as lcm(a,b). This will be returning the least common multiple of a and b.
Practice Problems
  1. GCD and LCM ( CodeChef )
This is all for this article. In the next article, we will be discussing Integer Factorization.

Thank You

Comments