Number Theory

Introduction: Welcome to the World of Number Theory!

Welcome to Number Theory! While most of math focuses on functions, shapes, or data, Number Theory is like being a "math detective." We go back to the very basics to study integers (whole numbers) and how they interact.
You might think, "I've known how to divide since primary school," but here we look at the hidden patterns behind division, remainders, and prime numbers. These concepts aren't just for puzzles; they are the backbone of modern computer security and cryptography. Don't worry if it feels abstract at first—once you see the patterns, it’s like learning a secret code!

1. Number Bases (The Language of Numbers)

We usually count in Base 10 (the decimal system), likely because we have ten fingers. But numbers can be written in any base!

Understanding Base $n$

In Base $n$, each digit's value depends on its position, multiplied by a power of $n$.
The syllabus uses the notation $2013_n$. To find its value in our normal Base 10, we expand it like this:
$2013_n = (2 \times n^3) + (0 \times n^2) + (1 \times n^1) + (3 \times n^0)$

Working with Bases higher than 10

If a base is larger than 10 (like Base 16, or Hexadecimal), we run out of single digits. We use capital letters to represent numbers from 10 to 15:
A = 10, B = 11, C = 12, D = 13, E = 14, F = 15.
Example: $1A_n$ in Base 16 would be $(1 \times 16^1) + (10 \times 16^0) = 16 + 10 = 26.$

Quick Review: To convert a number from Base $n$ to Base 10, write out the powers of $n$ starting from the right (beginning with $n^0$) and multiply them by the digits.

2. Divisibility and the Division Algorithm

In Number Theory, we use a special symbol for divisibility: $a|b$.
This is read as "a divides b." It means that $b$ divided by $a$ results in a whole number with no remainder (e.g., $3|12$ is true, but $3|10$ is false).

The Division Algorithm

For any two positive integers $a$ and $b$, we can always write:
$a = bq + r$
Where:
- $q$ is the quotient (how many times it fits).
- $r$ is the remainder (the leftover bit).
Crucial Rule: The remainder $r$ must be smaller than the divisor $b$ ($0 \le r < b$).

Common Mistake: Forgetting that the remainder must be less than $b$. If you are dividing by 5, your remainder must be 0, 1, 2, 3, or 4. If you get a remainder of 6, you haven't finished dividing!

3. Divisibility Tests

You need to know how to quickly check if a number is divisible by certain integers without using a calculator.

Standard Tests:

2: The last digit is even.
3: The sum of the digits is divisible by 3.
4: The last two digits form a number divisible by 4.
5: The last digit is 0 or 5.
8: The last three digits form a number divisible by 8.
9: The sum of the digits is divisible by 9.
11: Take the alternating sum of the digits (add one, subtract the next...). If the result is 0 or divisible by 11, the whole number is. Example for 1331: $1 - 3 + 3 - 1 = 0$, so 11 divides 1331.

Composite and Prime Tests:

If a number is composite (like 6), you can test for it by checking its factors (e.g., a number is divisible by 6 if it passes the tests for both 2 and 3).
For other primes less than 50, you may need to develop an algorithmic test, which often involves manipulating the last digit and subtracting it from the rest of the number.

Key Takeaway: Divisibility isn't just about dividing; it's about the properties of the digits themselves!

4. Primes, HCF, and Coprimality

Prime numbers are the "atoms" of the number world. They only have two factors: 1 and themselves.

Highest Common Factor (HCF) and Coprimality

The HCF (also known as GCD) is the largest number that divides into two numbers.
If the hcf(a, b) = 1, we say that $a$ and $b$ are coprime (or relatively prime). This means they share no common factors other than 1.
Example: 8 and 9 are coprime because the factors of 8 are {1, 2, 4, 8} and factors of 9 are {1, 3, 9}. The only match is 1.

Important Properties:

Linear Combinations: If $a|b$ and $a|c$, then $a$ must also divide any "combination" of them: $a|(bx + cy)$ for any integers $x$ and $y$.
Analogy: If you have two stacks of \$5 bills, any amount you make by adding or removing bills from those stacks will still be a multiple of \$5.
Euclid’s Lemma: If $a|rs$ and hcf(a, r) = 1, then $a|s$.
Basically, if $a$ divides a product but has nothing in common with the first part of the product, it must be dividing the second part.

5. Finite (Modular) Arithmetic

This is often called "Clock Arithmetic." In modulo $n$, we only care about the remainder when a number is divided by $n$.

The Notation

$a \equiv b \pmod n$
This means "$a$ is congruent to $b$ modulo $n$." It basically tells us that $a$ and $b$ leave the same remainder when divided by $n$.
Example: $17 \equiv 2 \pmod 5$. Both 17 and 2 leave a remainder of 2 when divided by 5.

Solving Linear Congruences

You will be asked to solve equations like: $ax \equiv b \pmod n$.
To solve these, you are looking for an integer $x$ that makes the statement true.
Step-by-step approach:
1. Check if a solution exists: A solution exists if hcf(a, n) divides $b$.
2. Simplify the congruence if possible.
3. Test values or use properties of modular arithmetic to isolate $x$.

Did you know? Modular arithmetic is how your computer keeps your credit card info safe! Encryption uses huge prime numbers and modular arithmetic to scramble data so only the person with the "key" can solve the congruence and read the message.

Summary Checklist

Can you convert numbers between Base $n$ and Base 10?
Do you remember the letters A-F for Base 16?
Can you state the Division Algorithm $a = bq + r$?
Do you know the divisibility tests for 3, 4, 9, and 11?
Do you understand that coprime means the HCF is 1?
Can you apply Euclid's Lemma to divisibility problems?
Can you solve a basic linear congruence like $3x \equiv 1 \pmod 5$?

Don't worry if this seems tricky at first! Number Theory is a different way of thinking. Keep practicing the "Clock Arithmetic" and the divisibility rules, and the patterns will start to click!

* The content provided by thinka is generated by AI and may not always be accurate or up-to-date. Please use it as a supplementary resource and verify with official materials.