Numerical Number Theory

Numerical Number Theory encompasses a wide range of topics centered on the properties and relationships of integers. From basic divisibility to advanced primality testing and factorization algorithms, it serves as the foundation for numerous applications in computer science, cryptography, and other fields.

Note 1: Divisibility and the Euclidean Algorithm: Divisibility is a foundational concept. We say that an integer 'a' divides an integer 'b' (written a|b) if there exists an integer 'k' such that b = ak. Understanding divisibility allows us to explore prime numbers, greatest common divisors (GCD), and least common multiples (LCM). The Euclidean Algorithm is a cornerstone for finding the GCD of two integers. It involves repeatedly applying the division algorithm until the remainder is zero. The last non-zero remainder is the GCD. Historically, Euclid's Elements (circa 300 BC) presented this algorithm. A common misconception is thinking the GCD is always 1; two numbers are relatively prime (or coprime) if their GCD is 1. Practical applications include simplifying fractions and cryptographic algorithms.

Note 2: Prime Numbers and the Fundamental Theorem of Arithmetic: A prime number is an integer greater than 1 that has exactly two distinct positive divisors: 1 and itself. The Fundamental Theorem of Arithmetic states that every integer greater than 1 can be uniquely expressed as a product of prime numbers, up to the order of the factors. This theorem is the bedrock of many number-theoretic results. For example, 12 = 2^2 * 3. Finding large prime numbers is computationally challenging but crucial for cryptography. Eratosthenes of Cyrene (c. 276–194 BC) devised the Sieve of Eratosthenes, an efficient algorithm for finding all prime numbers up to a specified integer. Students sometimes believe that 1 is prime; it isn't by definition.

Note 3: Modular Arithmetic: Modular arithmetic involves performing arithmetic operations within a finite set of integers, called a residue system. We say that 'a' is congruent to 'b' modulo 'm' (written a ≡ b (mod m)) if 'm' divides (a - b). This creates equivalence classes of integers that share the same remainder when divided by 'm'. Modular arithmetic is widely used in computer science (hashing, cryptography), and it provides a framework for studying the remainders of arithmetic operations. Fermat's Little Theorem and Euler's Theorem are important results related to modular exponentiation. A frequent error is forgetting to reduce the result modulo 'm' after each arithmetic operation.

Note 4: Congruences and Linear Congruences: A congruence is an equation of the form ax ≡ b (mod m), where a, b, and m are integers. Solving a linear congruence means finding the values of 'x' that satisfy the equation. The existence and uniqueness of solutions depend on the GCD of 'a' and 'm'. Specifically, a solution exists if and only if gcd(a, m) divides b. If gcd(a, m) = 1, then there is a unique solution modulo m. The Chinese Remainder Theorem (CRT) provides a method for solving systems of linear congruences with pairwise relatively prime moduli. CRT has practical applications in coding theory and computer science. Confusing congruence equations with standard equations is a common mistake.

Note 5: Euler's Totient Function: Euler's totient function, denoted φ(n), counts the number of positive integers less than or equal to n that are relatively prime to n. That is, φ(n) is the number of integers k in the range 1 ≤ k ≤ n for which gcd(n, k) = 1. If n is a prime number, then φ(n) = n - 1. Euler's theorem, a generalization of Fermat's Little Theorem, states that if a and n are coprime, then a^φ(n) ≡ 1 (mod n). The totient function plays a crucial role in public-key cryptography, such as RSA. Calculating φ(n) can be challenging for large n if its prime factorization is unknown. Many think that φ(n) always equals n-1, which is only true if n is prime.

Note 6: Quadratic Residues and the Legendre Symbol: An integer 'a' is a quadratic residue modulo 'm' if there exists an integer 'x' such that x^2 ≡ a (mod m). Determining whether 'a' is a quadratic residue is fundamental in many number theory problems. The Legendre symbol (a/p) is defined for an odd prime 'p' and an integer 'a' not divisible by 'p'. It is equal to 1 if 'a' is a quadratic residue modulo 'p', -1 if 'a' is a quadratic non-residue modulo 'p', and 0 if p divides a. Quadratic reciprocity is a powerful theorem that relates the Legendre symbols (p/q) and (q/p) for distinct odd primes p and q. Understanding these concepts is vital in advanced cryptography and coding theory. A common oversight is not checking if the modulus is prime before using the Legendre symbol.

Note 7: Diophantine Equations: A Diophantine equation is a polynomial equation, usually with two or more unknowns, such that only integer solutions are sought or studied. A classic example is the linear Diophantine equation ax + by = c, where a, b, and c are integers, and we seek integer solutions for x and y. Solutions exist if and only if gcd(a, b) divides c. Finding all solutions typically involves finding one particular solution and then parameterizing the general solution using the GCD. Fermat's Last Theorem, a famous unsolved problem for centuries, concerns the Diophantine equation x^n + y^n = z^n for integer solutions with n > 2. A misunderstanding is assuming that all Diophantine equations have solutions; most don't.

Note 8: Continued Fractions: A continued fraction is an expression of the form a_0 + 1/(a_1 + 1/(a_2 + ...)), where a_0, a_1, a_2, ... are integers. Continued fractions provide a way to represent real numbers, both rational and irrational. Every rational number has a finite continued fraction representation, while every irrational number has an infinite continued fraction representation. Continued fractions are useful for finding good rational approximations to irrational numbers. For example, the continued fraction representation of pi allows us to find increasingly accurate rational approximations. Some misunderstand the connection between finite and infinite continued fractions; only rational numbers have finite representations.

Note 9: Primality Testing: Determining whether a given number is prime is a fundamental problem in number theory. While trial division (checking divisibility by all integers up to the square root of the number) works for small numbers, it is inefficient for large numbers. Probabilistic primality tests, such as the Miller-Rabin test, are widely used in practice. These tests do not guarantee primality but provide a high degree of certainty. Deterministic primality tests, such as the AKS primality test, guarantee primality but are computationally more expensive. The search for efficient primality tests continues to be an active area of research. It's a misconception that probabilistic tests are always incorrect; the probability of error can be made arbitrarily small.

Note 10: Integer Factorization: Integer factorization is the process of decomposing a composite number into its prime factors. While the Fundamental Theorem of Arithmetic guarantees the uniqueness of the prime factorization, finding the factors can be computationally difficult for large numbers. The difficulty of factoring large numbers is the basis for many public-key cryptosystems, such as RSA. Algorithms for integer factorization include trial division, Pollard's rho algorithm, and the quadratic sieve. The general number field sieve is the most efficient algorithm known for factoring very large numbers. People often assume that factorization is 'easy', but this is not true for sufficiently large numbers.

Browse public study notes