Introduction to Number Theory
Welcome to Number Theory! This chapter, part of your Additional Pure Mathematics module, is often called the "Queen of Mathematics." While you've been working with numbers your whole life, we are now going to look "under the hood" to see how they behave, how they divide, and how they interact in different systems. This is the foundation of modern computer security and cryptography!
Don't worry if some of the notation looks strange at first. Number theory is very logical, and once you get the hang of "clock arithmetic" and divisibility rules, it becomes one of the most satisfying parts of Further Maths.
1. Divisibility and the Division Algorithm
In Number Theory, we are mostly interested in integers (\(\mathbb{Z}\)). We say that \(a\) divides \(b\) (written as \(a | b\)) if \(b\) is a multiple of \(a\). For example, \(3 | 12\) is true, but \(5 | 12\) is not.
The Division Algorithm
This sounds fancy, but you’ve been doing it since primary school! It simply states that for any two positive integers \(a\) and \(b\), you can write:
\(a = bq + r\)
where:
- \(q\) is the quotient (how many times it fits).
- \(r\) is the remainder (what is left over).
- Importantly, \(0 \le r < b\). The remainder is always smaller than the number you divided by.
Quick Review: If \(a = 17\) and \(b = 5\), then \(17 = 5(3) + 2\). Here, \(q=3\) and \(r=2\).
Properties of Divisibility
A key result you need to know and apply is:
If \(a | b\) and \(a | c\), then \(a | (bx + cy)\) for any integers \(x\) and \(y\).
Analogy: If a ruler can measure 10cm and 20cm perfectly, it can also measure any combination of them (like \(2 \times 10 + 3 \times 20 = 80cm\)) perfectly.
2. Prime Numbers and Euclid's Lemma
Prime numbers are the building blocks of all integers. Every integer greater than 1 is either a prime or a composite number (made by multiplying primes).
Euclid’s Lemma
This is a vital tool for proofs. It states:
If \(a | rs\) and the highest common factor \(\text{hcf}(a, r) = 1\) (meaning they are coprime), then \(a | s\).
Example: If \(3 | (7 \times s)\), since 3 doesn't go into 7, it must go into \(s\).
Key Takeaway: If a number divides a product but shares no factors with the first part of the product, it must divide the second part.
3. Number Bases
We usually count in Base 10, but we can use any integer \(n \ge 2\) as a base. In Base \(n\), we use digits from \(0\) to \(n-1\).
If the base is higher than 10, we use letters:
A = 10, B = 11, C = 12, D = 13, E = 14, F = 15
Understanding the Notation
A number like \(2013_n\) means:
\(2n^3 + 0n^2 + 1n^1 + 3n^0\)
Example: Converting \(23_5\) to Base 10
\(2(5^1) + 3(5^0) = 10 + 3 = 13\).
Common Mistake: Forgetting that the "ones" column is always \(n^0\), which equals 1, regardless of the base!
4. Divisibility Tests
You are expected to know the "shortcuts" to see if a number is divisible by certain integers without doing long division.
- 2: Last digit is even.
- 3: Sum of digits is divisible by 3.
- 4: Last two digits form a number divisible by 4.
- 5: Last digit is 0 or 5.
- 8: Last three digits form a number divisible by 8.
- 9: Sum of digits is divisible by 9.
- 11: The alternating sum of digits (plus, minus, plus...) is divisible by 11.
Did you know? To test for a composite number like 6, you just test for its coprime factors (2 and 3). If it passes both, it's divisible by 6!
5. Modular Arithmetic (Finite Arithmetic)
Modular arithmetic is often called "Clock Arithmetic." We say \(a \equiv b \pmod{n}\) if \(a\) and \(b\) leave the same remainder when divided by \(n\).
Linear Congruences
A linear congruence looks like this: \(ax \equiv b \pmod{n}\).
To solve these, we try to find a value for \(x\) that makes the statement true. Unlike normal algebra, there might be no solutions, one solution, or many solutions!
Example: Solve \(3x \equiv 1 \pmod{5}\)
Try values for \(x\):
- \(x=1 \implies 3 \equiv 3 \pmod{5}\) (No)
- \(x=2 \implies 6 \equiv 1 \pmod{5}\) (Yes! Since \(6 \div 5 = 1\) remainder \(1\))
Simultaneous Congruences
Sometimes you have a system of two or three congruences. While the Chinese Remainder Theorem is a formal way to solve these, for this syllabus, you can often solve them by substitution or by listing possibilities for the largest modulus first.
6. Fermat’s Little Theorem (FLT)
This is a very powerful "power-reducer." It helps us calculate huge exponents easily. If \(p\) is a prime number:
- \(a^{p-1} \equiv 1 \pmod{p}\) (provided \(a\) is not a multiple of \(p\))
- \(a^p \equiv a \pmod{p}\) (always true for any \(a\))
Memory Aid: Think of the exponent \(p-1\) as a "reset button" that turns the number into 1.
Example: Find \(2^{100} \pmod{3}\)
Since 3 is prime, FLT says \(2^{3-1} \equiv 2^2 \equiv 1 \pmod{3}\).
Now, \(2^{100} = (2^2)^{50} = (1)^{50} = 1\).
So, \(2^{100} \equiv 1 \pmod{3}\). Magic!
7. The Order of \(a\) modulo \(p\)
The order of \(a\) modulo \(p\) is the smallest positive integer \(k\) such that:
\(a^k \equiv 1 \pmod{p}\)
Important Rule: The order \(k\) must be a factor of \(p-1\).
If you are looking for the order of a number modulo 7, you only need to check factors of 6 (i.e., 1, 2, 3, or 6).
Key Takeaway: Fermat's Little Theorem says \(a^{p-1} \equiv 1\), but there might be a smaller power that gets to 1 even sooner. That smallest power is the "order."
Quick Review Box
Notation: \(a | b\) means \(a\) divides \(b\).
Division: \(a = bq + r\).
FLT: \(a^{p-1} \equiv 1 \pmod{p}\) if \(p\) is prime.
Coprime: \(\text{hcf}(a,b) = 1\).
Bases: \(A=10, B=11, \dots, F=15\).