Number Theory Basics

What is Number Theory?

Number theory: Study of properties of integers

Focus: Whole numbers (0, 1, 2, 3, ...)

Topics:

• Prime numbers
• Divisibility
• Greatest common divisor
• Modular arithmetic
• Number patterns

Applications: Cryptography, computer science, coding theory

Divisibility

a divides b (a | b): b = ka for some integer k

Read: "a divides b" or "b is divisible by a"

Example: 3 | 12 because 12 = 3 × 4

Divisibility Rules

Divisible by 2: Last digit is even (0, 2, 4, 6, 8)

Divisible by 3: Sum of digits divisible by 3

Divisible by 4: Last two digits divisible by 4

Divisible by 5: Last digit is 0 or 5

Divisible by 6: Divisible by both 2 and 3

Divisible by 9: Sum of digits divisible by 9

Divisible by 10: Last digit is 0

Example: Check Divisibility

378:

• By 2? Yes (last digit 8 is even)
• By 3? Yes (3+7+8 = 18, divisible by 3)
• By 6? Yes (divisible by both 2 and 3)
• By 9? Yes (18 is divisible by 9)

125:

• By 5? Yes (ends in 5)
• By 10? No (doesn't end in 0)

Prime Numbers

Prime number: Natural number > 1 with exactly two divisors (1 and itself)

First primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31...

Composite number: Natural number > 1 that is NOT prime

Special case: 1 is neither prime nor composite

Example: Identify Primes

7: Divisors are 1 and 7 only → Prime

9: Divisors are 1, 3, 9 → Composite (3 × 3)

2: Only even prime number

15: Divisors are 1, 3, 5, 15 → Composite (3 × 5)

Prime Factorization

Fundamental Theorem of Arithmetic: Every integer > 1 has unique prime factorization

Prime factorization: Write number as product of primes

Example 1: Find Prime Factorization

60 = ?

Factor tree:

60 = 2 × 30
   = 2 × 2 × 15
   = 2 × 2 × 3 × 5
   = 2² × 3 × 5

Prime factorization: 2² × 3 × 5

Example 2: Large Number

84:

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

Sieve of Eratosthenes

Method to find all primes up to n

Process:

1. List numbers from 2 to n
2. Start with 2 (first prime)
3. Cross out all multiples of 2 (except 2)
4. Move to next unmarked number
5. Cross out its multiples
6. Repeat until done

Example: Find Primes up to 30

Start: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30

After crossing multiples of 2, 3, 5:

Primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

Greatest Common Divisor (GCD)

GCD(a, b): Largest positive integer that divides both a and b

Notation: GCD(a, b) or (a, b)

Also called: Greatest common factor (GCF)

Example 1: Find GCD by Listing

GCD(12, 18) = ?

Divisors of 12: 1, 2, 3, 4, 6, 12 Divisors of 18: 1, 2, 3, 6, 9, 18

Common divisors: 1, 2, 3, 6

Greatest: 6

GCD(12, 18) = 6

Example 2: Using Prime Factorization

GCD(60, 90) = ?

Prime factorizations:

• 60 = 2² × 3 × 5
• 90 = 2 × 3² × 5

Take lowest power of each common prime:

• 2¹ (lower of 2² and 2¹)
• 3¹ (lower of 3¹ and 3²)
• 5¹ (both have 5¹)

GCD = 2 × 3 × 5 = 30

Euclidean Algorithm

Efficient method to find GCD

Process: GCD(a, b) = GCD(b, a mod b) Repeat until remainder is 0

Example: Euclidean Algorithm

GCD(48, 18) = ?

Step 1: 48 = 18 × 2 + 12 → GCD(48, 18) = GCD(18, 12)

Step 2: 18 = 12 × 1 + 6 → GCD(18, 12) = GCD(12, 6)

Step 3: 12 = 6 × 2 + 0 → GCD(12, 6) = 6

Answer: GCD(48, 18) = 6

Least Common Multiple (LCM)

LCM(a, b): Smallest positive integer divisible by both a and b

Example 1: Find LCM by Listing

LCM(4, 6) = ?

Multiples of 4: 4, 8, 12, 16, 20, 24... Multiples of 6: 6, 12, 18, 24, 30...

Common multiples: 12, 24, 36...

Least: 12

LCM(4, 6) = 12

Example 2: Using Prime Factorization

LCM(12, 18) = ?

Prime factorizations:

• 12 = 2² × 3
• 18 = 2 × 3²

Take highest power of each prime:

• 2² (higher of 2² and 2¹)
• 3² (higher of 3¹ and 3²)

LCM = 2² × 3² = 4 × 9 = 36

Relationship Between GCD and LCM

Important formula:

GCD(a, b) × LCM(a, b) = a × b

Example: Use Formula

GCD(12, 18) = 6 Find LCM(12, 18):

LCM = (12 × 18) / GCD
LCM = 216 / 6
LCM = 36

Relatively Prime (Coprime)

Two numbers are relatively prime if GCD = 1

Share no common factors except 1

Example: Relatively Prime

GCD(15, 28) = 1 → Relatively prime

GCD(12, 18) = 6 → NOT relatively prime

GCD(7, 9) = 1 → Relatively prime

Modular Arithmetic

a mod n: Remainder when a is divided by n

Read: "a modulo n" or "a mod n"

Clock arithmetic: 15:00 is same as 3:00 (mod 12)

Example 1: Calculate mod

17 mod 5 = ?

17 ÷ 5 = 3 remainder 2

17 mod 5 = 2

Example 2: Negative Numbers

-7 mod 3 = ?

-7 = -3 × 3 + 2

-7 mod 3 = 2 (always return non-negative remainder)

Modular Arithmetic Properties

Addition: (a + b) mod n = [(a mod n) + (b mod n)] mod n

Multiplication: (a × b) mod n = [(a mod n) × (b mod n)] mod n

Example: Modular Arithmetic

(23 + 17) mod 5 = ?

Method 1: 40 mod 5 = 0

Method 2:

23 mod 5 = 3
17 mod 5 = 2
(3 + 2) mod 5 = 5 mod 5 = 0

Both give 0

Congruence

a ≡ b (mod n): a and b have same remainder when divided by n

Read: "a is congruent to b modulo n"

Equivalent: n divides (a - b)

Example: Congruence

17 ≡ 5 (mod 6) because:

• 17 mod 6 = 5
• 5 mod 6 = 5
• Same remainder

25 ≡ 4 (mod 7) because:

• 25 mod 7 = 4
• 4 mod 7 = 4

Applications: Day of Week

Find day of week using modular arithmetic

Example: Days Calculation

Today is Monday (day 0)

What day is it in 100 days?

100 mod 7 = ?

100 = 7 × 14 + 2

100 mod 7 = 2

2 days after Monday = Wednesday

Applications: Cryptography

RSA encryption uses:

• Prime numbers
• Modular arithmetic
• Number theory theorems

Key generation relies on:

• Finding large primes
• Computing GCD
• Modular exponentiation

Fermat's Little Theorem

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

a^(p-1) ≡ 1 (mod p)

Used in: Primality testing, cryptography

Example: Fermat's Little Theorem

p = 7, a = 2

Check: 2⁶ mod 7 = ?

2⁶ = 64 64 = 7 × 9 + 1

2⁶ ≡ 1 (mod 7) ✓

Perfect Numbers

Perfect number: Equals sum of its proper divisors

Proper divisors: All divisors except the number itself

Example: Perfect Number

6:

• Divisors: 1, 2, 3
• Sum: 1 + 2 + 3 = 6
• Perfect! ✓

28:

• Divisors: 1, 2, 4, 7, 14
• Sum: 1 + 2 + 4 + 7 + 14 = 28
• Perfect! ✓

Next perfect numbers: 496, 8128...

Practice