Number Theory Fundamentals

TL;DR

Number theory is all about the properties and relationships of whole numbers, especially integers. You'll learn about divisibility, prime numbers, and how numbers behave when you divide them. Mastering these basics will be super useful for solving many Math Olympiad problems.

1. The Mental Model

Think of number theory as taking numbers apart and seeing how their pieces fit together. It's like looking under the hood of a car to understand how the engine works, rather than just driving it.

2. The Core Material

Number theory focuses on integers: ..., -3, -2, -1, 0, 1, 2, 3, ...

Divisibility

A number 'a' is divisible by a number 'b' (where b is not zero) if you can divide 'a' by 'b' and get an integer with no remainder. We write this as b | a. If it's not divisible, we write b <binary data, 1 bytes> a.

For example:
* 3 | 12 because 12 / 3 = 4 (an integer).
* 5 <binary data, 1 bytes> 12 because 12 / 5 = 2.4 (not an integer).

Key properties of divisibility:
* If a | b and b | c, then a | c (transitivity).
* If a | b and a | c, then a | (bx + cy) for any integers x, y. This is really powerful!

Prime Numbers and Composite Numbers

Photo by Jan van der Wolf on Pexels

A prime number is a natural number greater than 1 that has exactly two distinct positive divisors: 1 and itself.
Examples: 2, 3, 5, 7, 11, 13, ...

A composite number is a natural number greater than 1 that is not prime. It has more than two positive divisors.
Examples: 4, 6, 8, 9, 10, 12, ... (1 is neither prime nor composite).

The number 1 is unique; it's neither prime nor composite.

Fundamental Theorem of Arithmetic (Unique Prime Factorization)

Photo by Vitaly Gariev on Pexels

This is a cornerstone! It states that every integer greater than 1 can be uniquely expressed as a product of prime numbers, up to the order of the factors.

Example:
* 12 = 2 * 2 * 3 = 2^2 * 3
* 30 = 2 * 3 * 5
* 100 = 2 * 2 * 5 * 5 = 2^2 * 5^2

Knowing the prime factorization of numbers helps you find common divisors, multiples, and simplify fractions, among other things.

Greatest Common Divisor (GCD) and Least Common Multiple (LCM)

Photo by rahul winson on Pexels

The GCD of two non-zero integers a and b is the largest positive integer that divides both a and b. We write it as gcd(a, b).
The LCM of two non-zero integers a and b is the smallest positive integer that is a multiple of both a and b. We write it as lcm(a, b).

You can find GCD and LCM using prime factorization:
1. Find the prime factorization of each number.
2. For GCD, take the lowest power of each common prime factor.
3. For LCM, take the highest power of each prime factor (common or not).

Example: a = 12 = 2^2 * 3 and b = 18 = 2 * 3^2
* gcd(12, 18): common primes are 2 and 3. Lowest power of 2 is 2^1, lowest power of 3 is 3^1. So, gcd(12, 18) = 2 * 3 = 6.
* lcm(12, 18): all primes involved are 2 and 3. Highest power of 2 is 2^2, highest power of 3 is 3^2. So, lcm(12, 18) = 2^2 * 3^2 = 4 * 9 = 36.

A useful relationship: For any positive integers a and b, a * b = gcd(a, b) * lcm(a, b).

graph TD
    A["Start with an integer N > 1"] --> B{"Is N prime?"}
    B -- Yes --> C["N is a Prime Number"]
    B -- No --> D["N is a Composite Number"]
    D --> E["Find prime factors of N"]
    E --> F["Express N as product of primes"]
    F --> G["Unique Prime Factorization (e.g., 12 = 2^2 * 3)"]
    G --> H["Apply to GCD/LCM calculations"]
    G --> I["Analyze divisibility"]

Modular Arithmetic (Congruence)

Photo by Yan Krukau on Pexels

Modular arithmetic is about remainders when you divide. If a and b have the same remainder when divided by n, we say a is congruent to b modulo n. We write a ≡ b (mod n).

Example:
* 17 ≡ 5 (mod 12) because 17 / 12 = 1 remainder 5, and 5 / 12 = 0 remainder 5.
* 25 ≡ 1 (mod 4) because 25 / 4 = 6 remainder 1.

Properties:
* If a ≡ b (mod n) and c ≡ d (mod n), then:
* a + c ≡ b + d (mod n)
* a - c ≡ b - d (mod n)
* a * c ≡ b * d (mod n)
* This lets you do arithmetic with remainders, which is extremely useful for problems involving cycles or large numbers.

3. Worked Example

Problem: Find the remainder when 7^100 is divided by 5.

Solution:
We need to find 7^100 (mod 5).
First, let's look at the base 7 (mod 5):
7 ≡ 2 (mod 5)

Now, we can substitute this into the expression:
7^100 ≡ 2^100 (mod 5)

Let's look at powers of 2 (mod 5):
2^1 ≡ 2 (mod 5)
2^2 = 4 ≡ 4 (mod 5)
2^3 = 8 ≡ 3 (mod 5)
2^4 = 16 ≡ 1 (mod 5)

Notice that 2^4 ≡ 1 (mod 5). This is a cycle of length 4.
We can use this to simplify 2^100.
Since 100 is a multiple of 4 (100 = 4 * 25), we can write:
2^100 = (2^4)^25

So, (2^4)^25 ≡ 1^25 (mod 5)
1^25 = 1

Therefore, 7^100 ≡ 1 (mod 5).

The remainder when 7^100 is divided by 5 is 1.

4. Key Takeaways

• Integers are the stars of number theory; understand their fundamental properties.
• Every number greater than 1 has a unique prime fingerprint (its prime factorization).
• Use prime factorization to efficiently find GCDs and LCMs.
• Modular arithmetic simplifies calculations by focusing on remainders.
• Look for cycles in modular arithmetic to handle large exponents.

Common mistakes to avoid:
- Don't confuse prime numbers with odd numbers (2 is prime, but not odd).
- Forgetting that 1 is neither prime nor composite.
- Incorrectly applying divisibility rules or properties.
- Not reducing numbers to their smallest non-negative remainder in modular arithmetic.

5. Now Try It

Find the last digit of 3^2023. (Hint: The last digit is the number modulo 10. Look for a pattern in the powers of 3 modulo 10.)
What success looks like: You'll arrive at a single digit (0-9) as your answer, showing the steps involved using modular arithmetic.