**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**

This is all for this article. In the next article, we will be discussing Integer Factorization.

Thank You

## Comments

## Post a Comment