📋 Prerequisites

• Arithmetic & Order of Operations

Number theory starts with divisibility and primes — the atoms of the integer world. Know the divisibility rules, understand what makes a number prime, and master the Sieve of Eratosthenes. These are the foundation for everything else in number theory: GCD, LCM, modular arithmetic, and beyond.

📚 Key Concepts

Divisibility Definition

An integer $a$ is divisible by a nonzero integer $b$ if there exists an integer $k$ such that $a = b \cdot k$.

Notation: $ b \mid a $ (read "b divides a")

Examples: $ 3 \mid 12 $ because 12 = 3 \(\times\) 4. $ 5 \nmid 12 $ because 12 isn't a multiple of 5.

Properties:

• If $ a \mid b $ and $ b \mid c $, then $ a \mid c $ (transitivity)
• If $ a \mid b $ and $ a \mid c $, then $ a \mid (b + c) $ and $ a \mid (b - c) $
• If $ a \mid b $, then $ a \mid (b \cdot k) $ for any integer k
• Every integer is divisible by 1 and by itself

Divisibility Rules

• Divisible by 2: last digit is even (0, 2, 4, 6, 8)
• Divisible by 3: sum of digits is divisible by 3
• Divisible by 4: last two digits form a number divisible by 4
• Divisible by 5: last digit is 0 or 5
• Divisible by 6: divisible by both 2 and 3
• Divisible by 7: double the last digit, subtract from rest; repeat (less commonly used)
• Divisible by 8: last three digits form a number divisible by 8
• Divisible by 9: sum of digits is divisible by 9
• Divisible by 10: last digit is 0
• Divisible by 11: alternating sum of digits is divisible by 11 (including zero)

Why these work: \(Because 10 \\equiv 0 mod 2,5; 10 \\equiv 1 mod 3,9; 10 \\equiv -1 mod 11. We'll prove this properly with modular arithmetic later.\)

Prime & Composite Numbers

A positive integer greater than 1 is:

• Prime: if its only positive divisors are 1 and itself
• Composite: if it has a positive divisor other than 1 and itself

Important notes:

• 1 is neither prime nor composite (it's a unit)
• 2 is the only even prime number
• Primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ...
• There are infinitely many primes (Euclid's proof)

Sieve of Eratosthenes

An efficient algorithm to find all primes up to a given number n:

1. Write all numbers from 2 to n
2. Start with the smallest prime (2), mark all its multiples as composite
3. Move to the next unmarked number — it's prime. Mark all its multiples
4. Continue until you pass $\sqrt{n}$
5. All remaining unmarked numbers are prime

Optimization: you only need to check up to $\sqrt{n}$ because any composite n must have a factor \(\leq \sqrt{n}.\)

Prime Factorization

Every positive integer can be written uniquely as a product of primes (up to ordering).

This is the Fundamental Theorem of Arithmetic.

Example: $ 84 = 2^2 \times 3 \times 7 $

How to factor: divide by small primes repeatedly, or use factor trees.

Euclid's Lemma

If a prime $p$ divides the product $ab$, then $p$ divides $a$ or $p$ divides $b$ (or both).

This is why primes are "atomic" — they can't be split across factors. If a prime shows up in a product, it must come entirely from one factor or the other.

\(Important: this only works for primes! Composite numbers don't have this property (e.g., 6 divides 4 \\times 3 but 6 doesn't divide 4 or 3 individually).\)

Counting Divisors (Preview)

If $ n = p_1^{a_1} \cdot p_2^{a_2} \cdot ... \cdot p_k^{a_k} $, then the number of positive divisors is:

\[ d(n) = (a_1 + 1)(a_2 + 1)...(a_k + 1) \]

Because for each prime, you can choose exponent 0 through $a_i$ in the divisor. We'll cover this more in the GCD/LCM module.

✏️ Example Problems