Number Theory Lecture 1

Overview

Number theory is the mathematical study of integers and their properties. This lecture introduces foundational concepts that form the basis for more advanced number theory and competitive programming techniques. You'll explore what the GCD is, how to compute it using the Euclidean Algorithm, the nature of prime numbers, and efficient methods to determine primality, including the Sieve of Eratosthenes.

Part 1: Greatest Common Divisor (GCD)

The Greatest Common Divisor (GCD) of two or more integers is the largest integer that divides all of them without leaving any remainder. If two numbers have GCD = 1, they are called co-prime.

Example

gcd(24, 16):

• Divisors of 24: 1, 2, 3, 4, 6, 8, 12, 24
• Divisors of 16: 1, 2, 4, 8, 16
• Common divisors: 1, 2, 4, 8
• Result: GCD = 8

Key Properties of GCD

• gcd(a, b) = gcd(b, a % b)
• gcd(x, 0) = x
• gcd(a, b) = gcd(a - b, b) (basic recursive idea)

Mathematical Proof

Assume a = d·x and b = d·y, then:

a - b = d·(x - y), so d divides a - b as well.

Part 2: Euclidean Algorithm

The Euclidean Algorithm is an efficient method for computing the GCD of two numbers based on the principle:

gcd(a, b) = gcd(b, a % b)

This recursive reduction continues until one value becomes zero.

Time Complexity

Each step reduces the size of the inputs significantly. The algorithm runs in O(log min(a, b)).

Code Example

int gcd(int a, int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}

Real-World Application Problem

Given two arrays A[1..n] and B[1..m], for each B[j] compute:

gcd(A[1] + B[j], A[2] + B[j], ..., A[n] + B[j])

Optimized Solution:

• Let d = gcd(|A[2] - A[1]|, ..., |A[n] - A[1]|)
• Then answer is gcd(A[1] + B[j], d) for each B[j]

ll computeGCD(const vector& a) {
  ll d = 0;
  for (int i = 1; i < a.size(); ++i)
    d = gcd(d, abs(a[i] - a[0]));
  return d;
}

vector solve(const vector& a, const vector& b) {
  ll baseGCD = computeGCD(a);
  vector result;
  for (ll bj : b)
    result.push_back(gcd(a[0] + bj, baseGCD));
  return result;
}

Part 3: Prime Numbers

A prime number is a number greater than 1 that is divisible only by 1 and itself.

Examples:

• Prime: 2, 3, 5, 7, 11
• Not Prime: 4 (2×2), 6 (2×3), 9 (3×3)

Naive Primality Test

bool isPrime(int n) {
  if (n < 2) return false;
  for (int i = 2; i < n; ++i)
    if (n % i == 0) return false;
  return true;
}

Time: O(n)

Optimized Primality Test

bool isPrime(int n) {
  if (n < 2) return false;
  for (int i = 2; i * i <= n; ++i)
    if (n % i == 0) return false;
  return true;
}

Time: O(√n)

Part 4: Sieve of Eratosthenes

The Sieve of Eratosthenes is a powerful method to find all primes from 1 to n.

vector sieve(int n) {
  vector isPrime(n+1, 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;
}

Why Start from i * i?

Any composite number less than i * i would have already been marked by smaller prime factors.

Time Complexity: O(n log log n)

Summary Table