### GCD, LCM, and Euclid's Algorithm

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
This is all for this article. In the next article, we will be discussing Integer Factorization.

Thank You