Number Theory

number-theory: The Ultimate Cheatsheet

1. Detailed Explanation

• What is number-theory?

Number theory is a branch of pure mathematics devoted primarily to the study of integers and their properties. It explores relationships between numbers, especially integers, and includes topics like divisibility, prime numbers, congruences, and Diophantine equations.

• Why is it important and what kind of problems does it solve?

Number theory is crucial in many fields, including:

*   **Cryptography:** Modern encryption algorithms like RSA rely heavily on prime numbers and modular arithmetic.
*   **Computer Science:** Hashing algorithms, random number generation, and data compression techniques often use number-theoretic concepts.
*   **Engineering:** Signal processing and coding theory utilize number theory.
*   **Pure Mathematics:** Number theory is a fundamental area of mathematical research with deep connections to other fields.

Number theory helps solve problems like:

*   Finding prime numbers and factoring integers.
*   Determining if a number is divisible by another number.
*   Solving modular equations.
*   Designing secure cryptographic systems.
*   Generating pseudo-random numbers.

• Core concepts, underlying principles, and key terminology.

  • Integers: The set of whole numbers (…, -2, -1, 0, 1, 2, …).
  • Divisibility: An integer a is divisible by an integer b if there exists an integer k such that a = b * k. We write b | a.
  • Prime Number: A natural number greater than 1 that has no positive divisors other than 1 and itself.
  • Composite Number: A natural number greater than 1 that is not prime (i.e., it has divisors other than 1 and itself).
  • Greatest Common Divisor (GCD): The largest positive integer that divides two or more integers without a remainder.
  • Least Common Multiple (LCM): The smallest positive integer that is divisible by two or more integers.
  • Euclidean Algorithm: An efficient algorithm for computing the GCD of two integers.
  • Modular Arithmetic: A system of arithmetic for integers where numbers “wrap around” upon reaching a certain value (the modulus). We write a ≡ b (mod m) if a and b have the same remainder when divided by m.
  • Congruence: The relationship between two integers that are congruent modulo m.
  • Modular Inverse: An integer x such that ax ≡ 1 (mod m), where a and m are coprime (i.e., GCD(a, m) = 1).
  • Prime Factorization: Expressing a composite number as a product of its prime factors.
  • Fermat’s Little Theorem: If p is a prime number, then for any integer a not divisible by p, a^(p-1) ≡ 1 (mod p).
  • Euler’s Totient Function (φ(n)): Counts the number of integers between 1 and n that are coprime to n.

2. When to Use number-theory (and When Not To)

• Identify problem patterns that suggest number-theory is a good fit.

  • Problems involving divisibility, prime numbers, GCD, LCM, or modular arithmetic.
  • Problems that require finding factors or prime factorization of numbers.
  • Problems that involve cryptography or secure communication.
  • Problems that ask for the number of integers with specific properties.
  • Problems where the constraints involve very large numbers and efficient calculations are necessary.

• Discuss scenarios where a different data structure or algorithm would be more appropriate.

  • If the problem primarily involves sorting or searching a collection of numbers without any specific number-theoretic properties, standard sorting algorithms (e.g., merge sort, quicksort) or search algorithms (e.g., binary search) would be more appropriate.
  • If the problem involves manipulating strings or text, string algorithms (e.g., string matching, suffix trees) should be used.
  • If the problem requires graph traversal or shortest path finding, graph algorithms (e.g., BFS, DFS, Dijkstra’s algorithm) are more suitable.
  • If the problem focuses on geometric calculations, computational geometry techniques should be applied.
  • If the problem requires statistical analysis, statistical methods and libraries should be used.

3. Core Algorithm / Data Structure Template

Here’s a general template for approaching number theory problems:

1. Understand the Problem: Carefully read the problem statement and identify the key number-theoretic concepts involved.
2. Identify Relevant Concepts: Determine which concepts like divisibility, prime numbers, GCD, LCM, modular arithmetic, etc., are relevant to the problem.
3. Choose Appropriate Algorithms: Select the most efficient algorithms for the specific tasks required. Examples include:
   • Euclidean Algorithm for GCD.
   • Sieve of Eratosthenes for finding prime numbers.
   • Modular exponentiation for fast power calculations.
4. Implement the Algorithms: Write clean, well-commented code for the chosen algorithms.
5. Combine Algorithms: Combine the individual algorithms to solve the overall problem.
6. Optimize for Efficiency: Consider optimizations such as memoization or precomputation to improve performance.
7. Test Thoroughly: Test the solution with a variety of test cases, including edge cases and large inputs.

4. Code Implementations (Python, Java, C++)

Python

def gcd(a, b):
    """
    Calculates the greatest common divisor (GCD) of two integers using the Euclidean algorithm.

    Args:
        a: The first integer.
        b: The second integer.

    Returns:
        The GCD of a and b.
    """
    while(b):
        a, b = b, a % b
    return a

def is_prime(n):
    """
    Checks if a number is prime.

    Args:
        n: The number to check.

    Returns:
        True if n is prime, False otherwise.
    """
    if n <= 1:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

def extended_gcd(a, b):
  """
  Extended Euclidean Algorithm to find gcd(a, b) and coefficients x, y
  such that ax + by = gcd(a, b).

  Returns: (gcd, x, y)
  """
  if a == 0:
    return (b, 0, 1)

  gcd, x1, y1 = extended_gcd(b % a, a)

  x = y1 - (b // a) * x1
  y = x1

  return (gcd, x, y)

def modular_inverse(a, m):
    """
    Calculates the modular inverse of a modulo m using the Extended Euclidean Algorithm.

    Args:
        a: The integer for which to find the inverse.
        m: The modulus.

    Returns:
        The modular inverse of a modulo m, or None if it doesn't exist.
    """
    gcd, x, y = extended_gcd(a, m)
    if gcd != 1:
        return None  # a and m are not coprime, so the inverse doesn't exist
    else:
        return x % m  # Ensure the result is positive

Java

class NumberTheory {
    /**
     * Calculates the greatest common divisor (GCD) of two integers using the Euclidean algorithm.
     *
     * @param a The first integer.
     * @param b The second integer.
     * @return The GCD of a and b.
     */
    public static long gcd(long a, long b) {
        while (b != 0) {
            long temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    /**
     * Checks if a number is prime.
     *
     * @param n The number to check.
     * @return True if n is prime, False otherwise.
     */
    public static boolean isPrime(long n) {
        if (n <= 1) {
            return false;
        }
        for (long i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static long[] extendedGCD(long a, long b) {
        if (a == 0) {
            return new long[] {b, 0, 1};
        }

        long[] result = extendedGCD(b % a, a);
        long gcd = result[0];
        long x1 = result[1];
        long y1 = result[2];

        long x = y1 - (b / a) * x1;
        long y = x1;

        return new long[] {gcd, x, y};
    }

    public static Long modularInverse(long a, long m) {
        long[] result = extendedGCD(a, m);
        long gcd = result[0];
        long x = result[1];

        if (gcd != 1) {
            return null; // Inverse doesn't exist
        } else {
            return (x % m + m) % m; // Ensure positive result
        }
    }
}

C++

#include <iostream>

using namespace std;

/**
 * Calculates the greatest common divisor (GCD) of two integers using the Euclidean algorithm.
 *
 * @param a The first integer.
 * @param b The second integer.
 * @return The GCD of a and b.
 */
long long gcd(long long a, long long b) {
    while (b) {
        long long temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

/**
 * Checks if a number is prime.
 *
 * @param n The number to check.
 * @return True if n is prime, False otherwise.
 */
bool isPrime(long long n) {
    if (n <= 1) {
        return false;
    }
    for (long long i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

tuple<long long, long long, long long> extended_gcd(long long a, long long b) {
    if (a == 0) {
        return make_tuple(b, 0, 1);
    }

    long long gcd, x1, y1;
    tie(gcd, x1, y1) = extended_gcd(b % a, a);

    long long x = y1 - (b / a) * x1;
    long long y = x1;

    return make_tuple(gcd, x, y);
}


long long modular_inverse(long long a, long long m) {
    long long gcd, x, y;
    tie(gcd, x, y) = extended_gcd(a, m);

    if (gcd != 1) {
        return -1; // Inverse doesn't exist
    } else {
        return (x % m + m) % m; // Ensure positive result
    }
}

5. Complexity Analysis

Operation	Time Complexity	Space Complexity	Best Case	Average Case	Worst Case
gcd(a, b)	O(log(min(a, b)))	O(1)	O(1)	O(log(min(a, b)))	O(log(min(a, b)))
isPrime(n)	O(sqrt(n))	O(1)	O(1)	O(sqrt(n))	O(sqrt(n))
extended_gcd(a, b)	O(log(min(a, b)))	O(log(min(a, b)))	O(1)	O(log(min(a, b)))	O(log(min(a, b)))
modular_inverse(a, m)	O(log(min(a, m)))	O(log(min(a, m)))	O(1)	O(log(min(a, m)))	O(log(min(a, m)))

• GCD: The Euclidean algorithm’s time complexity is logarithmic in the smaller of the two numbers. Space complexity is O(1) due to the iterative nature, although a recursive implementation would have O(log n) stack space.
• isPrime: The time complexity for the naive prime check is O(sqrt(n)). Space complexity is O(1).
• extended_gcd: Similar to GCD, the time complexity is O(log(min(a, b))). The recursive implementation has O(log(min(a, b))) stack space in the worst case.
• modular_inverse: Dominated by the extended GCD, so O(log(min(a, m))). The recursive implementation has O(log(min(a, m))) stack space in the worst case.

6. Pro Tips, Tricks, and Common Pitfalls

• Pro Tips:

  • Precomputation: For problems involving repeated calculations of the same values (e.g., prime numbers within a range), precompute and store the results in an array or table to avoid redundant calculations. The Sieve of Eratosthenes is an excellent example of precomputation.
  • Modular Arithmetic Properties: Utilize properties of modular arithmetic (e.g., (a + b) mod m = (a mod m + b mod m) mod m) to prevent integer overflow and simplify calculations.
  • Fermat’s Little Theorem / Euler’s Theorem: Leverage these theorems to simplify modular exponentiation and find modular inverses in certain cases.
  • Binary Exponentiation (Modular Exponentiation): Use this technique to efficiently calculate large powers modulo a number.
  • Understand Constraints: Pay close attention to the constraints on the input values. This can help determine the most appropriate algorithms and data structures to use.
  • Prime Factorization Optimization: When finding prime factors, you only need to check up to the square root of the number.

• Common Pitfalls:

  • Integer Overflow: Be careful when dealing with large numbers, especially when multiplying or exponentiating. Use appropriate data types (e.g., long long in C++, long in Java, int in Python for larger values) and use modular arithmetic to prevent overflow.
  • Division by Zero: Avoid division by zero, especially when calculating modular inverses. Ensure that the divisor is not zero or that a modular inverse exists.
  • Incorrect Modular Arithmetic: Make sure to apply the modulo operator correctly throughout the calculations to maintain the desired modular properties. Remember (a * b) mod m = ((a mod m) * (b mod m)) mod m.
  • Inefficient Prime Checking: Using a naive prime checking algorithm (checking divisibility up to n) can be very slow for large numbers. Use more efficient algorithms like the Sieve of Eratosthenes or Miller-Rabin primality test.
  • Off-by-One Errors: Be careful with loop conditions and array indices, especially when dealing with prime numbers or factors.
  • Not Considering Edge Cases: Always test your solution with edge cases, such as 0, 1, negative numbers (if allowed), and very large numbers.
  • Assuming Coprimality: Remember that modular inverses only exist if the number and the modulus are coprime (GCD is 1).

7. Classic Problem Examples

Example: Add Digits

Description: Given an integer num, repeatedly add all its digits until the result has only one digit, and return it.

High-Level Approach:

The problem can be solved without a loop or recursion using the concept of digital root. The digital root of a number is the single-digit value obtained by repeatedly adding the digits of a number until a single digit is obtained. The digital root can be calculated using the formula:

digital_root(n) = 0 if n == 0 else 1 + (n - 1) % 9

This formula is based on the fact that the digital root of a number is congruent to the number modulo 9 (except when the number is a multiple of 9, in which case the digital root is 9, and when the number is zero, in which case the digital root is 0). The formula handles the case where n is a multiple of 9 correctly.

def addDigits(num: int) -> int:
    if num == 0:
        return 0
    else:
        return 1 + (num - 1) % 9