Number Theory and Modular Arithmetic: every key term you need (+ practice quiz)
25 flashcard terms for Discrete Mathematics Topic 6, written to match the course framework. Study them here, then drill them as interactive flashcards, or test yourself with the 15-question quiz — free, no account needed.
An integer divides another when the second is an exact integer multiple of the first. Every integer divides zero, while only the units divide one, and the relation is transitive.
Division algorithm
The result that dividing any integer by a positive integer yields a unique quotient and a remainder lying between zero and one less than the divisor. Uniqueness is what makes remainders well defined.
Prime number
An integer greater than one whose only positive divisors are one and itself. Two is the only even prime, and one is deliberately excluded so factorisation stays unique.
Composite number
An integer greater than one that has a divisor other than one and itself. Every composite has a prime factor no larger than its square root, which bounds trial division.
Fundamental theorem of arithmetic
Every integer greater than one factors into primes in exactly one way apart from the order of the factors. Both existence and uniqueness require proof and uniqueness is the harder half.
Infinitude of primes
Euclid's argument that no finite list of primes is complete: multiplying the list and adding one produces a number whose prime factors are all missing from the list.
Sieve of Eratosthenes
An algorithm listing primes up to a bound by repeatedly striking out multiples of each newly found prime, needing only primes up to the square root of the bound.
Greatest common divisor
The largest integer dividing two given integers. It can be read off matched prime factorisations, but for large numbers it is far faster to compute by repeated division.
Least common multiple
The smallest positive integer that both given integers divide. For positive integers it equals their product divided by their greatest common divisor.
Relatively prime integers
Two integers whose greatest common divisor is one. They share no prime factor, and this coprimality is exactly the condition for an inverse to exist modulo one of them.
Euclid's algorithm
A method for the greatest common divisor that repeatedly replaces the larger number by its remainder on division by the smaller, stopping when the remainder reaches zero.
Extended Euclid's algorithm
A version that also returns integer coefficients expressing the greatest common divisor as a combination of the two inputs, which is how modular inverses are actually computed.
Bezout identity
The statement that the greatest common divisor of two integers can always be written as an integer combination of them, and that it is the smallest positive value so expressible.
Congruence modulo n
Two integers are congruent modulo n when n divides their difference, equivalently when they leave the same remainder. This is an equivalence relation whose classes are the residue classes.
Residue class
The set of all integers congruent to a fixed value modulo n. The n residue classes partition the integers, and arithmetic on them is well defined.
Modular addition and multiplication
Congruences may be added, subtracted and multiplied term by term, which is why one may reduce intermediate results at any point without changing the final residue.
Modular cancellation
Dividing both sides of a congruence by a common factor is only valid when that factor is relatively prime to the modulus; otherwise the modulus must be divided too.
Modular inverse
A value whose product with a given residue is one modulo n. It exists exactly when the residue and modulus are relatively prime, and it is found by extended Euclid.
Linear congruence
An equation of the form a times x congruent to b modulo n. It is solvable exactly when the greatest common divisor of a and n divides b, and then it has that many solutions.
Chinese remainder theorem
A guarantee that a system of congruences with pairwise relatively prime moduli has a solution unique modulo the product of the moduli, which the extended algorithm constructs.
Fermat little theorem
For a prime modulus and a base not divisible by that prime, raising the base to the prime minus one gives one. It is the basis of fast primality screening.
Euler totient function
The count of positive integers up to n that are relatively prime to n. It is multiplicative across coprime factors and equals n minus one exactly when n is prime.
Euler theorem
A generalisation of the little theorem: for a base relatively prime to the modulus, raising it to the totient of the modulus yields one, which controls exponents in modular arithmetic.
Fast modular exponentiation
Computing a large power modulo n by repeated squaring and reducing at every step, which turns a hopeless computation into one taking about as many steps as the exponent has bits.
RSA key idea
A public key scheme resting on the difficulty of factoring a product of two large primes, where encryption and decryption exponents are inverses modulo the totient.