ℕNumber Theory
Elementary, algebraic, analytic number theory, cryptography
Subfields
Elementary Number Theory
Divisibility, congruences, Fermat's little theorem, Euler's theorem
Algebraic Number Theory
Algebraic integers, ideals, class numbers, class field theory
Analytic Number Theory
Prime distribution, Riemann zeta function, Riemann hypothesis
Combinatorial Number Theory
Ramsey theory, additive combinatorics, partitions
Cryptographic Number Theory
RSA, elliptic curve cryptography, discrete logarithm problem
Concepts
Prime Numbers
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. Every natural number can be uniquely expressed as a product of primes.
GCD and LCM
GCD (Greatest Common Divisor) is the largest common divisor of two numbers. LCM (Least Common Multiple) is the smallest common multiple.
Fermat's Little Theorem
If p is prime and a is not divisible by p, then a^(p-1) ≡ 1 (mod p).
Fibonacci Sequence
The Fibonacci sequence is where each term is the sum of the two preceding terms. F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2).
Diophantine Equations
Diophantine equations are polynomial equations seeking integer solutions. Key problems are existence and finding all solutions.
Modular Arithmetic
Modular arithmetic is a system where calculations are done with remainders after division by a modulus. Also called clock arithmetic.
Chinese Remainder Theorem
A system of congruences with pairwise coprime moduli has a unique solution. It allows decomposing large computations into smaller ones.
Euler's Totient Function
Euler's totient function φ(n) counts positive integers up to n that are coprime to n. It's central to RSA cryptography.
Quadratic Residues
An integer a is a quadratic residue mod n if there exists x such that x² ≡ a (mod n).