LCM and GCD

LCM and GCD

The Least Common Multiple (LCM) and Greatest Common Divisor (GCD) are two fundamental concepts in number theory. They are used to find common multiples and divisors of integers, and they have important applications in solving problems related to divisibility, fractions, and many other areas of mathematics.

---

1. Greatest Common Divisor (GCD)

The GCD of two integers $a$ and $b$ is the largest positive integer that divides both $a$ and $b$ without leaving a remainder. The GCD is also known as the Greatest Common Factor (GCF).

Formal Definition:

The GCD of two integers $a$ and $b$, denoted by $\gcd(a, b)$, is the largest integer $d$ such that:

$$d \mid a \quad \text{and} \quad d \mid b$$

This means that $d$ divides both $a$ and $b$ exactly.

Example:

Find $\gcd(12, 18)$:

• The divisors of 12: $1, 2, 3, 4, 6, 12$
• The divisors of 18: $1, 2, 3, 6, 9, 18$

The common divisors of 12 and 18 are $1, 2, 3, 6$, and the greatest of these is 6. Therefore:

$$\gcd(12, 18) = 6$$

Properties of GCD:

• Commutative: $\gcd(a, b) = \gcd(b, a)$
• Associative: $\gcd(a, \gcd(b, c)) = \gcd(\gcd(a, b), c)$
• Distributive over LCM: $$\gcd(a, b) \times \text{lcm}(a, b) = |a \times b|$$

---

2. Least Common Multiple (LCM)

The LCM of two integers $a$ and $b$ is the smallest positive integer that is divisible by both $a$ and $b$. In other words, it is the smallest number that both $a$ and $b$ divide into exactly.

Formal Definition:

The LCM of two integers $a$ and $b$, denoted by $\text{lcm}(a, b)$, is the smallest integer $m$ such that:

$$a \mid m \quad \text{and} \quad b \mid m$$

This means that $m$ is divisible by both $a$ and $b$.

Example:

Find $\text{lcm}(12, 18)$:

• The multiples of 12 are $12, 24, 36, 48, 60, \dots$
• The multiples of 18 are $18, 36, 54, 72, \dots$

The smallest common multiple of 12 and 18 is 36. Therefore:

$$\text{lcm}(12, 18) = 36$$

Properties of LCM:

• Commutative: $\text{lcm}(a, b) = \text{lcm}(b, a)$
• Associative: $\text{lcm}(a, \text{lcm}(b, c)) = \text{lcm}(\text{lcm}(a, b), c)$
• Distributive over GCD: $$\gcd(a, b) \times \text{lcm}(a, b) = |a \times b|$$

---

3. Relationship Between LCM and GCD

There is a key relationship between the LCM and GCD of two numbers. It is given by:

$$\gcd(a, b) \times \text{lcm}(a, b) = |a \times b|$$

This means that the product of the GCD and the LCM of two numbers is equal to the product of the numbers themselves.

Example:

Let’s verify this relationship for $a = 12$ and $b = 18$:

We know:

• $\gcd(12, 18) = 6$
• $\text{lcm}(12, 18) = 36$

Now, check the relationship:

$$\gcd(12, 18) \times \text{lcm}(12, 18) = 6 \times 36 = 216$$

and

$$|12 \times 18| = |216| = 216$$

Thus, the equation holds true:

$$6 \times 36 = 12 \times 18$$

---

4. Methods to Calculate GCD and LCM

Euclidean Algorithm (for GCD)

The Euclidean Algorithm is an efficient method for computing the GCD of two numbers. It works by repeatedly applying the division algorithm and replacing the larger number by the remainder until the remainder is zero. The last non-zero remainder is the GCD.

Steps:

1. Divide the larger number by the smaller number.
2. Replace the larger number with the remainder from the division.
3. Repeat until the remainder is zero. The GCD is the last non-zero remainder.

Example: Find $\gcd(48, 18)$

1. Divide 48 by 18:

   $$48 \div 18 = 2 \quad \text{(quotient)}, \quad 48 - 2 \times 18 = 12 \quad \text{(remainder)}$$

   So, $\gcd(48, 18) = \gcd(18, 12)$.

2. Divide 18 by 12:

   $$18 \div 12 = 1 \quad \text{(quotient)}, \quad 18 - 1 \times 12 = 6 \quad \text{(remainder)}$$

   So, $\gcd(18, 12) = \gcd(12, 6)$.

3. Divide 12 by 6:

   $$12 \div 6 = 2 \quad \text{(quotient)}, \quad 12 - 2 \times 6 = 0 \quad \text{(remainder)}$$

   The remainder is zero, so the GCD is 6.

Thus, $\gcd(48, 18) = 6$.

Finding LCM Using GCD:

The LCM can be calculated using the formula:

$$\text{lcm}(a, b) = \frac{|a \times b|}{\gcd(a, b)}$$

Example:

Find $\text{lcm}(12, 18)$:

We already know that:

• $\gcd(12, 18) = 6$
• $|12 \times 18| = 216$

Now, using the formula for LCM:

$$\text{lcm}(12, 18) = \frac{216}{6} = 36$$

Thus, $\text{lcm}(12, 18) = 36$.

---

5. Applications of LCM and GCD

1. Simplifying Fractions:

   • The GCD is used to simplify fractions. For example, to simplify $\frac{12}{18}$, divide both the numerator and the denominator by $\gcd(12, 18) = 6$:
   $$\frac{12}{18} = \frac{12 \div 6}{18 \div 6} = \frac{2}{3}$$

2. Finding Common Denominators:

   • When adding or subtracting fractions, the LCM of the denominators is used to find a common denominator.

3. Solving Diophantine Equations:

   • Diophantine equations, which are equations that seek integer solutions, often involve the GCD and LCM.

4. Cryptography:

   • In encryption algorithms like RSA, the GCD plays a crucial role in finding keys and ensuring security.

5. Scheduling Problems:

   • The LCM is used in problems where you need to find common intervals of recurring events (e.g., two events repeating every 12 days and 18 days will both coincide every $\text{lcm}(12, 18) = 36$ days).

---

6. Conclusion

The GCD is the largest divisor shared by two numbers, while the LCM is the smallest multiple shared by the two numbers. The relationship between the GCD and LCM is important, as it helps simplify many number-theoretic problems. The Euclidean algorithm provides an efficient way to compute the GCD, and once the GCD is known, the LCM can be easily calculated. These concepts have wide applications in number theory, cryptography, scheduling, and many other areas.