Day 10 - Number Theory: Logic, Concepts & Understanding

🎯What is Number Theory?

🧠 Core Concept:

Number theory is the branch of mathematics that studies the properties and relationships of integers. In programming interviews, it helps us solve problems involving:

Prime numbers - Building blocks of all integers
Divisibility - Understanding when one number divides another
Modular arithmetic - Working with remainders efficiently
Greatest Common Divisor (GCD) - Finding common factors

🤔 Why Learn This?

Number theory appears in:

Cryptography and security algorithms
Hash functions and data structures
Algorithm optimization techniques
Mathematical problem-solving in competitive programming

🔢Prime Numbers: The Building Blocks

📚 What is a Prime Number?

A prime number is a natural number greater than 1 that has exactly two factors: 1 and itself.

                    Examples: 2, 3, 5, 7, 11, 13, 17, 19, 23...

                    Not Prime: 1 (only one factor), 4 (factors: 1,2,4), 9 (factors: 1,3,9)

🧠 Logic Behind Prime Checking

💡 Naive Approach Logic:

To check if n is prime, test if any number from 2 to n-1 divides n.

Step 1: If n < 2, return False (by definition)

Step 2: For i from 2 to n-1, check if n % i == 0

Step 3: If any i divides n, return False

Step 4: If no divisor found, return True

Time Complexity: O(n) - We check every number
Problem: Very slow for large numbers!

⚡ Optimized Prime Checking Logic

💡 Key Insight:

If n has a factor greater than √n, it must also have a factor less than √n!

🤔 Why √n Works:

Consider n = a × b where a ≤ b

If both a > √n and b > √n, then a × b > √n × √n = n
This is impossible since a × b = n
Therefore, at least one factor must be ≤ √n

🎯 Example: Is 49 prime?

√49 = 7, so we only check divisors up to 7

49 ÷ 2 = 24.5 (not divisible)
49 ÷ 3 = 16.33... (not divisible)
49 ÷ 4 = 12.25 (not divisible)
49 ÷ 5 = 9.8 (not divisible)
49 ÷ 6 = 8.16... (not divisible)
49 ÷ 7 = 7 ✓ (divisible!)

Result: 49 is not prime (49 = 7 × 7)

Time Complexity: O(√n) - Much faster!

🏭 Sieve of Eratosthenes: Bulk Prime Generation

💡 The Big Idea:

Instead of checking each number individually, eliminate all composite numbers systematically.

Step 1: Create array [2, 3, 4, 5, 6, 7, 8, 9, 10, 11...]

Step 2: Start with first prime (2)

Step 3: Mark all multiples of 2 as composite (4, 6, 8, 10...)

Step 4: Move to next unmarked number (3)

Step 5: Mark all multiples of 3 as composite (9, 15, 21...)

Step 6: Repeat until √n

🎨 Visual Example: Sieve up to 30

Initial: [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 2:  [2, 3, ✗, 5, ✗, 7, ✗, 9, ✗, 11, ✗, 13, ✗, 15, ✗, 17, ✗, 19, ✗, 21, ✗, 23, ✗, 25, ✗, 27, ✗, 29, ✗]

After 3:  [2, 3, ✗, 5, ✗, 7, ✗, ✗, ✗, 11, ✗, 13, ✗, ✗, ✗, 17, ✗, 19, ✗, ✗, ✗, 23, ✗, 25, ✗, ✗, ✗, 29, ✗]

After 5:  [2, 3, ✗, 5, ✗, 7, ✗, ✗, ✗, 11, ✗, 13, ✗, ✗, ✗, 17, ✗, 19, ✗, ✗, ✗, 23, ✗, ✗, ✗, ✗, ✗, 29, ✗]

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

Time Complexity: O(n log log n)
Space Complexity: O(n)
Best For: Finding all primes up to a limit

🔗GCD & LCM: Finding Common Ground

📚 Definitions:

GCD (Greatest Common Divisor): Largest number that divides both a and b

LCM (Least Common Multiple): Smallest number that both a and b divide

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

🧠 Euclidean Algorithm Logic

💡 The Brilliant Insight:

GCD(a, b) = GCD(b, a mod b)

🤔 Why This Works:

If d divides both a and b, then:

a = d × k₁ for some integer k₁
b = d × k₂ for some integer k₂
a mod b = a - (a÷b) × b = d × k₁ - (a÷b) × d × k₂
So d also divides (a mod b)

This means any common divisor of (a,b) is also a common divisor of (b, a mod b)

🎯 Example: GCD(48, 18)

GCD(48, 18) → 48 mod 18 = 12

GCD(18, 12) → 18 mod 12 = 6

GCD(12, 6) → 12 mod 6 = 0

GCD(6, 0) → Answer: 6

Verification: 48 = 6×8, 18 = 6×3, so GCD is indeed 6!

Time Complexity: O(log min(a, b))
Why so fast: Each step reduces the problem size by at least half!

🔄Modular Arithmetic: The Art of Remainders

📚 What is Modular Arithmetic?

Working with remainders instead of actual numbers. It's like clock arithmetic!

                    Notation: a ≡ b (mod m) means "a and b have the same remainder when divided by m"

                    Example: 17 ≡ 5 (mod 12) because both 17 and 5 leave remainder 5 when divided by 12

⚡ Fast Modular Exponentiation

💡 The Problem:

Computing a^b mod m directly can overflow for large numbers!

🚨 Example Problem:

Calculate 2^1000 mod 1000000007

2^1000 has about 301 digits!
No standard data type can hold this
We need a smarter approach

💡 The Solution: Binary Exponentiation

Key insight: a^b = (a^(b/2))^2 when b is even

Step 1: If exponent is 0, return 1

Step 2: If exponent is odd, multiply result by base

Step 3: Square the base, halve the exponent

Step 4: Repeat until exponent becomes 0

Key: Take mod at each step to prevent overflow!

🎯 Example: 3^10 mod 7

Initial: base=3, exp=10, result=1, mod=7

Step 1: exp=10 (even), base²=(3²) mod 7 = 9 mod 7 = 2, exp=5
Step 2: exp=5 (odd), result=(1×2) mod 7 = 2, exp=4
Step 3: exp=4 (even), base²=(2²) mod 7 = 4, exp=2  
Step 4: exp=2 (even), base²=(4²) mod 7 = 16 mod 7 = 2, exp=1
Step 5: exp=1 (odd), result=(2×2) mod 7 = 4, exp=0

Final Answer: 4
                        

Verification: 3^10 = 59049, 59049 mod 7 = 4 ✓

Time Complexity: O(log b)
Space Complexity: O(1)
Magic: Reduces 1000 multiplications to just 10!

φEuler's Totient Function

📚 Definition:

φ(n) = count of integers from 1 to n that are coprime to n (GCD = 1)

                    Examples:

                    φ(6) = 2 (numbers 1, 5 are coprime to 6)

                    φ(9) = 6 (numbers 1, 2, 4, 5, 7, 8 are coprime to 9)

🧠 The Logic Behind the Formula

💡 Key Insight:

For a prime p: φ(p) = p - 1 (all numbers except multiples of p)

φ(n) = n × ∏(1 - 1/p) for all prime factors p of n

🤔 Why This Formula Works:

Start with all n numbers: {1, 2, 3, ..., n}
Remove multiples of first prime p₁: n - n/p₁ numbers left
Remove multiples of second prime p₂: multiply by (1 - 1/p₂)
Continue for all prime factors

🎯 Example: φ(12)

12 = 2² × 3, so prime factors are 2 and 3

φ(12) = 12 × (1 - 1/2) × (1 - 1/3)

= 12 × (1/2) × (2/3)

= 12 × 1/3 = 4

Verification: Numbers coprime to 12: {1, 5, 7, 11} → Count = 4 ✓

🔢Divisors and Perfect Numbers

📚 Understanding Divisors:

Divisors of n are all positive integers that divide n evenly.

Example: Divisors of 12 are {1, 2, 3, 4, 6, 12}

🧠 Smart Divisor Finding Logic

💡 Key Insight:

Divisors come in pairs! If d divides n, then n/d also divides n.

Step 1: Only check up to √n

Step 2: For each divisor i found, also add n/i

Step 3: Special case: if i² = n, only add i once

🎯 Example: Find divisors of 36

√36 = 6, so check 1, 2, 3, 4, 5, 6

1 divides 36 → add 1 and 36/1 = 36
2 divides 36 → add 2 and 36/2 = 18
3 divides 36 → add 3 and 36/3 = 12
4 divides 36 → add 4 and 36/4 = 9
6 divides 36 → add 6 and 36/6 = 6 (but 6 = 6, so add once)

Result: {1, 2, 3, 4, 6, 9, 12, 18, 36}

Time Complexity: O(√n)
Space Complexity: O(d(n)) where d(n) is number of divisors

✨ Perfect Numbers

📚 Definition:

A perfect number equals the sum of its proper divisors (excluding itself).

🎯 Example: 6 is perfect

Divisors of 6: {1, 2, 3, 6}
Proper divisors: {1, 2, 3}
Sum: 1 + 2 + 3 = 6 ✓

🎯 Example: 28 is perfect

Proper divisors: {1, 2, 4, 7, 14}
Sum: 1 + 2 + 4 + 7 + 14 = 28 ✓

🚀Real-World Applications & Interview Problems

🎯 Common Interview Patterns:

Problem Type	Key Concept	Example Problems
Prime Checking	Optimized √n algorithm	Count Primes, Prime Factorization
Bulk Prime Finding	Sieve of Eratosthenes	Find all primes in range
Common Factors	Euclidean Algorithm	Simplify fractions, array GCD
Large Exponents	Fast modular exponentiation	Power calculations, RSA crypto
Counting Problems	Euler's totient function	Coprime counting, cyclic groups

🧮 Day 10 - Number Theory

🎯What is Number Theory?

🧠 Core Concept:

🤔 Why Learn This?

🔢Prime Numbers: The Building Blocks

📚 What is a Prime Number?

🧠 Logic Behind Prime Checking

💡 Naive Approach Logic:

⚡ Optimized Prime Checking Logic

💡 Key Insight:

🤔 Why √n Works:

🎯 Example: Is 49 prime?

🏭 Sieve of Eratosthenes: Bulk Prime Generation

💡 The Big Idea:

🎨 Visual Example: Sieve up to 30

🔗GCD & LCM: Finding Common Ground

📚 Definitions:

🧠 Euclidean Algorithm Logic

💡 The Brilliant Insight:

🤔 Why This Works:

🎯 Example: GCD(48, 18)

🔄Modular Arithmetic: The Art of Remainders

📚 What is Modular Arithmetic?

⚡ Fast Modular Exponentiation

💡 The Problem:

🚨 Example Problem:

💡 The Solution: Binary Exponentiation

🎯 Example: 3^10 mod 7

φEuler's Totient Function

📚 Definition:

🧠 The Logic Behind the Formula

💡 Key Insight:

🤔 Why This Formula Works:

🎯 Example: φ(12)

🔢Divisors and Perfect Numbers

📚 Understanding Divisors:

🧠 Smart Divisor Finding Logic

💡 Key Insight:

🎯 Example: Find divisors of 36

✨ Perfect Numbers

📚 Definition:

🎯 Example: 6 is perfect

🎯 Example: 28 is perfect

🚀Real-World Applications & Interview Problems

🎯 Common Interview Patterns: