Numbers and Number Theory glossary

Clear, one-line definitions of the Numbers and Number Theory terms used across the OgbonLab textbooks. Each entry links to the interactive sections where the idea is taught.

bezout coefficients

Integers s, t such that sa + tb = gcd(a, b); produced by the extended Euclidean algorithm.

complex number

A number of the form a + bi where a, b are real and i² = -1; the set ℂ.

See: Complex numbers & phasors

composite

An integer greater than 1 that has at least one positive divisor other than 1 and itself.

congruence mod n

The relation a ≡ b (mod n), holding when n divides a - b; partitions ℤ into n equivalence classes.

congruent modulo n

Two integers a and b are congruent modulo n when n divides their difference: n | (a - b).

coprime

Two integers a, b are coprime when gcd(a, b) = 1; they share no common prime factors.

divisor

An integer d that divides another integer n exactly, leaving no remainder; we write d | n.

See: Greatest Common Divisors

euclid's lemma

If a prime p divides a product ab, then p divides a or p divides b; the key step in proving unique factorization.

euclid’s lemma

If a prime p divides a product ab, then p divides a or p divides b; the key step in proving unique factorization.

euler totient

φ(n), the count of integers in {1, ..., n} coprime to n; φ is the foundation of Euler's theorem and RSA correctness.

factor

An integer that divides another integer exactly; also: to rewrite an expression as a product of simpler ones.

See: The Formation Factor, The Photoelectric Factor

gcd

Greatest common divisor: the largest positive integer that divides each of the given integers.

greatest common divisor

gcd(a, b) is the largest positive integer dividing both a and b; computed efficiently by the Euclidean algorithm.

See: Greatest Common Divisors

imaginary unit

The number i, defined by i² = -1; it generates the imaginary axis of the complex plane.

integer

A whole number, positive, negative, or zero; the set ℤ = {..., -2, -1, 0, 1, 2, ...}.

See: The Integers, Even and Odd Integers; Divisibility

integers

The set ℤ = {..., -2, -1, 0, 1, 2, ...}; closed under addition, subtraction, and multiplication.

See: The Integers, Even and Odd Integers; Divisibility

irrational number

A real number that cannot be written as a ratio of two integers, such as √2 or π.

lcm

Least common multiple: the smallest positive integer that is a multiple of each of the given integers.

least common multiple

lcm(a, b) is the smallest positive integer divisible by both a and b; satisfies lcm(a, b) · gcd(a, b) = |ab|.

modular inverse

For a, n with gcd(a, n) = 1, the unique b ∈ {1, ..., n-1} satisfying ab ≡ 1 (mod n).

multiple

An integer obtained by multiplying another integer by some integer; 12 is a multiple of 3.

See: Multiples, Multiple classification

natural number

A positive whole number; the set ℕ = {1, 2, 3, ...}. Some texts include 0.

natural numbers

The set ℕ = {0, 1, 2, ...} or {1, 2, 3, ...} depending on convention; the counting numbers.

parity

Whether an integer is even or odd; preserved or flipped by certain operations.

prime

An integer greater than 1 whose only positive divisors are 1 and itself.

rational number

A number expressible as a ratio a/b of two integers with b ≠ 0; the set ℚ.

See: Rational Numbers

rational numbers

The set ℚ of fractions a/b with a, b ∈ ℤ and b ≠ 0; dense in ℝ but countable.

See: Rational Numbers

real number

Any number on the number line; the set ℝ, which contains both the rationals and irrationals.

See: Real Numbers: Positivity, Addition and Multiplication of Real Numbers

real numbers

The set ℝ of all numbers on the number line, rationals together with irrationals.

See: Real Numbers: Positivity, Addition and Multiplication of Real Numbers

rivest, shamir, adleman

The three cryptographers who published the RSA public-key cryptosystem in 1978 (CACM 21(2)).

units

In modular arithmetic mod n, the integers coprime to n; the units form a group (ℤ/nℤ)* under multiplication.