Highest Common Factor, Prime Factorization, and Lowest Common Multiple

Overview of Factors, Multiples, and Prime Decomposition

• The study of elementary number theory centers on the multiplicative properties of integers, focusing on factors, multiples, prime numbers, and their interactions.

• Factor (Divisor): An integer $d$ is a factor of an integer $n$ if there exists an integer $k$ such that $n = d \times k$. Equivalently, dividing $n$ by $d$ leaves a remainder of $0$.

• Multiple: An integer $m$ is a multiple of an integer $n$ if $m = n \times k$ for some integer $k$.

• Prime Number: An integer $p > 1$ whose only positive divisors are $1$ and $p$.

• Composite Number: A positive integer greater than $1$ that has at least one divisor other than $1$ and itself.

• Fundamental Theorem of Arithmetic: Every integer greater than $1$ can be uniquely represented as a product of prime powers, up to the order of the factors:   $n = p_1^{a_1} \times p_2^{a_2} \times \dots \times p_k^{a_k}$

Highest Common Factor (HCF)

• Definition: The Highest Common Factor (HCF), also known as the Greatest Common Divisor (GCD), of two or more non-zero integers is the largest positive integer that divides each of the numbers without leaving a remainder.

• Methods for Finding HCF:

  • Listing Divisors: Enumerate all positive divisors of each integer, identify common elements, and select the greatest value.

  • Prime Factorization: Express each number as a product of prime powers; the HCF is the product of the lowest power of each common prime factor:     $\text{HCF}(a, b) = \prod_i p_i^{\min(a_i, b_i)}$

• Problem 1: HCF of $18$ and $32$

  • Positive divisors of $18$: $\{1, 2, 3, 6, 9, 18\}$

  • Positive divisors of $32$: $\{1, 2, 4, 8, 16, 32\}$

  • Intersection of factor sets: $\{1, 2\}$

  • Prime factorization method:     $18 = 2^1 \times 3^2$     $32 = 2^5$     $\text{HCF}(18, 32) = 2^{\min(1, 5)} = 2^1 = 2$

  • Result: $2$

• Problem 2: HCF of $42$ and $63$

  • Positive divisors of $42$: $\{1, 2, 3, 6, 7, 14, 21, 42\}$

  • Positive divisors of $63$: $\{1, 3, 7, 9, 21, 63\}$

  • Intersection of factor sets: $\{1, 3, 7, 21\}$

  • Prime factorization method:     $42 = 2^1 \times 3^1 \times 7^1$     $63 = 3^2 \times 7^1$     $\text{HCF}(42, 63) = 3^{\min(1, 2)} \times 7^{\min(1, 1)} = 3^1 \times 7^1 = 21$

  • Result: $21$

• Problem: HCF of $120$ and $72$

  • Divisor listing for $120$ begins with: $1, 2, \dots$

  • Complete positive divisors of $120$: $\{1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120\}$

  • Complete positive divisors of $72$: $\{1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72\}$

  • Common divisors: $\{1, 2, 3, 4, 6, 8, 12, 24\}$

  • Prime factorization method:     $120 = 2^3 \times 3^1 \times 5^1$     $72 = 2^3 \times 3^2$     $\text{HCF}(120, 72) = 2^{\min(3, 3)} \times 3^{\min(1, 2)} = 2^3 \times 3^1 = 8 \times 3 = 24$

  • Result: $24$

Prime Factorization and Factor Trees

• Factor Tree Method: A recursive visual algorithm to decompose a composite number into its constituent prime factors by splitting composite nodes into pairs of factors until all terminal leaves are prime numbers.

• Problem 3: Prime Factors of $37$

  • Divisibility check: Tested primes up to $\sqrt{37} \approx 6.08$ (namely $2, 3, 5$) do not divide $37$.

  • Classification: $37$ is a prime number.

  • Prime factorization: $37 = 37$

• Problem 4: Prime Factors of $93$

  • Divisibility check: The sum of the digits is $9 + 3 = 12$, which is divisible by $3$.

  • Division: $93 \div 3 = 31$

  • Primality of quotient: $31$ is a prime number because no prime up to $\sqrt{31} \approx 5.57$ (namely $2, 3, 5$) divides it.

  • Prime factors: $3$ and $31$

  • Prime factorization: $93 = 3 \times 31$

• Prime Factorization of $84$ via Factor Tree:

  • Step 1: Decompose $84$ into a prime factor and a composite factor:     $84 = 2 \times 42$

  • Step 2: Decompose the composite node $42$:     $42 = 2 \times 21$

  • Step 3: Decompose the composite node $21$:     $21 = 3 \times 7$

  • Terminal prime leaves obtained: $2, 2, 3, 7$

  • Complete prime product:     $84 = 2 \times 2 \times 3 \times 7 = 2^2 \times 3 \times 7$

Sequences and Listings of Multiples

• Generating multiples requires systematically multiplying a base integer $n$ by successive natural numbers $k = 1, 2, 3, 4, \dots$.

• Multiples of Seven ($7$):

  • Computed by $7 \times k$:     $7 \times 1 = 7$     $7 \times 2 = 14$     $7 \times 3 = 21$     $7 \times 4 = 28$     $7 \times 5 = 35$

  • Sequence: $7, 14, 21, 28, 35$

• Multiples of Five ($5$):

  • Computed by $5 \times k$ for $k = 1$ through $k = 9$:     $5, 10, 15, 20, 25, 30, 35, 40, 45$

  • All multiples of $5$ conclude with the terminal units digit $0$ or $5$.

• Multiples of Nine ($9$):

  • Computed by $9 \times k$ for $k = 1$ through $k = 6$:     $9, 18, 27, 36, 45, 54$

  • The digital root of each multiple of $9$ is always $9$.

Lowest Common Multiple (LCM)

• Definition: The Lowest Common Multiple (LCM), or Least Common Multiple, of two non-zero integers $a$ and $b$ is the smallest positive integer that is divisible by both $a$ and $b$.

• Fundamental Relationship Between HCF and LCM:   $\text{HCF}(a, b) \times \text{LCM}(a, b) = |a \times b|$   $\text{LCM}(a, b) = \frac{|a \times b|}{\text{HCF}(a, b)}$

• Prime Factorization Formula for LCM:   $\text{LCM}(a, b) = \prod_i p_i^{\max(a_i, b_i)}$

• LCM Problem 1: Lowest Common Multiple of $3$ and $8$

  • Multiples of $3$:     $3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48$

  • Multiples of $8$:     $8, 16, 24, 32, 40, 48, 56, 64$

  • Identification of common multiples: The values occurring in both lists are $24$ and $48$.

  • Selection of the lowest common value: $24$

  • Prime factorization verification:     $3 = 3^1$     $8 = 2^3$     $\text{LCM}(3, 8) = 2^{\max(3, 0)} \times 3^{\max(0, 1)} = 2^3 \times 3^1 = 8 \times 3 = 24$

  • Result: $24$

• LCM Problem 2: Lowest Common Multiple of $9$ and $12$

  • Multiples of $9$:     $9, 18, 27, 36, 45, 54$

  • Multiples of $12$:     $12, 24, 36, 48$

  • Identification of common multiples: The lowest value appearing in both sequences is $36$.

  • Prime factorization verification:     $9 = 3^2$     $12 = 2^2 \times 3^1$     $\text{LCM}(9, 12) = 2^{\max(0, 2)} \times 3^{\max(2, 1)} = 2^2 \times 3^2 = 4 \times 9 = 36$

  • Verification via formula:     $\text{HCF}(9, 12) = 3$     $\text{LCM}(9, 12) = \frac{9 \times 12}{3} = \frac{108}{3} = 36$

  • Result: $36$

Header Values and Marginal Entries

• Marginal Quantity $74$: Numerical entry located in the top header row.

• Currency Quantity $\$3.70$: Value recorded alongside the header margin, representing an amount of three dollars and seventy cents.