1 Module 1: Math Foundations
Module Objective: This module builds the core mathematical foundation required for competi-
tive programming and interviews. It covers prime numbers, GCD, modular arithmetic, and cyclic
problems like Josephus. Mastery of this module ensures efficiency in solving number-theory-heavy
problems.
Learning Outcomes:
• Understand and generate prime numbers efficiently
• Factorize integers using prime factorization
• Compute GCD/LCM using Euclidean Algorithm
• Apply modular arithmetic to cyclic and large-number problems
• Solve the Josephus problem with both recursion and iteration
• Implement all above concepts in Java for contests
1.1 Session 1: Prime Numbers & Prime Factorization
Duration: 1 Hr
Theory Notes:
• Definition: Prime numbers are numbers > 1 divisible only by 1 and itself.
• Fundamental Theorem of Arithmetic: Every integer > 1 can be uniquely expressed as
a product of prime numbers.
• Applications:
– Simplifying fractions
– LCM/GCD problems
– Cryptography (RSA encryption)
– Counting divisors
– Factorization-based combinatorics
• Methods to Generate or Check Primes:
√
1. Trial Division: Check divisibility up to n
2. Sieve of Eratosthenes: Efficient generation of all primes up to n
3. Segmented Sieve: Useful for large ranges in contests
4. Primality Tests: Fermat/Miller-Rabin (for very large numbers)
1
Example: Prime Factorization of 180
• 180 ÷ 2 = 90
• 90 ÷ 2 = 45
• 45 ÷ 3 = 15
• 15 ÷ 3 = 5
• 5÷5=1
• Prime factorization: 22 · 32 · 5
Java Implementation: Sieve of Eratosthenes
// Generate primes up to n using Sieve
public static boolean[] sieve(int n) {
boolean[] isPrime = new boolean[n+1];
[Link](isPrime, true);
isPrime[0] = isPrime[1] = false;
for(int i=2; i*i <= n; i++) {
if(isPrime[i]) {
for(int j=i*i; j <= n; j += i)
isPrime[j] = false;
}
}
return isPrime;
}
// Example usage:
boolean[] primes = sieve(100); // primes[2..100] true if prime
Competitive Programming Tricks:
• Precompute primes for multiple queries
• Use factorization for divisor-count problems
• Segment sieve for ranges like [1012 , 1012 + 106 ]
• Store prime factors in arrays for fast access
Practice Problems:
• LeetCode: [Link]
• LeetCode: [Link]
2
• GFG: [Link]
• CSES: [Link] (Prime factors)
• Codeforces: [Link]
1.2 Session 2: GCD (Euclidean Algorithm) & Number Theory
Duration: 1 Hr
Theory Notes:
• GCD Definition: Largest integer dividing two numbers
• LCM Definition: Smallest multiple divisible by both numbers
• Euclidean Algorithm:
(
a if b = 0
gcd(a, b) =
gcd(b, a mod b) otherwise
• Properties:
– gcd(a, 0) = a
– gcd(a, b) = gcd(b, a%b)
a∗b
– lcm(a, b) = gcd(a,b)
– If gcd(a, b) = 1, numbers are coprime
• Applications: Fraction simplification, modular inverses, cyclic sequences
Java Implementation: Recursive & Iterative
// Recursive GCD
public static int gcd(int a, int b) {
if(b == 0) return a;
return gcd(b, a % b);
}
// Iterative GCD
public static int gcdIter(int a, int b) {
while(b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
3
Competitive Programming Tricks:
• GCD of array: iterative application
• Coprime checks for combinatorial problems
• Use gcd to simplify modular fractions
Practice Problems:
• LeetCode: [Link]
• LeetCode: [Link]
• GFG: [Link]
• CSES: [Link]
• Codeforces: [Link]
1.3 Session 3: Modular Arithmetic & Josephus Problem
Duration: 1 Hr
Theory Notes:
• Modular Arithmetic Rules:
(a + b)%m = ((a%m) + (b%m))%m
(a ∗ b)%m = ((a%m) ∗ (b%m))%m
• Handles **large numbers** and **cyclic patterns**
• Applications: Modular inverses, cyclic counters, hashing
• Josephus Problem: People in a circle; every k-th eliminated
– Recurrence: J(n, k) = (J(n − 1, k) + k)%n
– Base: J(1, k) = 0
Java Implementation: Josephus Recursive and Iterative
// Recursive
public static int josephus(int n, int k) {
if(n == 1) return 0;
return (josephus(n-1, k) + k) % n;
}
4
// Iterative
public static int josephusIter(int n, int k) {
int res = 0;
for(int i=2; i<=n; i++)
res = (res + k) % i;
return res;
}
Competitive Programming Tricks:
• Transform recursive to iterative to avoid stack overflow
• Use modulo to handle large n values
• Precompute answers if k is fixed across multiple queries
Practice Problems:
• LeetCode: [Link]
• GFG: [Link]
• Codeforces: [Link]
• CSES: [Link]
1.4 Module 1 Summary and Competitive Notes
• Always precompute primes when multiple queries exist
• Euclidean GCD is fastest for large numbers
• Modular arithmetic avoids overflow and handles cyclic problems
• Josephus problem: recurrence + modulo; iterative solution preferred in contests
• Competitive programming tricks:
– Convert recursion to iteration for memory safety
– Use sieve to store primes up to 106 efficiently
– Use GCD for fraction simplification, LCM computations, and coprime checks