Whizmath Number Theory Masterclass: The Queen of Mathematics

Welcome to Whizmath's Comprehensive Number Theory Lesson! Number theory is the branch of mathematics devoted to the study of integers and their properties. Often called the "Queen of Mathematics," it combines beautiful theoretical concepts with powerful practical applications in cryptography and computer science.

From prime numbers to modular arithmetic, this guide will take you through the fascinating world of integers and their patterns.

Lesson Objectives

By the end of this lesson, you will:

Section 1: Prime Numbers and Divisibility

1.1 Prime Numbers

A prime number is a natural number greater than 1 with no positive divisors other than 1 and itself.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Fundamental Theorem of Arithmetic

Every integer greater than 1 can be represented uniquely as a product of prime powers.

n = p₁a₁ × p₂a₂ × ... × pₖaₖ

Example

Factorize 84 into its prime factors:

84 = 2 × 42 = 2 × 2 × 21 = 2 × 2 × 3 × 7 = 2² × 3¹ × 7¹

1.2 Divisibility and GCD/LCM

Divisibility: We say a|b (a divides b) if b = ka for some integer k.

Greatest Common Divisor (GCD)

The largest integer that divides two numbers. For 24 and 36:

GCD(24,36) = 12

Least Common Multiple (LCM)

The smallest positive integer divisible by both numbers. For 6 and 8:

LCM(6,8) = 24

Euclidean Algorithm

An efficient method for finding GCD:

  1. Divide larger number by smaller number
  2. Replace larger number with smaller number and smaller number with remainder
  3. Repeat until remainder is 0
  4. GCD is the last non-zero remainder

Section 2: Modular Arithmetic

2.1 Congruence and Basic Properties

We say a ≡ b (mod m) if m divides (a - b).

Addition
If a ≡ b (mod m) and c ≡ d (mod m), then a + c ≡ b + d (mod m)
Multiplication
If a ≡ b (mod m) and c ≡ d (mod m), then a × c ≡ b × d (mod m)
Exponentiation
If a ≡ b (mod m), then aⁿ ≡ bⁿ (mod m) for any positive integer n
Example

Calculate 17 × 23 mod 5:

17 ≡ 2 mod 5 and 23 ≡ 3 mod 5

17 × 23 ≡ 2 × 3 ≡ 6 ≡ 1 mod 5

2.2 Fermat's Little Theorem and Euler's Theorem

Fermat's Little Theorem

If p is prime and a is not divisible by p:

ap-1 ≡ 1 (mod p)

Euler's Theorem

For coprime a and n:

aφ(n) ≡ 1 (mod n)

where φ(n) is Euler's totient function (count of numbers ≤ n coprime to n)

Section 3: Advanced Concepts and Applications

3.1 Diophantine Equations

Polynomial equations where we seek integer solutions.

Linear Diophantine Equations

Equations of form ax + by = c have solutions iff GCD(a,b) divides c.

General solution if (x₀,y₀) is one solution:

x = x₀ + (b/d)t, y = y₀ - (a/d)t where d = GCD(a,b)

Example

Find all integer solutions to 6x + 9y = 21:

GCD(6,9)=3 divides 21, so solutions exist.

Particular solution: x=2, y=1

General solution: x=2+3t, y=1-2t for any integer t

3.2 Cryptographic Applications

RSA Cryptosystem
  1. Choose two large primes p and q
  2. Compute n = p × q and φ(n) = (p-1)(q-1)
  3. Choose e coprime to φ(n)
  4. Find d such that e × d ≡ 1 mod φ(n)
  5. Public key: (n,e), Private key: (n,d)
  6. Encryption: c ≡ me mod n
  7. Decryption: m ≡ cd mod n

Section 4: Practice Problems

Beginner Level

1. Find the prime factorization of 120
2. Calculate GCD(48, 60) using the Euclidean algorithm

Intermediate Level

3. Solve the congruence 3x ≡ 4 mod 7
4. Find all integer solutions to 5x + 7y = 1

Advanced Level

5. Using Fermat's Little Theorem, compute 316 mod 17
6. In RSA, if p=5, q=11, and e=3, find d and encrypt m=8

Conclusion

Number theory reveals the hidden patterns and structures within the integers, with applications ranging from pure mathematics to modern cryptography. By mastering these concepts, you'll develop a deeper appreciation for the beauty and utility of numbers.

Continue your number theory journey with Whizmath! 👑

Interactive Quizzes