Number Theory

Prime Numbers

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.

Primality Test: A simple way to check if a number n is prime is to try dividing it by all integers from 2 up to sqrt(n). If none of these divide n evenly, then n is prime. This is an O(sqrt(n)) algorithm.

Sieve of Eratosthenes: An efficient algorithm for finding all prime numbers up to a specified integer N. It works by iteratively marking as composite the multiples of each prime. Its complexity is O(N log log N).

Divisibility and GCD

Greatest Common Divisor (GCD): The largest positive integer that divides two integers. Also known as Greatest Common Factor (GCF).

Euclidean Algorithm: A highly efficient method for computing the GCD of two integers a and b. The principle is that gcd(a, b) = gcd(b, a % b). The base case is when b is 0, in which case the GCD is a. This is extremely fast, with a complexity of O(log(min(a,b))).

Modular Arithmetic

Modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" upon reaching a certain value—the modulus m.

Properties: The key to working with large numbers is to apply the modulus at each step of a calculation:

• (a + b) % m = ((a % m) + (b % m)) % m
• (a - b) % m = ((a % m) - (b % m) + m) % m (add m to handle negative results)
• (a * b) % m = ((a % m) * (b % m)) % m

Modular Exponentiation (Binary Exponentiation):

A common problem is to compute (base^exp) % m for very large exponents. Doing base^exp first would cause overflow. We can use the properties of modular arithmetic combined with the idea of representing the exponent in binary to solve this in O(log exp) time.

Modular Inverse: The modular multiplicative inverse of an integer a (mod m) is an integer x such that (a * x) % m = 1. This allows for division in modular arithmetic: (b / a) % m = (b * x) % m. An inverse exists only if a and m are coprime (gcd(a,m)==1). It can be found using the Extended Euclidean Algorithm or, if m is prime, using Fermat's Little Theorem: a^(m-2) % m.