Welcome to the World of Numbers!
In this chapter, we are diving into Number Theory, which is essentially the "purest" part of mathematics. It is the study of the properties of integers (whole numbers). While it might seem abstract at first, it is the secret engine behind everything from internet security to how your credit card is encrypted.
Because this is part of the Further Pure with Technology section, we won't just be doing calculations by hand; we’ll be thinking about how we can use programming and technology to explore these patterns. Don't worry if you’re not a computer expert—we’ll break everything down step-by-step!
1. The Building Blocks: Prime Factorisation
Before we start the complex stuff, let’s look at the "atoms" of the number world: Prime Numbers.
The Fundamental Theorem of Arithmetic
This sounds fancy, but it just means that every whole number greater than 1 is either a prime itself or can be written as a unique product of prime numbers.
Example: 60 can be written as \( 2^2 \times 3 \times 5 \). There is no other way to write 60 using only primes!
Technology Connection: Prime Testing
In your exam, you might see short programs designed to check if a number is prime. A common limitation of simple programs is speed. If a program checks every number up to \( n \) to see if it's a factor, it will be very slow for large numbers.
Top Tip: To check if \( n \) is prime, a computer only needs to test factors up to \( \sqrt{n} \). This is much more efficient!
Quick Review:
• Primes: Numbers with exactly two factors (1 and themselves).
• Unique Factorisation: Every integer has one unique "prime fingerprint."
• Efficiency: Always test factors up to \( \sqrt{n} \).
2. Modular Arithmetic (Clock Math)
Modular arithmetic is often called "clock arithmetic." If it is 10:00 now, 4 hours later it isn't 14:00 on a standard clock; it is 2:00. This is Modulo 12.
The Notation
We write this as: \( a \equiv b \pmod n \).
This means \( a \) and \( b \) leave the same remainder when divided by \( n \).
Example: \( 17 \equiv 2 \pmod 5 \) because both 17 and 2 leave a remainder of 2 when divided by 5.
Rules for Success
1. Keep it small: You can always replace a large number with its remainder to make calculations easier.
2. Negative remainders: Sometimes it’s easier to go backward. In \( \pmod{10} \), \( 9 \) is the same as \( -1 \). This makes powers like \( 9^{50} \) much easier because \( (-1)^{50} = 1 \).
Common Mistake to Avoid:
Don't treat the \( \equiv \) sign exactly like an equals sign for division. You cannot always "divide" both sides in modular arithmetic unless the number you are dividing by is co-prime to the modulus (meaning they share no common factors other than 1).
Key Takeaway: Modular arithmetic focuses on remainders. It turns infinite number lines into finite loops!
3. The Power Shortcuts: Fermat and Euler
When numbers get huge, we need shortcuts. These two theorems are your best friends for solving high-power problems.
Fermat’s Little Theorem
If \( p \) is a prime number and \( a \) is any integer not divisible by \( p \), then:
\( a^{p-1} \equiv 1 \pmod p \)
Example: What is \( 3^{10} \pmod{11} \)? Since 11 is prime, the answer is immediately 1!
Euler’s Totient Function \( \phi(n) \)
What if the modulus isn't prime? We use Euler’s Totient Function. \( \phi(n) \) is the count of numbers less than \( n \) that are co-prime to \( n \).
• If \( p \) is prime, \( \phi(p) = p - 1 \).
• If you have a product of two primes \( n = p \times q \), then \( \phi(n) = (p-1)(q-1) \).
Euler’s Theorem: \( a^{\phi(n)} \equiv 1 \pmod n \), provided \( a \) and \( n \) are co-prime.
Wilson’s Theorem
This is a specific test for primes: A number \( p \) is prime if and only if:
\( (p-1)! \equiv -1 \pmod p \)
Analogy: This is like a "secret handshake" that only prime numbers know.
Quick Review Box:
• Fermat: Use when the modulus is prime.
• Euler: Use for composite (non-prime) numbers.
• Wilson: Connects factorials and primes.
4. Diophantine Equations
A Diophantine Equation is just an equation where we only care about integer solutions. In the "Technology" paper, you will often use programming loops to find these.
Pythagorean Triples
These are integers that satisfy \( x^2 + y^2 = z^2 \).
The most famous is \( (3, 4, 5) \). You might be asked to find triples that satisfy specific conditions, like \( x + y + z = 100 \), using a program.
Pell’s Equation
This is a specific type of equation that looks like this:
\( x^2 - ny^2 = 1 \)
Where \( n \) is a non-square integer. These equations always have the trivial solution \( (1, 0) \), but they can have infinitely many larger integer solutions. Finding these by hand is hard, but a computer can "brute force" the search by checking values of \( y \) and seeing if \( 1 + ny^2 \) is a perfect square.
Don't worry if this seems tricky! In your exam, you aren't expected to solve Pell's equation from scratch using advanced theory; you are expected to understand the logic of a program that finds the solutions for you.
5. Programming in Number Theory
Since this is a "With Technology" unit, you need to understand how to write and read simple algorithms.
Key Programming Concepts:
• For Loops: Used to test a range of numbers (e.g., checking all \( x \) from 1 to 1000).
• If Statements: Used to check a condition (e.g., if \( x^2 - ny^2 == 1 \)).
• The Modulo Operator (%): In programming, `x % n` gives you the remainder of \( x \) divided by \( n \). This is vital for prime testing and modular arithmetic.
Limitations of Technology
Computers are fast, but they have limits:
1. Overflow: If a number gets too big (like \( 100! \)), the computer might run out of memory or give an incorrect "overflow" error.
2. Time Complexity: A "Brute Force" search (checking every single number) might take years if the solution is very large. We need "refinements" (like the \( \sqrt{n} \) trick) to speed things up.
Key Takeaway: Technology is a tool to handle the "heavy lifting" of calculation, but you need the mathematical theory to tell the computer what to calculate efficiently.
Final Summary
• Number Theory is all about the patterns found in whole numbers.
• Modular Arithmetic lets us work with remainders to simplify huge problems.
• Theorems (Fermat, Euler, Wilson) provide powerful shortcuts for powers and primes.
• Diophantine Equations look for integer-only solutions, often using computer loops.
• Technology requires smart algorithms to avoid errors and save time.
Keep practicing! Number theory is like a puzzle—once you see the patterns, everything starts to click into place.