Search & glossary

Every rule and concept in Number Theory, with its definition and a link to the lesson that teaches it. Search by term, by idea, or by lesson title.

Glossary (37)

$(p - 1)! \equiv -1$: Wilson: for a prime $p$ , $(p - 1)!; Fermat, Euler and Wilson › Wilson's Theorem
$\gcd\cdot\text{lcm} = ab$: The least common multiple $\text{lcm}(a, b)$ is the smallest positive integer divisible by both.; GCD, LCM and the Euclidean Algorithm › LCM and the Product Formula
$a^{p-1} \equiv 1$: If $p$ is prime and $p \nmid a$ , then $a^{p-1} \equiv 1 \pmod p$ ; equivalently $a^p \equiv a$ for every $a$ .; Fermat, Euler and Wilson › Fermat's Little Theorem
$ax + by = c$: The equation $ax + by = c$ has integer solutions iff $\gcd(a, b) \mid c$ .; Diophantine Equations › Linear Diophantine Equations
A generator: A primitive root mod $m$ is an element of order exactly $\varphi(m)$ .; Orders and Primitive Roots › Primitive Roots
Cancellation: If $ac \equiv bc \pmod m$ and $\gcd(c, m) = 1$ , then $a \equiv b \pmod m$ .; Modular Arithmetic › Inverses and Linear Congruences
Carry at $b$: Addition and multiplication work column by column in any base, exactly as in base ten, except that a column carries when it reaches $b$ instead of $10$ .; Digits and Bases › Arithmetic in Other Bases
Check every class: To prove a statement about all integers $n$ whose truth depends only on $n \bmod m$ , check the $m$ residues $0, 1, \ldots, m - 1$ .; Modular Arithmetic › Proofs by Residue Classes
Consistency first: If the moduli share factors, the system $x \equiv a_1 \pmod{m_1}$ , $x \equiv a_2 \pmod{m_2}$ has a solution iff $a_1 \equiv a_2 \pmod{\gcd(m_1, m_2)}$ , and the solution is then unique mod $\text{lcm}(m_1, m_2)$ — not mod $m_1m_2$ .; The Chinese Remainder Theorem › Moduli That Share a Factor
Count the dots two ways: A sum of floors counts lattice points: $\lfloor qk/p \rfloor$ is the number of points $(k, j)$ with $1 \le j \le qk/p$ , the points on or under the line $y = qx/p$ above $x = k$ .; Hard Number Theory › Floor Sums and Lattice Points
Definition and infinitude: A prime is an integer $p > 1$ whose only positive divisors are $1$ and $p$ ; an integer $n > 1$ that is not prime is composite.; Primes and Factorization › Primes
Digit sums and $9$: A number and its digit sum are congruent mod $9$ .; Digits and Bases › Digit Problems
Digit tests: A number is divisible by $2, 5, 10$ according to its last digit; by $4$ or $25$ according to its last two digits; by $8$ by its last three.; Divisibility › Divisibility Rules
Digits as unknowns: A two-digit number with digits $a, b$ is $10a + b$ ; reversing gives $10b + a$ ; their difference is $9(a - b)$ .; Digits and Bases › Digit Problems
Divides, quotient, remainder: We write $a \mid b$ (" $a$ divides $b$ ") when $b = ak$ for some integer $k$ .; Divisibility › The Division Algorithm
Euler's totient: $\varphi(m)$ counts the integers in $1, \ldots, m$ coprime to $m$ .; Fermat, Euler and Wilson › Euler's Theorem and $\varphi$
Every integer, every base: For any base $b \ge 2$ , every positive integer has a unique representation $n = d_kb^k + \cdots + d_1b + d_0$ with digits $0 \le d_i < b$ , written $\overline{d_k\cdots d_1d_0}_b$ .; Digits and Bases › Base $b$ Representation
Independent moduli combine: If $m_1, \ldots, m_k$ are pairwise coprime, the system $x \equiv a_i \pmod{m_i}$ has exactly one solution mod $M = m_1\cdots m_k$ .; The Chinese Remainder Theorem › CRT
Legendre's formula: The exponent of a prime $p$ in $n!$ is $\left\lfloor\dfrac np\right\rfloor + \left\lfloor\dfrac n{p^2}\right\rfloor + \left\lfloor\dfrac n{p^3}\right\rfloor + \cdots$ , a sum that stops once $p^k > n$ .; Primes and Factorization › Factorials and Legendre's Formula
Let the equation pick the modulus: A modulus is useful when the terms of the equation take few values in it.; Hard Number Theory › Choosing a Modulus
Modular inverses: $a$ has an inverse mod $m$ (a number $a^{-1}$ with $aa^{-1} \equiv 1$ ) exactly when $\gcd(a, m) = 1$ ; find it from Bézout.; Modular Arithmetic › Inverses and Linear Congruences
Multiplicative functions: $\tau(n)$ counts the divisors of $n$ , $\sigma(n)$ sums them, $\varphi(n)$ counts the residues coprime to $n$ .; Arithmetic Functions › $\tau$ , $\sigma$ and $\varphi$
No solution mod $m$ , no solution at all: If an equation has an integer solution, reducing it gives a solution modulo every $m$ .; Diophantine Equations › Congruence Obstructions
Order: For $\gcd(a, m) = 1$ , the order of $a$ mod $m$ is the least $d > 0$ with $a^d \equiv 1$ .; Orders and Primitive Roots › The Order of an Element
Period of $1/p$: The decimal expansion of $1/p$ ( $p \ne 2, 5$ ) has period equal to the order of $10$ modulo $p$ .; Orders and Primitive Roots › The Order of an Element
Reading off structure: Questions like "which $n$ have exactly $6$ divisors?" are questions about exponent patterns: $6 = 6$ or $2\cdot3$ , so $n = p^5$ or $n = p^2q$ .; Arithmetic Functions › Divisor Problems
Repeated remainders: Since $\gcd(a, b) = \gcd(b, a \bmod b)$ , dividing repeatedly and keeping remainders reaches $\gcd(a, b)$ as the last nonzero remainder.; GCD, LCM and the Euclidean Algorithm › The Euclidean Algorithm
Simon's Favorite Factoring Trick: $xy + ax + by = c$ becomes $(x + b)(y + a) = c + ab$ : add the missing constant to complete the product, then list factor pairs.; Diophantine Equations › Factoring and Bounding
Split, solve, reassemble: To compute something mod a composite $m = m_1m_2$ with $\gcd(m_1, m_2) = 1$ , compute it mod $m_1$ and mod $m_2$ separately — often much easier, for instance by Fermat on each prime — and then combine the two remainders with CRT.; The Chinese Remainder Theorem › Computing with CRT
Squares mod $p$: For an odd prime $p$ , exactly half of the nonzero residues are squares (quadratic residues).; Orders and Primitive Roots › Quadratic Residues
Summing over $d \mid n$: Many identities sum a function over the divisors of $n$ .; Arithmetic Functions › Sums and Products over Divisors
The combination rule: If $a \mid b$ and $a \mid c$ , then $a \mid bx + cy$ for all integers $x, y$ .; Divisibility › Combining Divisibility Facts
The gcd from factorizations: The greatest common divisor $\gcd(a, b)$ is the largest integer dividing both $a$ and $b$ .; GCD, LCM and the Euclidean Algorithm › Greatest Common Divisors
The gcd is a combination: For integers $a, b$ not both zero there exist integers $x, y$ with $ax + by = \gcd(a, b)$ .; GCD, LCM and the Euclidean Algorithm › Bézout's Identity
The toolkit in one place: Hard number theory problems combine a few moves: reduce mod a well-chosen modulus to rule out solutions; factor (SFFT, difference of squares, sums of cubes); bound a variable by size or by the growth of a power; use orders to control exponents; and apply Fe…; Hard Number Theory › Strategy
Unique factorization: Every integer $n > 1$ is a product of primes, and the factorization is unique up to order: $n = p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$ .; Primes and Factorization › The Fundamental Theorem of Arithmetic
Working mod $m$: $a \equiv b \pmod m$ means $m \mid (a - b)$ : $a$ and $b$ leave the same remainder on division by $m$ .; Modular Arithmetic › Congruences