Prime Numbers and Least Common Multiple (LCM)

• Least Common Multiple (LCM) and prime numbers are fundamental concepts in number theory

Prime Numbers

• A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself
• Prime numbers cannot be formed by multiplying two smaller natural numbers
• Examples of prime numbers include 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29
• The number 1 is not considered a prime number, as it only has one divisor (itself)

Identifying Prime Numbers

• To determine if a number n is prime, check for divisibility by all integers from 2 up to the square root of n
• If n is not divisible by any of these integers, then n is a prime number
• The square root serves as an upper limit because if n has a divisor larger than its square root, it must also have a divisor smaller than its square root

Prime Factorization

• Prime factorization is the process of expressing a composite number as a product of its prime factors
• Every composite number has a unique prime factorization
• The Fundamental Theorem of Arithmetic states this uniqueness
• To find the prime factorization of a number, divide it by the smallest prime number that divides it evenly
• Continue dividing the quotient by prime numbers until the quotient is 1
• The prime factorization is the product of all the prime divisors used in the process
• Example: The prime factorization of 28 is 2 x 2 x 7, or 2^2 x 7

Least Common Multiple (LCM)

• The Least Common Multiple (LCM) of two or more integers is the smallest positive integer that is divisible by each of the integers
• The LCM of 4 and 6 is 12, because 12 is the smallest positive integer that is divisible by both 4 and 6

Methods to Find the LCM

• Listing Multiples: List the multiples of each number until a common multiple is found; the smallest common multiple is the LCM
• Prime Factorization: Find the prime factorization of each number and take the highest power of each prime factor that appears in any of the factorizations; multiply these highest powers together to get the LCM
• Formula: For two numbers a and b, LCM(a, b) = (|a*b|) / GCD(a, b), where GCD(a, b) is the Greatest Common Divisor of a and b

Finding LCM using Listing Multiples

• List multiples of each number until a common multiple is found
• Example: Find the LCM of 6 and 8
  • Multiples of 6: 6, 12, 18, 24, 30, 36, 42, 48,...
  • Multiples of 8: 8, 16, 24, 32, 40, 48,...
• The smallest common multiple is 24, so LCM(6, 8) = 24

Finding LCM using Prime Factorization

• Find the prime factorization of each number
• Take the highest power of each prime factor that appears in any of the factorizations
• Multiply these highest powers together to get the LCM
• Example: Find the LCM of 12 and 18
  • Prime factorization of 12: 2^2 x 3
  • Prime factorization of 18: 2 x 3^2
• Highest powers: 2^2 and 3^2
• LCM(12, 18) = 2^2 x 3^2 = 4 x 9 = 36

Finding LCM using Formula

• For two numbers a and b, LCM(a, b) = (|a*b|) / GCD(a, b), where GCD(a, b) is the Greatest Common Divisor of a and b
• Example: Find the LCM of 24 and 36
  • GCD(24, 36) = 12
  • LCM(24, 36) = (24 * 36) / 12 = 864 / 12 = 72

Applications of LCM

• Arithmetic operations: LCM is used to find a common denominator when adding or subtracting fractions with different denominators
• Scheduling problems: LCM is used to determine when events will occur simultaneously
• If one event occurs every 6 days and another occurs every 8 days, they will occur together every LCM(6, 8) = 24 days
• Gear ratios: LCM can be used to determine the number of rotations needed for gears to return to their original position