Math Reference
Search integers, primes, modular arithmetic, cyclic-group generators, quadratic residues, Diophantine equations, and RSA with formulas and worked examples.
Successive powers of 3 visit every nonzero residue before returning to 1.
Squaring the nonzero residues produces only 1, 2, and 4.
55 matching terms
Integers and foundations
Integer
ℤA whole number that can be negative, zero, or positive.
Use integers for counts with direction, indexes, differences, and exact discrete calculations.
-4, 0, and 27 are integers.Integers and foundations
Natural number
ℕA counting number; whether zero is included depends on the convention being used.
State the convention before using natural numbers in a proof, specification, or program.
Some books define natural numbers as starting at 1, so always check the convention.
This guide uses ℕ = {0, 1, 2, 3, ...}.Integers and foundations
Absolute value
|a|The nonnegative distance from an integer to zero on the number line.
Use it to express magnitude, distance, error, and symmetric bounds.
|-7| = 7 and |5 - 12| = 7.Integers and foundations
Parity
n mod 2The property of an integer being even or odd.
Use parity for branching, alternating patterns, proofs, checksums, and bit-level logic.
18 mod 2 = 0, so 18 is even.Integers and foundations
Division algorithm
a = bq + rFor integers a and positive b, there are unique integers q and r with 0 ≤ r < b.
Use it as the foundation of quotient, remainder, Euclidean algorithms, and modular arithmetic.
29 = 6 × 4 + 5, so q = 4 and r = 5.Divisibility
Divisor
d | nAn integer d is a divisor of n when n = dk for some integer k.
Use divisors to analyze factor structure, common factors, and exact divisibility.
6 | 42 because 42 = 6 × 7.Divisibility
Multiple
n = dkA number obtained by multiplying an integer by another integer.
Use multiples for schedules, common periods, cyclic systems, and denominator alignment.
Multiples of 5 include 0, 5, 10, 15, and 20.Divisibility
Divisibility test
n mod d = 0A rule that determines whether one integer divides another without completing long division.
Use it for quick checks, mental arithmetic, input validation, and teaching place-value structure.
7,452 is divisible by 3 because 7 + 4 + 5 + 2 = 18.Divisibility
Greatest common divisor
gcd(a, b)The largest positive integer that divides both integers exactly.
Use it to reduce fractions, test coprimality, solve congruences, and calculate ratios.
gcd(84, 30) = 6.Divisibility
Least common multiple
lcm(a, b)The smallest positive integer that is a multiple of both nonzero integers.
Use it to synchronize cycles, combine fractions, and calculate repeating schedules.
lcm(12, 18) = 36.Divisibility
GCD-LCM identity
gcd(a,b)lcm(a,b)=|ab|A relationship connecting the greatest common divisor and least common multiple of two nonzero integers.
Use it to calculate one quantity efficiently when the other is already known.
gcd(12,18)=6, so lcm(12,18)=|12×18|/6=36.Divisibility
Euclidean algorithm
gcd(a,b)=gcd(b,a mod b)A repeated-remainder algorithm for finding the greatest common divisor.
Use it for fast GCD calculation even when the input integers are large.
gcd(252,105) = gcd(105,42) = gcd(42,21) = 21.Divisibility
Extended Euclidean algorithm
ax + by = gcd(a,b)An extension of the Euclidean algorithm that also finds Bézout coefficients x and y.
Use it to calculate modular inverses and solve linear Diophantine equations.
35×(-1) + 12×3 = 1, so -1 is a coefficient for 35.Divisibility
Coprime integers
gcd(a,b)=1Two integers are coprime when their greatest common divisor is 1.
Use coprimality to determine invertibility modulo n and to apply Euler's theorem.
8 and 15 are coprime even though neither number is prime.Primes and factorization
Prime number
pAn integer greater than 1 whose only positive divisors are 1 and itself.
Use primes as the basic building blocks of integer factorization and public-key cryptography.
2, 3, 5, 7, and 11 are prime numbers.Primes and factorization
Composite number
n = abAn integer greater than 1 that has a positive divisor other than 1 and itself.
Use it to distinguish factorable integers from primes.
21 is composite because 21 = 3 × 7.Primes and factorization
Prime factorization
n=∏pᵢ^aᵢWriting an integer as a product of powers of prime numbers.
Use it to compute divisors, GCDs, LCMs, and arithmetic functions.
360 = 2^3 × 3^2 × 5.Primes and factorization
Fundamental theorem of arithmetic
n=∏pᵢ^aᵢEvery integer greater than 1 has a prime factorization that is unique up to factor order.
Use it to justify algorithms and proofs based on prime exponents.
72 = 2^3 × 3^2 is the unique prime factorization of 72.Primes and factorization
Sieve of Eratosthenes
An algorithm that lists primes up to a limit by repeatedly marking multiples of each discovered prime.
Use it when many prime queries share the same moderate upper bound.
To find primes through 30, mark multiples of 2, 3, and 5.Primes and factorization
Primality test
An algorithm that decides whether a given integer is prime.
Use trial division for small inputs and probabilistic tests such as Miller-Rabin for large inputs.
A probable-prime test can require multiple rounds or a deterministic base set for the intended integer range.
Trial division only needs candidate divisors up to √n.Modular arithmetic
Congruence
a ≡ b (mod n)Two integers are congruent modulo n when n divides their difference.
Use it to replace integers with equivalent residues in cyclic calculations.
29 ≡ 5 (mod 12) because 12 divides 29 - 5.Modular arithmetic
Residue class
[a]ₙThe set of all integers congruent to a fixed integer modulo n.
Use it to reason about modular values as equivalence classes rather than isolated numbers.
[2]₅ = {..., -8, -3, 2, 7, 12, ...}.Modular arithmetic
Modulo operation
a mod nAn operation that returns a representative remainder after division by n.
Use it for wrapping indexes, clocks, hash buckets, and periodic states.
(23 + 5) mod 24 = 4.Modular arithmetic
Modular arithmetic
ℤ/nℤArithmetic performed on residue classes with results reduced modulo n.
Use it in cryptography, coding theory, cyclic buffers, and calendar calculations.
(17 × 19) mod 12 = 11.Modular arithmetic
Modular inverse
a⁻¹ mod nA value x satisfying ax ≡ 1 (mod n); it exists exactly when gcd(a,n)=1.
Use it to divide in modular arithmetic, solve congruences, and implement cryptographic algorithms.
Do not attempt modular division before checking that the divisor is coprime to the modulus.
3⁻¹ mod 7 = 5 because 3 × 5 ≡ 1 (mod 7).Modular arithmetic
Modular exponentiation
a^k mod nComputing a power modulo n without first constructing the potentially enormous full power.
Use repeated squaring in cryptography, primality tests, and large-exponent problems.
3^13 mod 7 = 3 using repeated squaring.Modular arithmetic
Linear congruence
ax ≡ b (mod n)A congruence that asks for integers x satisfying a linear modular equation.
Use GCD conditions and modular inverses to determine and calculate solutions.
3x ≡ 4 (mod 7) gives x ≡ 6 (mod 7).Modular arithmetic
Chinese remainder theorem
x ≡ aᵢ (mod nᵢ)A theorem that combines compatible congruences, giving a unique solution modulo the product when moduli are pairwise coprime.
Use it to combine independent cyclic constraints and accelerate large-integer computation.
x ≡ 2 (mod 3), x ≡ 3 (mod 5) gives x ≡ 8 (mod 15).Modular arithmetic
Euler's totient function
φ(n)The number of integers from 1 through n that are coprime to n.
Use it in Euler's theorem, RSA key calculations, and reduced residue systems.
φ(12) = 4 because 1, 5, 7, and 11 are coprime to 12.Modular arithmetic
Euler's theorem
a^φ(n) ≡ 1 (mod n)If a and n are coprime, raising a to φ(n) gives 1 modulo n.
Use it to reduce exponents, prove modular identities, and explain RSA.
gcd(3,10)=1 and φ(10)=4, so 3^4 ≡ 1 (mod 10).Modular arithmetic
Fermat's little theorem
a^(p-1) ≡ 1 (mod p)For prime p and a not divisible by p, a raised to p-1 is congruent to 1 modulo p.
Use it for modular inverses under a prime modulus and for primality screening.
Passing a Fermat test does not prove that a number is prime because pseudoprimes exist.
2^6 ≡ 1 (mod 7).Cyclic groups and generators
Group
(G, *)A set with an associative operation, an identity element, and an inverse for every element.
Use groups to describe arithmetic structures in which operations can be composed and reversed.
The integers form a group under addition with identity 0 and inverse -a for a.Cyclic groups and generators
Abelian group
a*b=b*aA group whose operation is commutative.
Use it for modular addition, vector addition, and many arithmetic groups where operation order does not matter.
(ℤ/nℤ, +) is an Abelian group.Cyclic groups and generators
Additive group modulo n
(ℤ/nℤ, +)The residue classes modulo n with addition performed modulo n.
Use it to model cyclic counters, periodic states, and congruence classes under addition.
In ℤ/5ℤ, 3+4=2.Cyclic groups and generators
Multiplicative group of units
(ℤ/nℤ)×The residue classes coprime to n, with multiplication modulo n.
Use it to study modular inverses, primitive roots, Euler's theorem, and public-key cryptography.
(ℤ/8ℤ)×={1,3,5,7}.Cyclic groups and generators
Cyclic group
G=⟨g⟩A group whose every element is a power or repeated sum of one element.
Use it to reduce a group operation to arithmetic on exponents or integer multiples.
The additive group ℤ/6ℤ is generated by 1 and by 5.Cyclic groups and generators
Generator
⟨g⟩=GAn element whose repeated group operation produces every element of a cyclic group.
Use it to enumerate cyclic groups and define exponent-based cryptographic operations.
Always state the group and operation because an element can generate one structure but not another.
Powers of 3 modulo 7 produce 3,2,6,4,5,1, so 3 generates (ℤ/7ℤ)×.Cyclic groups and generators
Order of an element
ord(g)The smallest positive integer k for which g^k is the identity element.
Use it to test whether an element is a generator and to determine cycle length.
Modulo 7, ord(2)=3 because 2^3≡1 and no smaller positive exponent works.Cyclic groups and generators
Primitive root
ordₙ(g)=φ(n)A generator of the multiplicative group of units modulo n.
Use primitive roots to represent nonzero residues as powers and to formulate discrete logarithms.
3 is a primitive root modulo 7 because its order is φ(7)=6.Cyclic groups and generators
Primitive root existence
Primitive roots modulo n exist exactly for n=1, 2, 4, p^k, or 2p^k where p is an odd prime.
Use the criterion before searching for a primitive root modulo a composite number.
There is no primitive root modulo 8 because 8 has none of the required forms.Cyclic groups and generators
Discrete logarithm
g^x=hGiven a generator g and group element h, the discrete logarithm asks for an exponent x satisfying g^x=h.
Use it to understand Diffie-Hellman, ElGamal, and elliptic-curve security assumptions.
The discrete logarithm can be easy in small or poorly chosen groups and hard only under appropriate parameters.
Modulo 7 with generator 3, log₃(5)=5 because 3^5≡5.Cyclic groups and generators
Carmichael function
λ(n)The smallest positive exponent m such that a^m≡1 modulo n for every a coprime to n.
Use it to obtain a tighter universal exponent than φ(n) for modular powers and RSA analysis.
λ(8)=2 because every odd a satisfies a²≡1 (mod 8).Quadratic residues
Quadratic residue
x²≡a (mod n)A residue a for which the congruence x²≡a modulo n has a solution.
Use it to analyze modular square roots, primality tests, and quadratic-residue cryptography.
2 is a quadratic residue modulo 7 because 3²≡2.Quadratic residues
Quadratic nonresidue
A nonzero residue for which x²≡a modulo n has no solution.
Use it to classify residues and construct tests or cryptographic parameters with known quadratic character.
3 is a quadratic nonresidue modulo 7.Quadratic residues
Modular square root
x=√a mod nA solution x to x²≡a modulo n.
Use it in point decompression, number-theoretic algorithms, and residue-based cryptography.
The square roots of 2 modulo 7 are 3 and 4.Quadratic residues
Legendre symbol
(a/p)For an odd prime p, a value 0, 1, or -1 indicating divisibility by p or quadratic-residue status modulo p.
Use it to test quadratic character and state Euler's criterion and quadratic reciprocity compactly.
(2/7)=1 because 2 is a quadratic residue modulo 7.Quadratic residues
Jacobi symbol
(a/n)A multiplicative extension of the Legendre symbol to positive odd composite denominators.
Use it for efficient character calculations and algorithms that do not require factoring n first.
A Jacobi symbol of 1 does not guarantee that a is a quadratic residue modulo composite n.
(5/21)=(5/3)(5/7)=1.Quadratic residues
Euler's criterion
a^((p-1)/2)≡(a/p) (mod p)A criterion that determines quadratic-residue status modulo an odd prime using modular exponentiation.
Use it to calculate the Legendre symbol without listing every square.
For p=7, 3^3≡-1 (mod 7), so 3 is a quadratic nonresidue.Quadratic residues
Quadratic reciprocity
(p/q)(q/p)=(-1)^((p-1)(q-1)/4)A theorem relating whether one odd prime is a quadratic residue modulo another.
Use it to reduce large Legendre-symbol calculations to smaller ones.
Because 3 and 11 are both 3 modulo 4, (3/11)=-(11/3).Quadratic residues
Supplementary laws
(-1/p), (2/p)Formulas that determine the quadratic character of -1 and 2 modulo an odd prime.
Use them with quadratic reciprocity to complete Legendre-symbol calculations.
(2/p)=1 when p≡1 or 7 (mod 8), and -1 when p≡3 or 5 (mod 8).Quadratic residues
Tonelli-Shanks algorithm
An algorithm for finding a modular square root of a quadratic residue modulo an odd prime.
Use it when the modulus is prime and the simple p≡3 modulo 4 shortcut does not apply.
For p=13, Tonelli-Shanks finds x=6 or 7 for x²≡10 (mod 13).Quadratic residues
Square roots modulo a composite
Modular square roots found modulo prime-power factors and combined with the Chinese remainder theorem.
Use it to analyze Rabin-type systems and congruences with composite moduli.
For a product of distinct odd primes, one residue can have multiple square roots, so selecting the intended root requires extra information.
Solve x²≡1 modulo 3 and 5, then combine the sign choices modulo 15.Integer equations
Diophantine equation
An equation for which only integer solutions are sought.
Use divisibility, GCD, congruences, and bounds to determine whether integer solutions exist.
3x + 5y = 17 has the integer solution x = 4, y = 1.Integer equations
Linear Diophantine equation
ax + by = cA linear equation whose unknowns must be integers; solutions exist exactly when gcd(a,b) divides c.
Use it for exact allocation, coin problems, schedules, and lattice constraints.
6x + 9y = 30 is solvable because gcd(6,9)=3 divides 30.Applications
RSA arithmetic
c ≡ m^e (mod n)Public-key arithmetic based on modular exponentiation and the difficulty of factoring a product of large primes.
Use it to understand how number theory supports encryption and digital signatures.
Toy values are for learning only; real RSA requires standardized padding, secure key sizes, and audited libraries.
With toy values n=55, e=3, and m=7, c=7^3 mod 55=13.