GCD and LCM

GCD and LCM#

The Greatest Common Divisor (GCD) of two numbers is the largest positive integer that divides both numbers without leaving a remainder. The Least Common Multiple (LCM) of two numbers is the smallest positive integer that is divisible by both numbers.

Finding the GCD#

To find the GCD of two numbers \(a\) and \(b\), we can use the Euclidean Algorithm:

  1. Divide \(a\) by \(b\): Compute the quotient and remainder.

  2. Replace \(a\) with \(b\) and \(b\) with the remainder: Repeat the process until the remainder is 0.

  3. GCD is the last non-zero remainder.

Finding the LCM#

To find the LCM of two numbers \(a\) and \(b\), we can use the relationship between GCD and LCM:

\[ \text{LCM}(a, b) = \frac{|a \times b|}{\text{GCD}(a, b)} \]
### Functions:
Hide code cell source 
import sympy as sp
from sympy import *
from math import gcd
import random

def find_gcd_lcm(a, b):
    gcd = sp.gcd(a, b)
    lcm = a * b // gcd
    print(f"GCD of {a} and {b} is {gcd}")
    print(f"LCM of {a} and {b} is {lcm}")

Examples:#

Finding the GCD and LCM of \(44\) and \(12\)#

a = 44
b = 12

find_gcd_lcm(a, b)

GCD of 44 and 12 is 4
LCM of 44 and 12 is 132

Explanation

To find the GCD of \(44\) and \(12\), we can use the Euclidean Algorithm:

  1. Divide \(44\) by \(12\):

\[ 44 = 12 \times 3 + 8 \]

  1. Replace \(44\) with \(12\) and \(12\) with \(8\):

\[ 12 = 8 \times 1 + 4 \]

  1. Replace \(12\) with \(8\) and \(8\) with \(4\):

\[ 8 = 4 \times 2 + 0 \]

  1. The GCD is the last non-zero remainder:

\[ \text{GCD}(44, 12) = 4 \]

Finding the LCM

To find the LCM of \(44\) and \(12\), use the relationship between GCD and LCM:

\[ \text{LCM}(44, 12) = \frac{|44 \times 12|}{\text{GCD}(44, 12)} = \frac{528}{4} = 132 \]

Finding the GCD and LCM of \(15\) and \(25\)#

a = 15
b = 25

find_gcd_lcm(a, b)

GCD of 15 and 25 is 5
LCM of 15 and 25 is 75

Explanation

To find the GCD of \(15\) and \(25\), we can use the Euclidean Algorithm:

  1. Divide \(25\) by \(15\):

\[ 25 = 15 \times 1 + 10 \]

  1. Replace \(25\) with \(15\) and \(15\) with \(10\):

\[ 15 = 10 \times 1 + 5 \]

  1. Replace \(15\) with \(10\) and \(10\) with \(5\):

\[ 10 = 5 \times 2 + 0 \]

  1. The GCD is the last non-zero remainder:

\[ \text{GCD}(15, 25) = 5 \]

Finding the LCM

To find the LCM of \(15\) and \(25\), use the relationship between GCD and LCM:

\[ \text{LCM}(15, 25) = \frac{|15 \times 25|}{\text{GCD}(15, 25)} = \frac{375}{5} = 75 \]

Finding the GCD and LCM of \(30\) and \(45\)#

a = 30
b = 45

find_gcd_lcm(a, b)

Explanation

To find the GCD of \(30\) and \(45\), we can use the Euclidean Algorithm:

  1. Divide \(45\) by \(30\):

\[ 45 = 30 \times 1 + 15 \]

  1. Replace \(45\) with \(30\) and \(30\) with \(15\):

\[ 30 = 15 \times 2 + 0 \]

  1. The GCD is the last non-zero remainder:

\[ \text{GCD}(30, 45) = 15 \]

Finding the LCM

To find the LCM of \(30\) and \(45\), use the relationship between GCD and LCM:

\[ \text{LCM}(30, 45) = \frac{|30 \times 45|}{\text{GCD}(30, 45)} = \frac{1350}{15} = 90 \]

Finding the GCD and LCM of \(21\) and \(14\)#

a = 21
b = 14

find_gcd_lcm(a, b)

Explanation

To find the GCD of \(21\) and \(14\), we can use the Euclidean Algorithm:

  1. Divide \(21\) by \(14\):

\[ 21 = 14 \times 1 + 7 \]

  1. Replace \(21\) with \(14\) and \(14\) with \(7\):

\[ 14 = 7 \times 2 + 0 \]

  1. The GCD is the last non-zero remainder:

\[ \text{GCD}(21, 14) = 7 \]

Finding the LCM

To find the LCM of \(21\) and \(14\), use the relationship between GCD and LCM:

\[ \text{LCM}(21, 14) = \frac{|21 \times 14|}{\text{GCD}(21, 14)} = \frac{294}{7} = 42 \]
Contents