Chapter 14: Mathematical Algorithms (GCD, LCM, Prime Numbers)
Introduction
Mathematical algorithms form the foundation of cryptography, number theory, and computational mathematics. Understanding how to efficiently compute GCD, LCM, prime numbers, factorization, and modular arithmetic is essential for security systems, optimization problems, and competitive programming.
Why This Matters
Mathematical algorithms power critical systems:
- Cryptography: RSA encryption uses prime numbers and modular arithmetic
- Computer graphics: Rational number operations require GCD
- Scheduling: LCM determines periodic events
- Hash functions: Modular arithmetic for distribution
- Competitive programming: Number theory problems
- Random number generation: Prime-based algorithms
- Error detection: Checksums using modular arithmetic
How to Study This Chapter
- Understand mathematical concepts - Number theory fundamentals
- Analyze algorithm efficiency - Iterative vs recursive approaches
- Implement optimizations - Sieve of Eratosthenes, binary GCD
- Test edge cases - Zero, one, negative numbers
- Apply to real problems - Cryptography, scheduling
Greatest Common Divisor (GCD)
GCD of two numbers is the largest positive integer that divides both numbers without remainder.
Euclidean Algorithm
Based on the principle: gcd(a, b) = gcd(b, a mod b)
Visualization
gcd(48, 18):
48 = 18 × 2 + 12 → gcd(48, 18) = gcd(18, 12)
18 = 12 × 1 + 6 → gcd(18, 12) = gcd(12, 6)
12 = 6 × 2 + 0 → gcd(12, 6) = 6
Result: gcd(48, 18) = 6
C Implementation
#include <stdio.h>
// Recursive Euclidean algorithm
int gcdRecursive(int a, int b) {
if (b == 0) {
return a;
}
return gcdRecursive(b, a % b);
}
// Iterative Euclidean algorithm
int gcdIterative(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
// Extended Euclidean algorithm (finds x, y such that ax + by = gcd(a, b))
int extendedGCD(int a, int b, int* x, int* y) {
if (b == 0) {
*x = 1;
*y = 0;
return a;
}
int x1, y1;
int gcd = extendedGCD(b, a % b, &x1, &y1);
*x = y1;
*y = x1 - (a / b) * y1;
return gcd;
}
int main() {
int a = 48, b = 18;
printf("GCD(%d, %d) = %d (recursive)\n", a, b, gcdRecursive(a, b));
printf("GCD(%d, %d) = %d (iterative)\n", a, b, gcdIterative(a, b));
int x, y;
int gcd = extendedGCD(a, b, &x, &y);
printf("Extended GCD: %d = %d * %d + %d * %d\n", gcd, a, x, b, y);
return 0;
}
C++ Implementation
#include <iostream>
#include <numeric> // For std::gcd (C++17)
using namespace std;
// Recursive GCD
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
// Binary GCD (Stein's algorithm) - faster for large numbers
int binaryGCD(int a, int b) {
if (a == 0) return b;
if (b == 0) return a;
// Count common factors of 2
int shift = 0;
while ((a | b) & 1) == 0) {
a >>= 1;
b >>= 1;
shift++;
}
// Remove remaining factors of 2 from a
while ((a & 1) == 0) {
a >>= 1;
}
do {
// Remove factors of 2 from b
while ((b & 1) == 0) {
b >>= 1;
}
// Ensure a <= b
if (a > b) {
swap(a, b);
}
b -= a;
} while (b != 0);
return a << shift;
}
// GCD of array
int gcdArray(int arr[], int n) {
int result = arr[0];
for (int i = 1; i < n; i++) {
result = gcd(result, arr[i]);
if (result == 1) {
return 1;
}
}
return result;
}
int main() {
int a = 48, b = 18;
cout << "GCD(" << a << ", " << b << ") = " << gcd(a, b) << endl;
cout << "Binary GCD(" << a << ", " << b << ") = " << binaryGCD(a, b) << endl;
// C++17 standard library
cout << "std::gcd(" << a << ", " << b << ") = " << std::gcd(a, b) << endl;
int arr[] = {12, 18, 24, 30};
cout << "GCD of array: " << gcdArray(arr, 4) << endl;
return 0;
}
Java Implementation
public class GCDAlgorithms {
// Recursive GCD
public static int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
// Iterative GCD
public static int gcdIterative(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
// GCD of array
public static int gcdArray(int[] arr) {
int result = arr[0];
for (int i = 1; i < arr.length; i++) {
result = gcd(result, arr[i]);
if (result == 1) {
return 1;
}
}
return result;
}
public static void main(String[] args) {
int a = 48, b = 18;
System.out.println("GCD(" + a + ", " + b + ") = " + gcd(a, b));
System.out.println("GCD(" + a + ", " + b + ") = " + gcdIterative(a, b));
int[] arr = {12, 18, 24, 30};
System.out.println("GCD of array: " + gcdArray(arr));
}
}
Complexity Analysis
- Time Complexity: O(log min(a, b))
- Space Complexity: O(1) iterative, O(log min(a, b)) recursive
- Binary GCD: Faster for very large numbers (uses bit operations)
Least Common Multiple (LCM)
LCM of two numbers is the smallest positive integer divisible by both numbers.
Formula
LCM(a, b) = (a × b) / GCD(a, b)
Implementation
#include <stdio.h>
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
int lcm(int a, int b) {
return (a / gcd(a, b)) * b; // Divide first to avoid overflow
}
// LCM of array
int lcmArray(int arr[], int n) {
int result = arr[0];
for (int i = 1; i < n; i++) {
result = lcm(result, arr[i]);
}
return result;
}
int main() {
int a = 12, b = 18;
printf("LCM(%d, %d) = %d\n", a, b, lcm(a, b));
int arr[] = {4, 6, 8};
printf("LCM of array: %d\n", lcmArray(arr, 3));
return 0;
}
Prime Numbers
A prime number is a natural number greater than 1 divisible only by 1 and itself.
Primality Testing
Trial Division
#include <stdio.h>
#include <stdbool.h>
#include <math.h>
// Basic primality test
bool isPrime(int n) {
if (n <= 1) return false;
if (n <= 3) return true;
if (n % 2 == 0 || n % 3 == 0) return false;
// Check divisors up to √n
for (int i = 5; i * i <= n; i += 6) {
if (n % i == 0 || n % (i + 2) == 0) {
return false;
}
}
return true;
}
int main() {
int n = 29;
printf("%d is %s\n", n, isPrime(n) ? "prime" : "not prime");
printf("Prime numbers up to 50:\n");
for (int i = 2; i <= 50; i++) {
if (isPrime(i)) {
printf("%d ", i);
}
}
printf("\n");
return 0;
}
Complexity: O(√n)
Sieve of Eratosthenes
Efficiently finds all primes up to n.
C++ Implementation
#include <iostream>
#include <vector>
using namespace std;
vector<int> sieveOfEratosthenes(int n) {
vector<bool> isPrime(n + 1, true);
vector<int> primes;
isPrime[0] = isPrime[1] = false;
for (int i = 2; i <= n; i++) {
if (isPrime[i]) {
primes.push_back(i);
// Mark multiples as non-prime
for (long long j = (long long)i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}
return primes;
}
// Segmented Sieve (for very large ranges)
vector<int> segmentedSieve(int L, int R) {
int limit = sqrt(R) + 1;
vector<int> basePrimes = sieveOfEratosthenes(limit);
vector<bool> isPrime(R - L + 1, true);
for (int prime : basePrimes) {
// Find first multiple of prime in [L, R]
int start = max(prime * prime, (L + prime - 1) / prime * prime);
for (int j = start; j <= R; j += prime) {
isPrime[j - L] = false;
}
}
vector<int> primes;
for (int i = L; i <= R; i++) {
if (i > 1 && isPrime[i - L]) {
primes.push_back(i);
}
}
return primes;
}
int main() {
int n = 50;
vector<int> primes = sieveOfEratosthenes(n);
cout << "Primes up to " << n << ":" << endl;
for (int prime : primes) {
cout << prime << " ";
}
cout << endl;
cout << "Count: " << primes.size() << endl;
return 0;
}
Complexity: O(n log log n)
Java Implementation
import java.util.*;
public class SieveOfEratosthenes {
public static List<Integer> sieve(int n) {
boolean[] isPrime = new boolean[n + 1];
Arrays.fill(isPrime, true);
isPrime[0] = isPrime[1] = false;
List<Integer> primes = new ArrayList<>();
for (int i = 2; i <= n; i++) {
if (isPrime[i]) {
primes.add(i);
for (long j = (long) i * i; j <= n; j += i) {
isPrime[(int) j] = false;
}
}
}
return primes;
}
public static void main(String[] args) {
int n = 50;
List<Integer> primes = sieve(n);
System.out.println("Primes up to " + n + ": " + primes);
System.out.println("Count: " + primes.size());
}
}
Prime Factorization
Decompose a number into prime factors.
C++ Implementation
#include <iostream>
#include <vector>
#include <map>
using namespace std;
// Basic factorization
vector<int> primeFactors(int n) {
vector<int> factors;
// Handle 2 separately
while (n % 2 == 0) {
factors.push_back(2);
n /= 2;
}
// Check odd factors up to √n
for (int i = 3; i * i <= n; i += 2) {
while (n % i == 0) {
factors.push_back(i);
n /= i;
}
}
// If n is still > 1, it's prime
if (n > 1) {
factors.push_back(n);
}
return factors;
}
// Factorization with counts
map<int, int> primeFactorization(int n) {
map<int, int> factors;
while (n % 2 == 0) {
factors[2]++;
n /= 2;
}
for (int i = 3; i * i <= n; i += 2) {
while (n % i == 0) {
factors[i]++;
n /= i;
}
}
if (n > 1) {
factors[n]++;
}
return factors;
}
int main() {
int n = 84;
vector<int> factors = primeFactors(n);
cout << n << " = ";
for (size_t i = 0; i < factors.size(); i++) {
cout << factors[i];
if (i < factors.size() - 1) cout << " × ";
}
cout << endl;
map<int, int> factorization = primeFactorization(n);
cout << n << " = ";
bool first = true;
for (auto& [prime, count] : factorization) {
if (!first) cout << " × ";
cout << prime;
if (count > 1) cout << "^" << count;
first = false;
}
cout << endl;
return 0;
}
Complexity: O(√n)
Modular Arithmetic
Essential for cryptography and hash functions.
Basic Operations
#include <iostream>
using namespace std;
// Modular addition
long long modAdd(long long a, long long b, long long mod) {
return ((a % mod) + (b % mod)) % mod;
}
// Modular subtraction
long long modSub(long long a, long long b, long long mod) {
return ((a % mod) - (b % mod) + mod) % mod;
}
// Modular multiplication
long long modMul(long long a, long long b, long long mod) {
return ((a % mod) * (b % mod)) % mod;
}
// Modular exponentiation: (base^exp) % mod
long long modPow(long long base, long long exp, long long mod) {
long long result = 1;
base %= mod;
while (exp > 0) {
if (exp & 1) {
result = (result * base) % mod;
}
base = (base * base) % mod;
exp >>= 1;
}
return result;
}
// Modular inverse using extended GCD
long long extendedGCD(long long a, long long b, long long& x, long long& y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
long long x1, y1;
long long gcd = extendedGCD(b, a % b, x1, y1);
x = y1;
y = x1 - (a / b) * y1;
return gcd;
}
long long modInverse(long long a, long long mod) {
long long x, y;
long long gcd = extendedGCD(a, mod, x, y);
if (gcd != 1) {
return -1; // Inverse doesn't exist
}
return (x % mod + mod) % mod;
}
int main() {
long long a = 7, b = 3, mod = 11;
cout << "(" << a << " + " << b << ") mod " << mod << " = " << modAdd(a, b, mod) << endl;
cout << "(" << a << " - " << b << ") mod " << mod << " = " << modSub(a, b, mod) << endl;
cout << "(" << a << " × " << b << ") mod " << mod << " = " << modMul(a, b, mod) << endl;
cout << "(" << a << "^" << b << ") mod " << mod << " = " << modPow(a, b, mod) << endl;
long long inv = modInverse(a, mod);
cout << "Inverse of " << a << " mod " << mod << " = " << inv << endl;
cout << "Verification: (" << a << " × " << inv << ") mod " << mod << " = "
<< modMul(a, inv, mod) << endl;
return 0;
}
Common Mistakes
- Integer overflow - In LCM calculation, multiply after dividing
- Not handling edge cases - Zero, one, negative numbers
- Inefficient primality tests - Checking all divisors instead of up to √n
- Sieve array size - Off-by-one errors
- Modular arithmetic errors - Not taking mod at each step
- Wrong GCD base case - Handling zero incorrectly
- Infinite loops - In iterative GCD with wrong condition
Debugging Tips
- Test with small numbers - Easy to verify manually
- Check edge cases - 0, 1, 2, negative numbers
- Verify mathematical properties - GCD(a, b) × LCM(a, b) = a × b
- Use known primes - Test sieve with primes you know
- Print intermediate values - In modular exponentiation
- Validate factorization - Multiply factors to get original
- Test overflow scenarios - Large numbers in LCM
Mini Exercises
- Implement binary GCD (Stein's algorithm)
- Count number of divisors of n
- Find nth prime number
- Compute Euler's totient function φ(n)
- Check if two numbers are coprime
- Find smallest prime factor
- Implement Miller-Rabin primality test
- Solve linear congruences
- Compute Fibonacci modulo m
- Find modular multiplicative inverse
Review Questions
- Why is Euclidean algorithm efficient for GCD?
- How does Sieve of Eratosthenes work?
- What's the relationship between GCD and LCM?
- When does modular inverse exist?
- Why is modular exponentiation important in cryptography?
Reference Checklist
By the end of this chapter, you should be able to:
- Implement GCD using Euclidean algorithm
- Calculate LCM efficiently
- Test primality of numbers
- Generate primes using Sieve of Eratosthenes
- Perform prime factorization
- Use modular arithmetic operations
- Compute modular exponentiation
- Find modular inverse
Next Steps
Chapter 15 explores cryptographic algorithms—RSA encryption, Diffie-Hellman key exchange, and advanced modular arithmetic applications in modern cryptography.
Key Takeaway: Mathematical algorithms are fundamental to computer science. GCD and LCM solve scheduling and fraction problems. Prime numbers and modular arithmetic power modern cryptography. Understanding these algorithms enables you to build secure systems and solve complex computational problems efficiently.