Welcome to the World of Number Theory!
Welcome to one of the oldest and most beautiful branches of mathematics! Number Theory is often called "The Queen of Mathematics" because it studies the fundamental properties of integers (whole numbers). In this chapter, you’ll learn how to find the greatest common factor of huge numbers, solve "clock arithmetic" problems, and use secret tricks to see if a number is divisible by 11 without even using a calculator.
Don't worry if some of the names sound a bit fancy—at its heart, this chapter is all about playing with whole numbers and finding the patterns hidden inside them.
1. The Division Theorem and HCF
Before we dive into the deep end, let’s look at something you’ve known since primary school: division! The Division Theorem (also called the Division Algorithm) simply states that for any two integers \(a\) and \(b\), you can write them as:
\(a = bq + r\)
Where:
\(a\) is the number you are dividing (the dividend).
\(b\) is the number you are dividing by (the divisor).
\(q\) is the quotient (how many times it fits in fully).
\(r\) is the remainder (what is left over, where \(0 \le r < |b|\)).
The Euclidean Algorithm
The Euclidean Algorithm is a systematic way to find the Highest Common Factor (HCF)—also known as the Greatest Common Divisor (GCD)—of two numbers. This is much faster than listing all the factors, especially for big numbers!
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.
4. The last non-zero remainder is your HCF!
Quick Review: To find \(HCF(120, 45)\):
\(120 = 2 \times 45 + 30\)
\(45 = 1 \times 30 + 15\)
\(30 = 2 \times 15 + 0\)
The HCF is 15.
Key Takeaway: The Euclidean Algorithm turns a hard HCF problem into a series of simple division steps. Keep going until you hit zero!
2. Bezout's Identity
Bezout’s Identity sounds intimidating, but it’s just a way of expressing the HCF as a combination of your two original numbers. It says that if \(d\) is the \(HCF(a, b)\), then you can find integers \(x\) and \(y\) such that:
\(ax + by = d\)
To find \(x\) and \(y\), we use back-substitution. We take the steps we used in the Euclidean Algorithm and work from the bottom up.
Step-by-Step Example: Express \(15\) as a combination of \(120\) and \(45\).
From our previous Euclidean steps:
(1) \(30 = 120 - 2(45)\)
(2) \(15 = 45 - 1(30)\)
Substitute (1) into (2):
\(15 = 45 - 1(120 - 2(45))\)
\(15 = 45 - 120 + 2(45)\)
\(15 = 3(45) - 1(120)\)
So, \(x = -1\) and \(y = 3\).
Common Mistake: When substituting, don't actually multiply out the terms (like \(3 \times 45\)). Keep them as "groups" so you can collect them like algebra terms at the end!
3. Modular Arithmetic
Modular arithmetic is often called "Clock Arithmetic." On a 12-hour clock, if it is 10:00 and you wait 5 hours, it becomes 3:00, not 15:00. This is because we "reset" every 12 hours.
We write this as: \(a \equiv b \pmod n\)
This means "\(a\) is congruent to \(b\) modulo \(n\)."
Essentially, it means \(a\) and \(b\) leave the same remainder when divided by \(n\).
Properties of Congruences
Congruences behave a lot like equals signs. If \(a \equiv b \pmod n\) and \(c \equiv d \pmod n\), you can:
1. Add/Subtract: \(a \pm c \equiv b \pm d \pmod n\)
2. Multiply: \(ac \equiv bd \pmod n\)
3. Powers: \(a^k \equiv b^k \pmod n\)
Did you know? Modular arithmetic is the backbone of modern internet security! Your credit card details are encrypted using these very same principles.
Key Takeaway: If you have a huge power to calculate, like \(3^{10} \pmod 4\), simplify the base first! Since \(3 \equiv -1 \pmod 4\), then \(3^{10} \equiv (-1)^{10} \equiv 1 \pmod 4\). Easy!
4. Divisibility Tests
Ever wanted to know if a huge number is divisible by something without doing the long division? Here are the official tests you need to know for the syllabus:
Divisibility by...
2: The number ends in an even digit (0, 2, 4, 6, 8).
3: The sum of the digits is divisible by 3.
4: The last two digits form a number divisible by 4. (Example: 512 is divisible by 4 because 12 is).
5: The number ends in 0 or 5.
6: The number passes the test for both 2 and 3.
9: The sum of the digits is divisible by 9.
10: The number ends in 0.
11: Take the alternating sum of the digits (add one, subtract the next, add the next...). if the result is 0 or a multiple of 11, it’s divisible!
\(2 - 8 + 1 - 6 = -11\).
Since -11 is a multiple of 11, yes it is!
Memory Aid for 3 and 9: These are "sum buddies." For both, you just add up all the digits in the number.
Summary: Number Theory Checklist
- Can you perform the Euclidean Algorithm to find the HCF?
- Can you use back-substitution for Bezout's Identity?
- Do you understand that \(a \equiv b \pmod n\) means they have the same remainder?
- Can you apply divisibility tests to quickly check numbers?
Final Tip: Number Theory rewards patience. If a modular arithmetic problem looks impossible (like a huge power), look for a pattern. Numbers love to repeat themselves in cycles!