Number Theory Cheat Sheet

The core ideas of Number Theory distilled into a single, scannable reference — perfect for review or quick lookup.

PiqCue — piqcue.com/number-theory/cheatsheet

Quick Reference

Prime Numbers

Natural numbers greater than 1 that have no positive divisors other than 1 and themselves. Primes are the fundamental building blocks of all integers through the Fundamental Theorem of Arithmetic.

Fundamental Theorem of Arithmetic

Every integer greater than 1 can be represented uniquely as a product of prime numbers, up to the order of the factors. This guarantees a single canonical prime factorization for every positive integer.

Modular Arithmetic

A system of arithmetic for integers in which numbers 'wrap around' upon reaching a certain value called the modulus. Two integers are congruent modulo $n$ if their difference is divisible by $n$.

Euclidean Algorithm

An efficient method for computing the greatest common divisor (GCD) of two integers by repeatedly applying the division algorithm. It is one of the oldest known algorithms still in widespread use.

Fermat's Little Theorem

If $p$ is a prime and $a$ is an integer not divisible by $p$, then $a^{p-1} \equiv 1 \pmod{p}$. This result underpins many primality tests and cryptographic protocols.

Euler's Totient Function

The function $\varphi(n)$ counts the number of integers from 1 to $n$ that are coprime to $n$. It generalizes Fermat's Little Theorem and is central to the RSA cryptosystem.

Diophantine Equations

Polynomial equations where only integer (or sometimes rational) solutions are sought. Named after Diophantus of Alexandria, they include famous problems such as Fermat's Last Theorem.

Chinese Remainder Theorem

A result stating that if one knows the remainders of an integer when divided by several pairwise coprime moduli, one can determine the remainder when divided by the product of those moduli uniquely.

Quadratic Reciprocity

A fundamental theorem describing the relationship between the solvability of two related quadratic equations modulo different primes. Gauss called it the 'golden theorem' and provided multiple proofs.

RSA Cryptosystem

A public-key encryption scheme whose security relies on the practical difficulty of factoring the product of two large prime numbers. It uses Euler's totient function to construct encryption and decryption keys.

Key Terms at a Glance

Prime Number:A natural number greater than 1 that has no positive divisors other than 1 and itself.

Composite Number:A positive integer greater than 1 that is not prime, meaning it has at least one positive divisor other than 1 and itself.

Greatest Common Divisor (GCD):The largest positive integer that divides each of two or more integers without a remainder.

Least Common Multiple (LCM):The smallest positive integer that is a multiple of each of two or more integers.

Congruence:A relation between two integers indicating they have the same remainder when divided by a given modulus. Written $a \equiv b \pmod{n}$.

Modulus:The divisor in modular arithmetic that determines the point at which integers 'wrap around.'

Coprime:Two integers whose greatest common divisor is 1, also called relatively prime.

Arithmetic Function:A function defined on positive integers that takes real or complex values, often encoding number-theoretic information. Examples include $\varphi(n)$ and $\mu(n)$.

Multiplicative Function:An arithmetic function $f$ such that $f(mn) = f(m)f(n)$ whenever $\gcd(m, n) = 1$.

Quadratic Residue:An integer $a$ is a quadratic residue modulo $n$ if the equation $x^2 \equiv a \pmod{n}$ has a solution.

Dirichlet Series:An infinite series of the form $\sum a_n / n^s$, used extensively in analytic number theory to study the distribution of primes.

Euler Product:A representation of a Dirichlet series as a product over prime numbers, reflecting the multiplicative structure of the integers.

Algebraic Integer:A complex number that is a root of a monic polynomial with integer coefficients. Generalizes ordinary integers to number fields.

Ideal:A special subset of a ring that generalizes the concept of divisibility and restores a form of unique factorization in algebraic number theory.

Primality Test:An algorithm that determines whether a given number is prime. Examples include the Miller-Rabin test and the AKS test.

Get study tips in your inbox

We'll send you evidence-based study strategies and new cheat sheets as they're published.

We'll notify you about updates. No spam, unsubscribe anytime.