Suggest an edit

Improve this article

Refine the answer for “What does number theory study?”. Your changes go to moderation before they’re published.

Approval required

Content

What you’re changing

Title (EN)

Short answer (EN)

Shown above the full answer for quick recall.

Answer (EN)

## What does number theory study?

### Short answer

Number theory is the branch of mathematics concerned with the properties of integers and related structures: divisibility, prime numbers and their distribution, modular arithmetic (congruences), solutions of Diophantine equations, and algorithms built on these ideas (for example, for cryptography).

### Detailed answer

#### Definition and the subject area

Number theory studies natural and integer numbers, their factorization into primes, divisibility, congruences modulo m, and also equations whose solutions are sought among integers or rationals (Diophantine equations). Modern number theory relies on tools from analysis, algebra, and computational mathematics.

#### Key areas and ideas

- Divisibility and algorithms.
  - GCD, the Euclidean algorithm, Bezout's lemma: for integers a, b there exist x, y such that ax + by = gcd(a, b).
  - The fundamental theorem of arithmetic: any n > 1 has a unique representation as a product of prime powers.
- Primes and factorization.
  - Primality tests (Miller-Rabin), factorization methods (Pollard's rho, the quadratic sieve).
  - Distribution of primes: how many primes do not exceed x.
- Congruences and modular arithmetic.
  - a ≡ b (mod m) means that m divides a − b; one can add, multiply, and raise to a power "modulo" m.
  - Fermat's little theorem: a^(p−1) ≡ 1 (mod p) for prime p with gcd(a, p)=1. Euler's theorem: a^φ(m) ≡ 1 (mod m) if gcd(a, m)=1.
  - The Chinese Remainder Theorem: a system of congruences with pairwise coprime moduli reduces to a single congruence modulo their product.
- Diophantine equations.
  - Linear: ax + by = c has integer solutions if and only if gcd(a, b) divides c.
  - Classical nonlinear ones: Pell's equation x^2 − Dy^2 = 1, Pythagorean triples, Mordell equations, and elliptic curves.
- Analytic number theory.
  - The prime number theorem: π(x) ~ x / ln x.
  - The Riemann zeta function and L-functions as tools for studying the distribution of primes.
- Algebraic number theory.
  - Rings of algebraic integers, factorization of primes in extensions of number fields, ideals, and class groups.
- Computational number theory and cryptography.
  - Practical algorithms: fast primality tests, modular exponentiation, the extended Euclidean algorithm, the Chinese Remainder Theorem in algorithmic form.
  - Applications: RSA, Diffie-Hellman, elliptic curves, signatures, and protocols.
- Additive and combinatorial number theory.
  - Sumsets, Schnirelmann-Roth-type theorems, the Goldbach and Waring conjectures.

#### Typical examples of problems and statements

- Check whether a number is prime; find its prime factorization for moderately large numbers.
- Solve the congruence a·x ≡ b (mod m) or a system of congruences with pairwise coprime moduli (CRT).
- Find GCD(a, b) and the Bezout coefficients x, y such that ax + by = gcd(a, b).
- Estimate the number of primes up to N and understand why cryptography algorithms on large numbers work.

#### Practical examples in code (Python)

```python
# Basic number theory tools for practice

def gcd(a: int, b: int) -> int:
    """Greatest common divisor (Euclidean algorithm)."""
    while b:
        a, b = b, a % b
    return abs(a)

def extended_gcd(a: int, b: int):
    """Extended Euclidean algorithm: returns (g, x, y), where ax + by = g = gcd(a, b)."""
    if b == 0:
        return (abs(a), 1 if a > 0 else -1, 0)
    g, x1, y1 = extended_gcd(b, a % b)
    return (g, y1, x1 - (a // b) * y1)

def mod_inverse(a: int, m: int) -> int:
    """Modular inverse: finds x such that a*x ≡ 1 (mod m), if gcd(a, m) = 1."""
    g, x, _ = extended_gcd(a, m)
    if g != 1:
        raise ValueError("Modular inverse does not exist")
    return x % m

def is_probable_prime(n: int) -> bool:
    """Probabilistic Miller-Rabin test for n > 3 (sufficient for practice).
    Small n are handled trivially.
    """
    if n < 2:
        return False
    small_primes = [2, 3, 5, 7, 11]
    if n in small_primes:
        return True
    for p in small_primes:
        if n % p == 0:
            return False
    # represent n-1 = 2^r * d, where d is odd
    d = n - 1
    r = 0
    while d % 2 == 0:
        d //= 2
        r += 1
    # fixed set of bases, sufficient for moderate n
    bases = [2, 3, 5, 7, 11]
    for a in bases:
        if a % n == 0:
            continue
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

def crt(remainders, moduli):
    """Chinese Remainder Theorem: solves the system x ≡ r_i (mod m_i) for pairwise coprime m_i.
    Returns (x, M), where M = prod(m_i) and x is the smallest nonnegative solution.
    """
    M = 1
    for m in moduli:
        M *= m
    x = 0
    for r, m in zip(remainders, moduli):
        Mi = M // m
        inv = mod_inverse(Mi % m, m)
        x = (x + r * Mi * inv) % M
    return x, M

if __name__ == "__main__":
    # GCD and Bezout coefficients
    a, b = 252, 198
    g, x, y = extended_gcd(a, b)
    print("gcd:", g, "Bezout check:", a * x + b * y)

# Modular inverse and solving the linear congruence a*x ≡ b (mod m)
    a, b, m = 7, 5, 26
    g = gcd(a, m)
    if b % g == 0:
        a_, b_, m_ = a // g, b // g, m // g
        inv = mod_inverse(a_, m_)
        x0 = (inv * b_) % m_
        print(f"Solution to a*x ≡ b (mod m): x ≡ {x0} (mod {m_})")

# Chinese Remainder Theorem: x ≡ 2 (mod 5), x ≡ 3 (mod 7)
    x, M = crt([2, 3], [5, 7])
    print("CRT:", x, "mod", M)  # 17 mod 35

# Probabilistic primality check
    for n in [97, 221, 10**9 + 7]:
        print(n, "prime?", is_probable_prime(n))

# Mini RSA demo (educational purposes only!)
    p, q = 61, 53
    n = p * q
    phi = (p - 1) * (q - 1)
    e = 17
    d = mod_inverse(e, phi)
    m = 42
    c = pow(m, e, n)
    m2 = pow(c, d, n)
    print("RSA:", "n=", n, "e=", e, "d=", d, "cipher=", c, "decrypted=", m2)
```

#### Practical applications (in IT and interviews)

- Cryptography and security: RSA, ECDSA, key-exchange protocols - all rely on prime numbers, modular arithmetic, and the difficulty of factorization/discrete logarithms.
- Hashing, sharding, and distributed systems: working modulo m, choosing good moduli (usually prime), assessing collisions and uniformity.
- Algorithm optimization: fast exponentiation, GCD computation, modular inverses - frequently appear in algorithm and data-structure problems.
- Checksums, coding, probabilistic structures (Bloom filters): choosing parameters based on the properties of numbers.

#### Key facts worth remembering

- Any natural number > 1 has a unique prime factorization.
- gcd(a, b) can be found quickly with the Euclidean algorithm; the extended version gives the coefficients for solving linear congruences.
- If gcd(a, m) = 1, then an inverse element a^{-1} exists modulo m and is unique modulo m.
- The "little" theorems (Fermat, Euler) provide the basis for fast exponentiation algorithms and primality tests.

Markdown · drag & drop images · ⌘B / ⌘I shortcuts1175 words

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.