Introduction to Number Theory
Welcome to one of the most fascinating branches of mathematics! Number Theory is often called the "Queen of Mathematics." It deals with the properties of integers—the whole numbers we use every day. While it might seem abstract, Number Theory is the secret language behind modern technology. For example, every time you buy something online, Number Theory (specifically Modular Arithmetic) is working behind the scenes to encrypt your credit card details and keep them safe!
In this chapter, we will explore how numbers divide each other, how to find the "highest common factor" using a ancient yet powerful algorithm, and how to do "clock math" using congruences. Don't worry if it sounds complicated; we'll take it one step at a time.
1. The Division Theorem and Euclidean Algorithm
At its heart, the Division Theorem is just a formal way of saying what happens when you divide one number by another. If you have two integers \(a\) and \(b\), you can write it as:
\(a = bq + r\)
Where:
- \(q\) is the quotient (how many times it fits).
- \(r\) is the remainder (what's left over), and \(0 \le r < b\).
The Euclidean Algorithm
This is a clever "loop" used to find the Highest Common Factor (HCF) or Great Common Divisor (GCD) of two numbers. Instead of listing every factor, we use the remainders to shrink the numbers down until the HCF reveals itself.
Step-by-Step Process:
1. Divide the larger number by the smaller number and find the remainder.
2. Replace the larger number with the smaller one, and the smaller one with the remainder.
3. Repeat until the remainder is zero. The last non-zero remainder is your HCF!
Example: Find HCF(126, 45)
\(126 = 2 \times 45 + 36\)
\(45 = 1 \times 36 + 9\)
\(36 = 4 \times 9 + 0\)
The remainder is now zero, so the HCF is 9.
Key Takeaway: The Euclidean Algorithm is like a "number shredder"—it keeps breaking numbers down into smaller remainders until only the HCF remains.
2. Bezout's Identity
Bezout’s Identity states that the HCF of two numbers \(a\) and \(b\) can be written as a "linear combination" of those numbers. In simple terms, you can always find integers \(x\) and \(y\) such that:
\(ax + by = \text{HCF}(a, b)\)
To find \(x\) and \(y\), we use back substitution. We take the steps from the Euclidean Algorithm and work backwards from the HCF line.
Quick Review:
- Use Euclidean Algorithm to go forward to find the HCF.
- Use Bezout’s Identity to go backward to find the coefficients \(x\) and \(y\).
3. Modular Arithmetic and Congruences
Think of modular arithmetic as "Clock Math." On a 12-hour clock, if it is 10 o'clock and you wait 5 hours, it isn't 15 o'clock—it's 3 o'clock. We say \(15 \equiv 3 \pmod{12}\).
Key Term: We say \(a \equiv b \pmod n\) (read as "\(a\) is congruent to \(b\) modulo \(n\)") if \(a\) and \(b\) have the same remainder when divided by \(n\). This also means that \(a - b\) is exactly divisible by \(n\).
Properties of Congruences
Congruences are great because they behave a lot like normal equations. If \(a \equiv b \pmod n\), then:
1. Addition/Subtraction: \(a \pm k \equiv b \pm k \pmod n\)
2. Multiplication: \(ak \equiv bk \pmod n\)
3. Powers: \(a^k \equiv b^k \pmod n\)
Did you know? This power rule is a lifesaver! If you want to find the remainder of \(11^{100} \div 10\), just note that \(11 \equiv 1 \pmod{10}\). Therefore, \(11^{100} \equiv 1^{100} \equiv 1 \pmod{10}\). The answer is just 1!
Common Mistake: Be careful with division! You cannot simply "divide" both sides of a congruence unless the number you are dividing by is coprime to the modulus \(n\). Usually, it's safer to avoid division and use multiplicative inverses instead.
4. Fermat's Little Theorem
This is a very specific, powerful rule used to simplify huge powers when the modulus is a prime number \(p\).
If \(p\) is prime, then for any integer \(a\):
\(a^p \equiv a \pmod p\)
Or, if \(a\) is not divisible by \(p\):
\(a^{p-1} \equiv 1 \pmod p\)
Example: Find \(4^{20} \pmod 7\)
Since 7 is prime, Fermat's Little Theorem tells us \(4^{7-1} \equiv 4^6 \equiv 1 \pmod 7\).
We can break \(4^{20}\) down: \(4^{20} = (4^6)^3 \times 4^2\).
This becomes: \(1^3 \times 16 \pmod 7\).
Since \(16 \div 7\) leaves a remainder of 2, the answer is 2.
Key Takeaway: Use Fermat’s Little Theorem to "slash" large powers down to much smaller, manageable numbers.
5. Divisibility Tests
Sometimes you just need to know if a number is divisible by another at a glance. Here are the tests you need for your exam:
- Divisible by 2: Ends in 0, 2, 4, 6, 8 (even).
- Divisible by 3: Sum of the digits is divisible by 3.
- Divisible by 4: The last two digits are divisible by 4.
- Divisible by 5: Ends in 0 or 5.
- Divisible by 6: Divisible by both 2 AND 3.
- Divisible by 9: Sum of the digits is divisible by 9.
- Divisible by 10: Ends in 0.
- Divisible by 11: The alternating sum of digits (Add, Subtract, Add, Subtract...) is 0 or divisible by 11.
Example for 11: Is 1,331 divisible by 11?
\(1 - 3 + 3 - 1 = 0\). Yes, it is!
6. Solution of Congruence Equations
A congruence equation looks like \(ax \equiv b \pmod n\). Solving it is like finding \(x\) in algebra, but we are looking for integer values.
Multiplicative Inverses
To solve \(ax \equiv 1 \pmod n\), we need the multiplicative inverse of \(a\). This is an integer \(x\) that, when multiplied by \(a\), gives a remainder of 1. We can find this using the Euclidean Algorithm and Bezout's Identity.
Existence Rule: The equation \(ax \equiv b \pmod n\) has a solution if and only if the HCF of \(a\) and \(n\) divides \(b\).
- If HCF(\(a, n\)) = 1, there is exactly one solution (modulo \(n\)).
- If HCF(\(a, n\)) does not divide \(b\), there are no solutions.
7. Combinatorics: Counting, Permutations, and Combinations
Combinatorics is the math of counting possibilities.
Basic Principles
- Multiplicative Principle (AND): If there are \(m\) ways to do one thing and \(n\) ways to do another, there are \(m \times n\) ways to do both.
- Addition Principle (OR): If tasks are mutually exclusive, add the possibilities.
Permutations vs. Combinations
This is the most important distinction in counting:
1. Permutations (\(^nP_r\)): Order Matters.
Think of a race where you win Gold, Silver, or Bronze. The order you finish in changes the result.
\(^nP_r = \frac{n!}{(n-r)!}\)
2. Combinations (\(^nC_r\)): Order Does NOT Matter.
Think of choosing a team of 11 players from a squad of 21. It doesn't matter if you are picked first or fifth; you're just on the team!
\(^nC_r = \frac{n!}{r!(n-r)!}\)
Set Notation and Subsets
A set is a collection of items.
- Did you know? If a set has \(n\) elements, the number of possible subsets it has is \(2^n\). This includes the empty set and the set itself!
Key Takeaway: Before solving a counting problem, ask yourself: "Does the order matter?"
- Yes \(\rightarrow\) Permutations.
- No \(\rightarrow\) Combinations.
Don't worry if this seems tricky at first! Number Theory is all about patterns. Once you practice the Euclidean Algorithm a few times and get used to "Clock Math," you'll start seeing these patterns everywhere.