Latest

A Carmichael number is a composite number $n$ that satisfies $a^{n-1} \equiv 1 \pmod n$ for each integer $a$ coprime to $n$. The definition of a Carmichael number gives the precise form.

A tree is a connected graph with no cycles. Trees are the minimal connected graphs, and they appear in data structures, in spanning problems and in counting problems. The node tree gives the precise definition.

A Fermat prime is a prime number of the form $2^{2^n} + 1$. The definition of a Fermat prime gives the precise form.

The sum of divisors $\sigma(n)$ of a positive integer $n$ is the sum of all its positive divisors. The definition of the sum of divisors gives the precise form.

A Gaussian integer is a complex number $a + bi$ with integers $a$ and $b$. The Gaussian integers form the ring $\mathbb{Z}[i]$. The definition of a Gaussian integer gives the precise form.

The Liouville function $\lambda(n)$ is $1$ or $-1$, by the parity of the number of prime factors of $n$ counted with multiplicity. The definition of the Liouville function gives the precise form.

The function $\omega(n)$ counts the distinct prime numbers that divide a positive integer $n$. The definition of the number of distinct prime factors gives the precise form.

A circuit is a closed trail in a graph: a round trip that uses each edge at most once. Eulerian circuits are the main example. The node circuit gives the precise definition.

A binary tree is a recursive structure. It is empty, or it is a root with an ordered pair of binary trees as left and right subtrees. Binary trees are a basic data structure, and they are counted by the Catalan numbers. The node binary tree gives the precise definition.

Euler's totient function $\varphi$ gives, for each positive integer $n$, the number of integers from $1$ to $n$ that are coprime to $n$. The definition of Euler's totient function gives the precise form.

A primitive $n$th root of unity is an $n$th root of unity that is not a $k$th root of unity for a smaller positive $k$. Its powers give all the $n$th roots of unity.

An induced subgraph is the subgraph on a chosen set of vertices that keeps all edges between them. Induced subgraphs describe the structure of a graph on a part of its vertex set. The node induced subgraph gives the precise definition.

A Mersenne prime is a prime number of the form $2^n - 1$. The definition of a Mersenne prime gives the precise form.

A quadratic integer is a root of a monic quadratic polynomial with integer coefficients, that is, an algebraic integer of degree at most $2$. The definition of a quadratic integer gives the precise form.

A graph isomorphism is a bijection between the vertices of two graphs that preserves and reflects adjacency. Isomorphic graphs have the same structure and differ only in the names of their vertices. The node graph isomorphism gives the precise definition.

The Möbius function $\mu$ is an arithmetic function that is $0$ on integers with a square factor greater than $1$. On a squarefree integer, its value $1$ or $-1$ depends on the parity of the number of prime factors. The definition of the Möbius function gives the precise form.

The binomial coefficient $\binom{n}{k}$ is the number of ways to choose $k$ elements from an $n$-element set. These numbers are the coefficients in the expansion of $(x + y)^n$. The node binomial coefficient gives the precise definition.

The Cayley graph of a group $G$ with a generating set $S$ has the elements of $G$ as vertices. It has an edge from $g$ to $g s$ for each $g \in G$ and $s \in S$. It encodes the structure of the group as a graph.

A Hamiltonian cycle is a cycle that passes through every vertex of a graph. The search for such cycles is a classical hard problem, related to the travelling salesman problem. The node Hamiltonian cycle gives the precise definition.

A Hamiltonian graph is a graph that has a cycle through all of its vertices. There is no simple test for this property, but degree conditions give sufficient criteria. The node Hamiltonian graph gives the precise definition.

An exponential generating function encodes a sequence $(a_n)$ as the series $\sum a_n x^n / n!$. It is the natural tool to count labelled structures, because products give binomial convolutions. The node exponential generating function gives the precise definition.

The central binomial coefficients $\binom{2n}{n}$ are the middle entries of the even rows of Pascal's triangle. They count balanced lattice paths and appear in the formula for Catalan numbers. The node central binomial coefficient gives the precise definition.

The Legendre symbol $\left(\frac{a}{p}\right)$ takes the value $1$, $-1$ or $0$, and it tells whether $a$ is a square modulo an odd prime $p$. The definition of the Legendre symbol gives the precise form.

A minimum spanning tree of a weighted connected graph is a spanning tree of least total weight. It is a classical problem of combinatorial optimization, solved by greedy algorithms. The node minimum spanning tree gives the precise definition.

A connected graph is a graph in one piece, in which any two vertices are joined by a walk. Connectivity is a basic hypothesis of many results, such as the existence of spanning trees. The node connected graph gives the precise definition.

The function $\Omega(n)$ counts the prime factors of a positive integer $n$, with each prime counted as often as it divides $n$. The definition of the number of prime factors with multiplicity gives the precise form.

The Fermat primality test is a probabilistic test of whether an integer $n > 1$ is prime. It chooses a base $a$ with $1 < a < n - 1$ and computes $a^{n-1} \bmod n$ by modular exponentiation. If the result is not $1$, then $n$ is composite, by Fermat's little theorem. If the result is $1$, then $n$ is called a probable prime to the base $a$.

A planar graph is a graph that can be drawn in the plane with no crossing edges. Planar graphs are the subject of Euler's formula and of the four colour theorem. The node planar graph gives the precise definition.

A perfect matching is a matching that covers every vertex of a graph. The theorems of Hall and Tutte say when a graph has one. The node perfect matching gives the precise definition.

The von Mangoldt function $\Lambda$ takes the value $\log p$ at each power of a prime $p$, and $0$ at all other positive integers. The definition of the von Mangoldt function gives the precise form.

A multiplicative function is an arithmetic function with $f(1) = 1$ that takes products of coprime integers to products of values. The definition of a multiplicative function gives the precise form.

A Liouville number is a real number that has rational approximations $p/q$ with error smaller than $1/q^n$ for each $n$. The definition of a Liouville number gives the precise form.

A regular graph is a graph in which all vertices have the same degree. Regular graphs are a basic family with strong symmetry and counting properties. The node regular graph gives the precise definition.

A linear Diophantine equation in two unknowns is an equation $a x + b y = c$ with given integers $a$, $b$ and $c$. Its solutions are the pairs of integers $(x, y)$ that satisfy it. When $a$ and $b$ are not both $0$, the equation has an integer solution if and only if $\gcd(a, b)$ divides $c$. In this case, let $d = \gcd(a, b)$ and let $(x_0, y_0)$ be one solution. Then the solutions are the pairs $(x_0 + k b / d, \; y_0 - k a / d)$ with $k$ an integer.

A Gaussian prime is a prime element of the ring of Gaussian integers. The definition of a Gaussian prime gives the precise form.

A completely multiplicative function is an arithmetic function with $f(1) = 1$ and $f(mn) = f(m) f(n)$ for all positive integers $m$ and $n$. The definition of a completely multiplicative function gives the precise form.

A spanning tree of a graph is a tree inside the graph that reaches every vertex. Spanning trees are the minimal connected spanning subgraphs, with uses in network design and in counting. The node spanning tree gives the precise definition.

The Miller–Rabin test is a probabilistic primality test for an odd integer $n > 2$. Write $n - 1 = 2^s d$ with $d$ odd, and choose a base $a$ with $1 < a < n - 1$. The number $n$ passes for base $a$ if $a^d \equiv 1 \pmod n$, or if $a^{2^r d} \equiv -1 \pmod n$ for some $r$ with $0 \le r < s$. Each odd prime $n$ passes for each base. If $n$ fails for some base, then $n$ is composite.

The number of divisors $d(n)$ of a positive integer $n$ is the count of its positive divisors. The definition of the number of divisors gives the precise form.

A trail is a walk in a graph that uses each edge at most once. Trails are the setting of Eulerian problems. The node trail gives the precise definition.