Foundations of Number Theory

TL;DR

Number theory explores properties of whole numbers, primarily focusing on primes, factors, and multiples. Understanding these basics helps you break down complex numbers into simpler components. This skill is crucial for many areas of math and computer science.

1. The Mental Model

Think of numbers as building blocks. Some blocks (prime numbers) can't be broken down further, while others are built from these prime blocks. We're learning how to find these core blocks and how to combine them.

2. The Core Material

Number theory is all about understanding integers – the whole numbers (positive, negative, or zero). We'll focus on positive integers for now.

What are Divisors and Multiples?

Photo by https://kaboompics.com/ on Pexels

A divisor (or factor) of a number is an integer that divides it without leaving a remainder. For example, 3 is a divisor of 12 because 12 ÷ 3 = 4 (no remainder).
A multiple of a number is what you get when you multiply that number by an integer. For example, 12 is a multiple of 3 because 3 × 4 = 12.

Prime Numbers

Photo by Jan van der Wolf on Pexels

A prime number is a positive integer greater than 1 that has only two distinct positive divisors: 1 and itself.
Examples: 2, 3, 5, 7, 11, 13...
1 is not a prime number by definition because it only has one distinct divisor (itself).

Composite Numbers

Photo by Magda Ehlers on Pexels

A composite number is a positive integer greater than 1 that is not prime. This means it has more than two distinct positive divisors.
Examples: 4 (divisors: 1, 2, 4), 6 (divisors: 1, 2, 3, 6), 9 (divisors: 1, 3, 9).

Prime Factorization

Photo by Mai Đạo on Pexels

Every composite number can be expressed as a unique product of prime numbers. This is called its prime factorization. It's like finding the fundamental building blocks for that number.

For example, to find the prime factorization of 12:
1. Start with the smallest prime number, 2. Is 12 divisible by 2? Yes, 12 = 2 × 6.
2. Now look at 6. Is it divisible by 2? Yes, 6 = 2 × 3.
3. So, 12 = 2 × 2 × 3. Or, written with exponents: $2^2 \times 3^1$.

graph TD
    A["Start with N"] --> B{"Is N prime?"}
    B -- "Yes" --> C["N is a prime factor"]
    B -- "No" --> D["Find smallest prime factor 'p' of N"]
    D --> E["Add 'p' to list of prime factors"]
    E --> F["Set N = N / p"]
    F --> B

Highest Common Factor (HCF) / Greatest Common Divisor (GCD)

The HCF (or GCD) of two or more numbers is the largest positive integer that divides each of the numbers without a remainder.

To find the HCF using prime factorization:
1. Find the prime factorization of each number.
2. Identify all common prime factors.
3. For each common prime factor, take the lowest power it appears in any of the factorizations.
4. Multiply these lowest powers together.

Example: Find HCF of 12 and 18.
- Prime factorization of 12: $2^2 \times 3^1$
- Prime factorization of 18: $2^1 \times 3^2$
- Common prime factors are 2 and 3.
- Lowest power of 2 is $2^1$.
- Lowest power of 3 is $3^1$.
- HCF = $2^1 \times 3^1 = 2 \times 3 = 6$.

Lowest Common Multiple (LCM)

The LCM of two or more numbers is the smallest positive integer that is a multiple of all the numbers.

To find the LCM using prime factorization:
1. Find the prime factorization of each number.
2. Identify all prime factors that appear in any of the factorizations (common or not).
3. For each prime factor, take the highest power it appears in any of the factorizations.
4. Multiply these highest powers together.

Example: Find LCM of 12 and 18.
- Prime factorization of 12: $2^2 \times 3^1$
- Prime factorization of 18: $2^1 \times 3^2$
- All prime factors are 2 and 3.
- Highest power of 2 is $2^2$.
- Highest power of 3 is $3^2$.
- LCM = $2^2 \times 3^2 = 4 \times 9 = 36$.

There's also a handy relationship between HCF and LCM for two numbers, A and B:
$A \times B = \text{HCF}(A, B) \times \text{LCM}(A, B)$

For 12 and 18: $12 \times 18 = 216$.
$\text{HCF}(12, 18) \times \text{LCM}(12, 18) = 6 \times 36 = 216$. It checks out!

3. Worked Example

Let's find the HCF and LCM of 60 and 72.

Step 1: Prime Factorization

For 60:
- $60 \div 2 = 30$
- $30 \div 2 = 15$
- $15 \div 3 = 5$
- $5 \div 5 = 1$
So, $60 = 2 \times 2 \times 3 \times 5 = 2^2 \times 3^1 \times 5^1$.

For 72:
- $72 \div 2 = 36$
- $36 \div 2 = 18$
- $18 \div 2 = 9$
- $9 \div 3 = 3$
- $3 \div 3 = 1$
So, $72 = 2 \times 2 \times 2 \times 3 \times 3 = 2^3 \times 3^2$.

Step 2: Calculate HCF

1. Common prime factors: 2 and 3.
2. Lowest power of 2: $2^2$ (from 60's factorization).
3. Lowest power of 3: $3^1$ (from 60's factorization).
4. Multiply: HCF = $2^2 \times 3^1 = 4 \times 3 = 12$.

Step 3: Calculate LCM

1. All prime factors that appear: 2, 3, and 5.
2. Highest power of 2: $2^3$ (from 72's factorization).
3. Highest power of 3: $3^2$ (from 72's factorization).
4. Highest power of 5: $5^1$ (from 60's factorization).
5. Multiply: LCM = $2^3 \times 3^2 \times 5^1 = 8 \times 9 \times 5 = 72 \times 5 = 360$.

So, the HCF of 60 and 72 is 12, and their LCM is 360.

4. Key Takeaways

• Every whole number greater than 1 is either prime or can be written as a unique product of primes.
• Prime numbers are the fundamental building blocks of integers, having only two divisors: 1 and themselves.
• Prime factorization is the process of breaking down a number into its prime building blocks.
• The HCF is the largest number that divides into all given numbers without a remainder.
• The LCM is the smallest number that is a multiple of all given numbers.
• You can always check your HCF and LCM calculations for two numbers using the formula: $A \times B = \text{HCF}(A, B) \times \text{LCM}(A, B)$.

Common Mistakes to Avoid:
- Forgetting that 1 is neither prime nor composite.
- Mixing up "lowest power" for HCF and "highest power" for LCM during prime factorization steps.
- Not including all unique prime factors (even non-common ones) when calculating the LCM.
- Accidentally using composite factors in your prime factorization.

5. Now Try It

Find the HCF and LCM of 84 and 120. First, find their prime factorizations. Then, use those factorizations to determine the HCF and LCM. Finally, check your answers using the HCF × LCM = A × B relationship. You should get HCF = 12 and LCM = 840.