Primes

Breaking Numbers into Rectangles

Imagine arranging square tiles into solid rectangles:

• $6$ tiles can form a $1 \times 6$ line or a $2 \times 3$ rectangle.
• $5$ tiles can only form a single line: $1 \times 5$.

The dimensions of these rectangles represent the factors of the number. Every integer greater than $1$ falls into one of two fundamental categories based on how many factors it possesses.

---

Defining Primes and Composites

We classify integers greater than $1$ strictly by their number of distinct positive factors:

• Prime Number: An integer greater than $1$ that has exactly two distinct positive factors: $1$ and itself.
  $\text{Examples: } 2, 3, 5, 7, 11, 13, 17, 19, \dots$
• Composite Number: An integer greater than $1$ that has more than two distinct positive factors.
  $\text{Examples: } 4, 6, 8, 9, 10, 12, 14, 15, \dots$

Key Observation: $2$ is the only even prime number. Any other even number is divisible by $2$, giving it at least three factors: $1$, $2$, and itself.

---

Why is $1$ Neither Prime Nor Composite?

A frequent point of confusion is the number $1$. Let us look at its factor count:

$\text{Factors of } 1 = \{1\}$

• It cannot be prime, because a prime must have exactly two distinct factors.
• It cannot be composite, because a composite must have more than two factors.
• Therefore, $1$ is special: it is neither prime nor composite.

---

Worked Example: Classifying Numbers

Problem: Classify each of the following as prime, composite, or neither:
$1, \quad 29, \quad 51, \quad 91$

Step-by-step Solution:

1. $1$:
   • Factors: $\{1\}$ (only one factor). $\rightarrow$ Neither prime nor composite.
2. $29$:
   • Test divisibility: Not even (not div by $2$). Sum of digits is $2+9 = 11$ (not div by $3$). Does not end in $0$ or $5$ (not div by $5$).
   • Factors: only $1$ and $29$. $\rightarrow$ Prime.

---

Worked Example (Continued)

1. $51$:
   • Quick check using divisibility rules: sum of digits is $5 + 1 = 6$, which is divisible by $3$.
   • Since $51 = 3 \times 17$, its factors include $1, 3, 17, 51$. $\rightarrow$ Composite.
2. $91$:
   • Not divisible by $2, 3$, or $5$.
   • Testing the next prime, $7$: $91 \div 7 = 13$ exactly.
   • Since $91 = 7 \times 13$, it has at least four factors: $1, 7, 13, 91$. $\rightarrow$ Composite.

Teacher's Pitfall Alert: Numbers like $51$ and $91$ look prime at first glance because they are odd and don't end in $5$. Always run your divisibility tests ($3$, $7$, etc.) before deciding!

---

Summary of the Classification

Every positive integer $\mathbb{Z}^+$ is partitioned into three distinct groups:

• To test if $n$ is prime: Check if any prime $p \le \sqrt{n}$ divides $n$.
• If no such prime divides $n$, then $n$ is prime.

The Building Blocks of Numbers

Every integer greater than $1$ is either a prime or a composite number:

• Prime numbers ($2, 3, 5, 7, 11, 13, \dots$) have exactly two distinct positive factors: $1$ and the number itself. (Note: $1$ is not a prime.)
• Composite numbers can be broken down into products of smaller positive integers.

According to the Fundamental Theorem of Arithmetic, any composite number can be broken down uniquely into a product of prime numbers—its prime factors.

To write these products efficiently, we collect repeated factors using index notation (powers):
$72 = 2 \times 2 \times 2 \times 3 \times 3 = 2^3 \times 3^2$

---

Method 1: The Factor Tree

A factor tree breaks a composite number down step by step along branching paths until only prime numbers remain at the ends (the "leaves").

• Pick any pair of factors to begin (e.g., $6 \times 10$ or $4 \times 15$).
• Continue splitting any non-prime branches.
• Circle the prime numbers at the tips. Regardless of your starting pair, the final primes are always identical: $2 \times 2 \times 3 \times 5 = 2^2 \times 3 \times 5$.

---

Method 2: Repeated Division (The Ladder Method)

For larger numbers, a systematic column layout prevents missing factors. We divide repeatedly by the smallest possible prime factor until the quotient is $1$.

• Use quick divisibility tests:
  • Even? Divide by $2$.
  • Sum of digits divisible by $3$? Divide by $3$.
  • Ends in $0$ or $5$? Divide by $5$.
• Read all divisor numbers along the left column: $2 \times 2 \times 3 \times 5 = 2^2 \times 3 \times 5$.

---

Worked Example: Factorising a Three-Digit Number

Problem: Express $360$ as a product of its prime factors in index notation.

Step-by-step solution via repeated division:

1. $360$ is even $\rightarrow$ divide by $2$ to get $180$.
2. $180$ is even $\rightarrow$ divide by $2$ to get $90$.
3. $90$ is even $\rightarrow$ divide by $2$ to get $45$.
4. $45$ is odd; $4+5=9$ (divisible by $3$) $\rightarrow$ divide by $3$ to get $15$.
5. $15$ divides by $3$ to get $5$.
6. $5$ is prime $\rightarrow$ divide by $5$ to leave $1$.

---

Worked Example: Expressing in Index Notation

Collecting all divisor primes from the left column:
$360 = \underbrace{2 \times 2 \times 2}_{\text{three } 2\text{s}} \times \underbrace{3 \times 3}_{\text{two } 3\text{s}} \times \underbrace{5}_{\text{one } 5}$

Writing in index notation with ascending bases:
$360 = 2^3 \times 3^2 \times 5$

Teacher's Note / Common Pitfall: Only divide by prime numbers. If you divide $360$ by composite numbers like $4$ or $9$, the outside factors will not be primes, and you will have to factorise them again later.

Beyond listing: Numbers as prime building blocks

Listing all factors or multiples is feasible for small numbers like $12$ and $18$, but quickly becomes inefficient for numbers like $168$ or $420$.

Every positive integer greater than $1$ can be expressed uniquely as a product of prime numbers. Think of these primes as the fundamental "building blocks" (or DNA) of the number:

• $24 = 2 \times 2 \times 2 \times 3 = 2^3 \times 3$
• $36 = 2 \times 2 \times 3 \times 3 = 2^2 \times 3^2$

By comparing their prime building blocks directly, we can find both:

1. Highest Common Factor (HCF): The largest collection of blocks they share.
2. Lowest Common Multiple (LCM): The smallest collection of blocks that contains both.

---

Visualising common primes: The Venn diagram

Placing prime factors into a Venn diagram clarifies the relationship between shared factors and multiples:

• Intersection (Overlap) gives the HCF:
  $\text{HCF} = 2 \times 2 \times 3 = 12$
• Union (All regions) gives the LCM:
  $\text{LCM} = 2 \times (2 \times 2 \times 3) \times 3 = 72$

---

The index rule: Minimum vs. maximum powers

Instead of drawing circles, write the numbers in index form with prime bases aligned:

$24 = 2^3 \times 3^1$
$36 = 2^2 \times 3^2$

We apply two complementary rules:

• $\text{HCF}$ takes the lowest power of common prime factors:

  • Must divide into both numbers $\implies$ limited by the smaller exponent.
  • $\text{HCF} = 2^{\min(3,2)} \times 3^{\min(1,2)} = 2^2 \times 3^1 = 12$

• $\text{LCM}$ takes the highest power of every prime factor present:

  • Must be divisible by both numbers $\implies$ must satisfy the larger exponent.
  • $\text{LCM} = 2^{\max(3,2)} \times 3^{\max(1,2)} = 2^3 \times 3^2 = 72$

---

Worked example: Finding HCF and LCM of 72 and 120

Problem:
Find the Highest Common Factor (HCF) and Lowest Common Multiple (LCM) of $72$ and $120$. Leave your answers in prime index notation, then evaluate them.

Step 1: Express each number as a product of prime factors

• Use repeated division by the smallest primes ($2, 3, 5$):
  $72 = 8 \times 9 = 2^3 \times 3^2$
  $120 = 12 \times 10 = (2^2 \times 3) \times (2 \times 5) = 2^3 \times 3^1 \times 5^1$

Step 2: Align the bases vertically

$$\begin{aligned} 72 &= 2^3 \times 3^2 \times 5^0 \\ 120 &= 2^3 \times 3^1 \times 5^1 \end{aligned}$$

(Writing $5^0 = 1$ helps track non-shared factors clearly).

---

Worked example: Applying the index rule

Comparing exponents column by column:

$$\begin{aligned} 72 &= 2^{\mathbf{3}} \times 3^{\mathbf{2}} \times 5^{\mathbf{0}} \\ 120 &= 2^{\mathbf{3}} \times 3^{\mathbf{1}} \times 5^{\mathbf{1}} \end{aligned}$$

• Finding the HCF (minimum power of shared primes):
  $\text{HCF} = 2^{\min(3,3)} \times 3^{\min(2,1)} = 2^3 \times 3^1 = 8 \times 3 = \mathbf{24}$
  (Factor $5$ is omitted because $5^0 = 1$, as $5$ does not divide $72$.)

• Finding the LCM (maximum power of all primes):
  $\text{LCM} = 2^{\max(3,3)} \times 3^{\max(2,1)} \times 5^{\max(0,1)} = 2^3 \times 3^2 \times 5^1 = 8 \times 9 \times 5 = \mathbf{360}$

Common Pitfall: Students often confuse the words Highest and Lowest. Remember: the Highest Common Factor must be small enough to divide both numbers (take minimum powers); the Lowest Common Multiple must be large enough to contain both numbers (take maximum powers).