maths.free › Number Theory

Number Theory

The mathematics of whole numbers. Some of the oldest problems and the newest cryptography live here: factor a number into primes, run Euclid's algorithm, compute huge powers modulo a prime without ever writing the power down.

Dersler

Introductory Prime factorisation Every integer is a product of primes in exactly one way. prime factorization of 360 Introductory Prime numbers Testing for primality by trial division up to the square root. is 97 prime Introductory GCD and LCM Euclid's algorithm and the identity gcd × lcm = a × b. gcd(48, 18) Core Modular arithmetic Remainders, congruences, fast powers and modular inverses. 3^100 mod 7 Introductory Divisors Counting and listing divisors from the prime factorisation. divisors of 36 Core Sequences Fibonacci, recurrences and closed forms. fib(20) Introductory Number bases Converting between decimal, binary, octal and hexadecimal. 255 to binary Core Diophantine equations Integer solutions: linear equations via Bézout, Pythagorean triples, Fermat. gcd(12, 18) Core Fermat's little theorem and Euler's theorem aᵖ⁻¹ ≡ 1 (mod p), the totient, and fast modular arithmetic. 2^100 mod 13 Advanced RSA: cryptography from number theory Public keys from two primes, and why factoring is the lock. inverse of 17 mod 3120

Symbols used here

\log_b x,\ \ln x
logarithm, natural log
The exponent b must be raised to for x; ln uses base e.
\sum_{k=1}^{n} a_k
summation
Add a_k for k = 1 up to n.
\prod_{k=1}^{n} a_k
product
Multiply a_k for k = 1 up to n.
\mathbb{N},\ \mathbb{Z},\ \mathbb{Q},\ \mathbb{R},\ \mathbb{C}
number sets
Naturals, integers, rationals, reals, complex numbers.
a \equiv b \pmod n
congruent modulo n
n divides a − b; a and b have the same remainder.
a \mid b,\ \gcd(a,b)
divides, greatest common divisor
b is a multiple of a; the largest number dividing both.
\varphi(n),\ \pi(x)
Euler's totient, prime-counting function
Count of 1..n coprime to n; number of primes up to x.
\mathbb{Z}/n\mathbb{Z},\ \mathbb{Z}_n
integers modulo n
The remainders 0…n−1 with clock arithmetic.
a \bmod n
remainder
What is left after dividing a by n.

Questions people ask

Why are primes so important?

Every integer factors into primes in exactly one way, so primes are the atoms of multiplication. Cryptography relies on that factoring being easy to state and hard to do.

How do I tell whether a big number is prime?

Trial division up to the square root works for small numbers. For large ones, probabilistic tests (Miller–Rabin) give an answer that is wrong with negligible probability, and deterministic tests (AKS) exist but are slower.

Diğer dallar

＋ Arithmetic𝑥 Algebra△ Geometry∿ Trigonometryƒ Precalculusσ Statistics & Probability⊢ Discrete Math & Logic∫ Calculus⊞ Linear Algebraẏ Differential Equations∇ Multivariable Calculusε Real Analysis⋔ Combinatorics & Graph Theory∈ Set Theory & Logic𝔾 Abstract Algebra𝑃 Probability Theory≈ Numerical Methodsℂ Complex Analysis◎ Topologyμ Measure Theory‖·‖ Functional Analysisκ Differential Geometryπ₁ Algebraic Topology→ Category Theory∞ Frontiers