Codex Wiki
number-theory.bigb
= Number theory
{wiki}
= Dirichlet theorem on primes in arithmetic progressions
{c}
{parent=Number theory}
{wiki=Dirichlet%27s_theorem_on_arithmetic_progressions}
If $\gcd(a,m)=1$, infinitely many primes satisfy
$$
p\equiv a\pmod m.
$$
= Multiplicative arithmetic function
{parent=Number theory}
{wiki=Multiplicative_function}
An arithmetic function $f$ is multiplicative when $f(mn)=f(m)f(n)$ whenever $m$ and $n$ are coprime.
= Divisor sum
{parent=Multiplicative arithmetic function}
The divisor sum of an arithmetic function $f$ is
$$
F(n)=\sum_{d\mid n}f(d).
$$
If $f$ is multiplicative, then $F$ is multiplicative as well.
= Repeated squaring
{parent=Number theory}
{wiki=Exponentiation_by_squaring}
Repeated squaring computes $a^n$ using $O(\log n)$ multiplications by reading the binary expansion of $n$. Performing every multiplication modulo $m$ computes $a^n\bmod m$ with the same number of modular multiplications.
= Integer
{title2=$\mathbb Z$}
{parent=Number theory}
{wiki}
An integer is a whole number, positive, negative, or zero.
= Positive integer
{parent=Integer}
{wiki=Natural_number}
A positive integer is an <integer> greater than zero.
= Odd integer
{parent=Integer}
{wiki=Parity_(mathematics)}
An odd integer is not divisible by two; equivalently, it has the form $2k+1$.
= Even number
{parent=Integer}
{wiki=Parity_(mathematics)}
An integer is even when it is divisible by two.
= Odd number
{parent=Integer}
{wiki=Parity_(mathematics)}
An integer is odd when it is not divisible by two.
= Square-free integer
{parent=Integer}
{wiki=Square-free_integer}
A square-free integer is divisible by no square greater than one.
= Divisibility
{title2=$\mid$}
{parent=Number theory}
{wiki}
An <integer> $d$ divides an integer $n$, written $d\mid n$, when $n=dk$ for some integer $k$.
= Integer divisor
{parent=Divisibility}
{wiki=Divisor}
An integer divisor of $n$ is an integer that divides $n$.
= Greatest common divisor
{title2=$\gcd$}
{parent=Divisibility}
{wiki}
The greatest common divisor of integers $a$ and $b$ is the largest positive integer dividing both.
= Coprime integers
{parent=Greatest common divisor}
{wiki=Coprime_integers}
Two <integers> $a$ and $b$ are coprime when $\gcd(a,b)=1$.
= Coprime
{synonym}
= Least common multiple
{title2=$\operatorname{lcm}$}
{parent=Divisibility}
{wiki}
The least common multiple of positive integers is the smallest positive integer divisible by all of them.
= Modular congruence
{title2=$\equiv$}
{parent=Number theory}
{wiki=Modular_arithmetic}
The congruence $a\equiv b\pmod n$ means that $n$ divides $a-b$.
= Prime number
{parent=Number theory}
{wiki}
A prime number is an integer $p>1$ whose only positive divisors are $1$ and $p$.
= Prime
{synonym}
= Fermat prime
{parent=Prime number}
{c}
{wiki}
A Fermat prime is a <prime number> of the form
$$
F_k=2^{2^k}+1.
$$
For $k\geq1$, it is congruent to $1$ modulo $4$ and to $2$ modulo $3$.
= Quadratic nonresidues modulo a Fermat prime
{parent=Fermat prime}
{c}
For a Fermat prime $p=2^{2^k}+1$, the multiplicative group modulo $p$ has order $2^{2^k}$. Its $\varphi(p-1)=(p-1)/2$ primitive roots are all quadratic nonresidues; since there are also $(p-1)/2$ nonresidues, the two sets coincide.
= Fundamental theorem of arithmetic
{parent=Prime number}
{c}
{wiki}
Every integer greater than one is a product of prime numbers, uniquely up to reordering the factors.
= Prime factorization
{synonym}
= Unique prime factorization
{synonym}
= Prime power
{parent=Prime number}
{wiki=Prime_power}
A prime power is a positive integer of the form $p^d$, where $p$ is a <prime number> and $d$ is a nonnegative integer.
= Prime powers
{synonym}
= Composite number
{parent=Number theory}
{wiki}
A composite number is an <integer> greater than one that is not a <prime number>.
= Fermat-Euler theorem
{parent=Number theory}
{c}
{wiki=Euler%27s_theorem}
If $\gcd(a,n)=1$, then $a^{\phi(n)}\equiv1\pmod n$. For prime $n=p$, this yields Fermat's little theorem.
= Generalized repunit pseudoprime construction
{parent=Fermat-Euler theorem}
For fixed $a>1$ and suitable odd primes $p$, the composite generalized repunit
$$
\frac{a^{2p}-1}{a^2-1}
$$
is congruent to one modulo $2p$ and is a pseudoprime to base $a$.
= Fermat pseudoprime
{parent=Number theory}
{c}
{wiki}
An odd composite number $N$ is a Fermat pseudoprime to a coprime base $b$ when
$$
b^{N-1}\equiv1\pmod N.
$$
= Strong pseudoprime
{parent=Fermat pseudoprime}
{wiki}
Write the even number $N-1$ as $2^s m$ with $m$ odd. An odd composite number $N$ is a strong pseudoprime to a coprime base $b$ when
$$
b^m\equiv1\pmod N
$$
or $b^{2^jm}\equiv-1\pmod N$ for some $0\leq j<s$.
= Strong-pseudoprime bases for a product of two primes with common predecessor divisor ten
{parent=Strong pseudoprime}
Let $N=pq$ for distinct odd <prime numbers> $p,q$ with $\gcd(p-1,q-1)=10$. Exactly $100$ unit bases make $N$ a <Fermat pseudoprime>, and exactly $50$ of these make it a <strong pseudoprime>. The Fermat bases form $C_{10}\times C_{10}$ under the <Chinese remainder theorem for unit groups>. If $N-1=2^sm$, then $5\mid m$ and $m$ is odd, so the $m$th-power map sends five elements of each $C_{10}$ to $1$ and five to $-1$. The strong condition requires equal signs in both components, giving $5^2+5^2=50$.
= Euler pseudoprime
{parent=Number theory}
{c}
{wiki}
An odd composite number $N$ is an Euler pseudoprime to a coprime base $b$ when
$$
b^{(N-1)/2}\equiv\left(\frac bN\right)\pmod N,
$$
where the right side is the Jacobi symbol.
= P-adic valuation
{parent=Number theory}
{c}
{wiki=P-adic_valuation}
For a prime $p$ and a nonzero integer $N$, the $p$-adic valuation is
$$
v_p(N)=\max\{a\in\mathbb Z_{\geq0}:p^a\mid N\}.
$$
It extends to nonzero rational numbers by $v_p(a/b)=v_p(a)-v_p(b)$.
= Legendre formula
{parent=P-adic valuation}
{c}
{wiki=Legendre%27s_formula}
For a <prime number> $p$ and a positive <integer> $n$, the <P-adic valuation> of a <factorial> is
$$
v_p(n!)=\sum_{j\geq1}\left\lfloor\frac{n}{p^j}\right\rfloor.
$$
= Valuation of a near-central binomial coefficient
{parent=P-adic valuation}
If $k\geq1$ and $k+2\leq p\leq2k+1$ is prime, then
$$
v_p\left(\binom{2k+1}{k+1}\right)=1.
$$
Indeed, neither $(k+1)!$ nor $k!$ contains a factor $p$, while $(2k+1)!$ contains $p$ exactly once because $2p>2k+1$.
= Primorial
{parent=Number theory}
{wiki}
For real $X\geq1$, the primorial up to $X$ is
$$
P(X)=\prod_{p\leq X}p,
$$
where the product ranges over primes.
= Chebyshev theta function
{title2=$\vartheta(x)$}
{parent=Primorial}
{c}
{wiki=Chebyshev_function}
The Chebyshev theta function is the <natural logarithm> of the <primorial>:
$$
\vartheta(x)=\sum_{p\leq x}\log p
=\log\prod_{p\leq x}p,
$$
where both the sum and the product range over <prime numbers>.
= Elementary lower bound for the Chebyshev theta function
{parent=Chebyshev theta function}
The <central binomial coefficient> and <Legendre formula> imply
$$
\vartheta(x)\geq\frac{x}{12}
$$
for every sufficiently large real number $x$.
= Elementary primorial bound
{parent=Primorial}
For every real $X\geq1$,
$$
P(X)\leq4^X.
$$
For integer $n$, strong induction proves this by splitting according to parity. If $n=2k$, every prime in $(k,2k]$ divides $\binom{2k}{k}$, so
$$
P(2k)\leq P(k)\binom{2k}{k}\leq4^k4^k.
$$
If $n=2k+1$, the <valuation of a near-central binomial coefficient> gives
$$
P(2k+1)\leq P(k+1)\binom{2k+1}{k+1}\leq4^{k+1}4^k.
$$
The binomial estimates follow from the binomial theorem; in the odd case the two equal central coefficients together are at most $2^{2k+1}$. The result for real $X$ follows by replacing $X$ with $\lfloor X\rfloor$.
= Decisive number
{parent=Number theory}
A positive <integer> $n$ is decisive when every <integer> $a$ satisfying $1<a<n$ and $\gcd(a,n)=1$ is a <prime number>. There are only finitely many decisive numbers: every prime $p<\sqrt n$ must divide a decisive $n$, so the <Chebyshev theta function> gives $\log n\geq\vartheta(\sqrt n)$, which eventually contradicts the linear lower bound for $\vartheta(\sqrt n)$.
= Prime-counting function
{parent=Number theory}
{wiki=Prime-counting_function}
The prime-counting function $\pi(X)$ is the number of primes at most $X$.
= Prime-counting upper bound from a primorial estimate
{parent=Prime-counting function}
If $P(X)\leq A^X$ for every $X\geq1$, where $A>1$, then
$$
\pi(X)\leq(1+2\log A)\frac{X}{\log X}
$$
for $X\geq2$. Every prime in $(\sqrt X,X]$ contributes at least $\sqrt X$ to the <primorial>, so
$$
(\sqrt X)^{\pi(X)-\pi(\sqrt X)}\leq P(X)\leq A^X.
$$
Taking logarithms, using $\pi(\sqrt X)\leq\sqrt X$, and observing that $\log X\leq\sqrt X$ for $X\geq2$ proves the claim.
= Primitive root
{parent=Number theory}
{wiki=Primitive_root_modulo_n}
A unit $g$ modulo $N$ is a primitive root when its multiplicative order is $\varphi(N)$.
= Lifting a primitive root to odd prime powers
{parent=Primitive root}
Let $p$ be an odd prime and let $b$ be primitive modulo $p$. Then $b$ is primitive modulo every $p^m$ if and only if it is primitive modulo $p^2$. In that case
$$
\operatorname{ord}_{p^m}(b)=p^{m-1}(p-1).
$$
= Primitive-root modulus classification
{parent=Primitive root}
An integer $n$ has a primitive root exactly when
$$
n\in\{1,2,4,p^a,2p^a\},
$$
where $p$ is an odd prime and $a\geq1$. When primitive roots exist, their number is $\varphi(\varphi(n))$.
= Quadratic residue
{parent=Number theory}
{wiki}
For an odd prime $p$, a nonzero class $a$ is a quadratic residue when $a\equiv x^2\pmod p$. These residues form an index-two subgroup of $(\mathbb Z/p\mathbb Z)^\times$.
= Quadratic nonresidue
{parent=Quadratic residue}
{wiki}
A nonzero class modulo an odd prime is a quadratic nonresidue when it is not a square.
= Quadratic non-residue
{synonym}
= Quadratic Gauss sum
{title2=$G(\chi)$}
{parent=Quadratic residue}
{c}
{wiki=Quadratic_Gauss_sum}
For $\omega=e^{2\pi i/p}$ and the <Legendre symbol> $\chi$, the quadratic Gauss sum is
$$
G(\chi)=\sum_{a=1}^{p-1}\chi(a)\omega^a.
$$
It equals $\sqrt p$ for $p\equiv1\pmod4$ and $i\sqrt p$ for $p\equiv3\pmod4$ with the standard choice of square root.
= Quadratic periods modulo eleven
{parent=Quadratic Gauss sum}
If $Q$ and $N$ are the nonzero square and nonsquare classes modulo eleven and $\omega=e^{2\pi i/11}$, then
$$
\sum_{q\in Q}\omega^q=\frac{-1+i\sqrt{11}}2,
\qquad
\sum_{n\in N}\omega^n=\frac{-1-i\sqrt{11}}2.
$$
Their sum is $-1$, and their difference is the <Quadratic Gauss sum> $i\sqrt{11}$.
= Legendre symbol
{parent=Quadratic residue}
{c}
{wiki}
For an odd prime $p$,
$$
\left(\frac ap\right)=
\begin{cases}
0,&p\mid a,\\
1,&a\not\equiv0\pmod p\text{ is a square},\\
-1,&a\text{ is a nonsquare}.
\end{cases}
$$
= Euler's criterion
{parent=Legendre symbol}
{c}
{wiki}
For an odd prime $p$ and $p\nmid a$,
$$
a^{(p-1)/2}\equiv\left(\frac ap\right)\pmod p.
$$
= Gauss lemma
{disambiguate=number theory}
{c}
{parent=Legendre symbol}
{wiki=Gauss%27s_lemma_(number_theory)}
For an odd prime $p$ and $p\nmid a$, let $m$ be the number of least positive residues among
$$
a,2a,\ldots,\frac{p-1}{2}a
$$
that exceed $p/2$. Then
$$
\left(\frac ap\right)=(-1)^m.
$$
= Euler criterion
{c}
{parent=Legendre symbol}
{wiki}
For an odd prime $p$,
$$
a^{(p-1)/2}\equiv\left(\frac ap\right)\pmod p.
$$
For $p\nmid a$, write $a=g^m$ using a <primitive root> $g$; then the left side is $(-1)^m$, which is one exactly when $m$ is even and $a$ is a square.
= First supplementary law for quadratic reciprocity
{parent=Euler criterion}
Euler's criterion at $a=-1$ gives
$$
\left(\frac{-1}{p}\right)=(-1)^{(p-1)/2}.
$$
= Second supplementary law for quadratic reciprocity
{parent=Euler criterion}
For every odd prime,
$$
\left(\frac2p\right)=(-1)^{(p^2-1)/8}.
$$
= Euclid proof for infinitely many primes congruent to seven modulo eight
{parent=Second supplementary law for quadratic reciprocity}
If $q_1,\ldots,q_r$ listed all primes congruent to seven modulo eight, then for $n=8q_1\cdots q_r$ the odd number $(n^2-2)/2$ is seven modulo eight. Every prime factor is one or seven modulo eight, at least one is seven, and none is among the $q_i$, a contradiction.
= Elementary logarithmic lower bound for primes in the quadratic-residue classes of two
{parent=Second supplementary law for quadratic reciprocity}
Let $\pi_k(x)$ count primes at most $x$ congruent to $k$ modulo eight. Bounding the prime-power divisibility of
$$
\prod_{\sqrt x/2\leq n\leq\sqrt x}(n^2-2)
$$
above and its size below gives, for all sufficiently large $x$,
$$
\pi_1(x)+\pi_7(x)+1\geq\frac{\log x}{6\log3}.
$$
= Prime-power binomial congruence for a matrix
{parent=Euler criterion}
For an integer matrix $A$ and prime $p$, the commuting-matrix binomial theorem and divisibility of $\binom pj$ for $0<j<p$ give
$$
(I+A)^p\equiv I+A^p\pmod p.
$$
= Weighted complete Legendre-symbol sum
{parent=Legendre symbol}
For $T=\sum_{a=1}^{p-1}a(\frac ap)$, one has $T=0$ when $p\equiv1\pmod4$, and $T\equiv0\pmod p$ for every $p>3$.
= Lower-half quadratic-residue sum for primes congruent to seven modulo eight
{parent=Legendre symbol}
If $p\equiv7\pmod8$, the sum of the least positive quadratic residues below $p/2$ is
$$
\frac{p^2-1}{16}.
$$
The proof uses $(\frac2p)=1$ to compare the sum of all residues with its image under doubling.
= Discriminant criterion for a quadratic congruence modulo an odd prime
{parent=Legendre symbol}
For $p\nmid a$, the congruence $aX^2+bX+c=0\pmod p$ has a solution exactly when its discriminant $b^2-4ac$ is zero or a quadratic residue modulo $p$.
= Primitive-root lifting criterion
{parent=Number theory}
If $g$ is primitive modulo an odd prime $p$ and $g^{p-1}\not\equiv1\pmod{p^2}$, then $g$ is primitive modulo every $p^k$.
= Möbius function
{parent=Number theory}
{wiki}
The Möbius function is $\mu(1)=1$, is zero on integers divisible by a prime square, and is $(-1)^r$ on products of $r$ distinct primes.
= Riemann zeta function
{title2=$\zeta(s)$}
{c}
{parent=Number theory}
{wiki}
$\zeta(s)=\sum_{n\ge1}n^{-s}$ for $\Re s>1$; its Euler product is $\prod_p(1-p^{-s})^{-1}$.
= Dirichlet eta function
{title2=$\eta(s)$}
{c}
{parent=Riemann zeta function}
{wiki}
For $\Re s>0$, the alternating Dirichlet series
$$
\eta(s)=\sum_{n=1}^\infty(-1)^{n-1}n^{-s}
$$
converges locally uniformly and defines a holomorphic function. For $\Re s>1$,
$$
\eta(s)=(1-2^{1-s})\zeta(s).
$$
= Analytic continuation of the Riemann zeta function to the right half-plane
{c}
{parent=Dirichlet eta function}
The identity $\zeta(s)=\eta(s)/(1-2^{1-s})$ continues the <Riemann zeta function> meromorphically to $\Re s>0$. Apparent singularities at nonreal zeros of $1-2^{1-s}$ are removable, as one sees by replacing $2$ with an integer $k$ for which $1-k^{1-s}\ne0$. At $s=1$, $\eta(1)=\log2$ and $1-2^{1-s}\sim(s-1)\log2$, so $\zeta$ has a simple pole of residue one.
= Jacobi symbol
{c}
{parent=Number theory}
{wiki}
For odd $n=\prod p_i^{e_i}$, $(a/n)=\prod(a/p_i)^{e_i}$. A value $1$ need not mean that $a$ is a square modulo composite $n$.
= Quadratic reciprocity
{parent=Number theory}
{wiki}
For distinct odd primes, $(p/q)(q/p)=(-1)^{(p-1)(q-1)/4}$.
= Quadratic character of minus three
{parent=Quadratic reciprocity}
For an odd prime $p\ne3$, quadratic reciprocity gives
$$
\left(\frac{-3}{p}\right)=\left(\frac p3\right).
$$
Thus $-3$ is a square modulo $p$ exactly when $p\equiv1\pmod3$.
= Cube roots of minus one modulo an odd prime
{parent=Quadratic character of minus three}
The factorization
$$
X^3+1=(X+1)(X^2-X+1)
$$
shows that $X^3=-1$ always has $X=-1$ as a solution. For $p\ne3$, it has two further solutions exactly when $-3$ is a quadratic residue; for $p=3$, all three factors coalesce at the unique root $-1$.
= Carmichael number
{c}
{parent=Number theory}
{wiki}
A composite $N$ is Carmichael when $a^{N-1}\equiv1\pmod N$ for every $a$ coprime to $N$.
= Korselt criterion
{c}
{parent=Number theory}
{wiki=Korselt%27s_criterion}
A composite integer $N$ is Carmichael exactly when it is square-free and $p-1$ divides $N-1$ for every prime $p$ dividing $N$.
= Continued fraction
{parent=Number theory}
{wiki}
A simple continued fraction recursively expands a real number by taking integer parts and reciprocals. Its convergents are exceptionally good rational approximations.
= Continued-fraction algorithm
{parent=Continued fraction}
Starting from $x_0=x>0$, define
$$
a_n=\lfloor x_n\rfloor,
\qquad
x_{n+1}=\frac1{x_n-a_n}
$$
whenever $x_n$ is not an integer. This produces $x=[a_0;a_1,a_2,\ldots]$.
= Termination criterion for a simple continued fraction
{parent=Continued-fraction algorithm}
A simple continued fraction terminates exactly when its value is rational. For a reduced rational $p/q$, each reciprocal step is one step of the Euclidean algorithm and replaces the denominator by a strictly smaller nonnegative remainder.
= Continued fraction convergent
{parent=Continued fraction}
{wiki}
Truncating a simple continued fraction gives a convergent; sufficiently accurate rational approximations with bounded denominator occur among these convergents.
= Continued-fraction matrix
{parent=Continued fraction convergent}
With $M(a)=\left(\begin{smallmatrix}a&1\\1&0\end{smallmatrix}\right)$,
$$
M(a_0)\cdots M(a_n)
=\begin{pmatrix}p_n&p_{n-1}\\q_n&q_{n-1}\end{pmatrix}.
$$
= Continued-fraction tail formula
{parent=Continued-fraction matrix}
If $p_n/q_n=[a_0,\ldots,a_n]$, then appending a positive tail $x$ gives
$$[a_0,\ldots,a_n,x]
=\frac{p_nx+p_{n-1}}{q_nx+q_{n-1}}.$$
= Positive generalized continued fraction
{parent=Continued fraction}
For positive $a_j,b_j$, define $p_0=a_0$, $p_{-1}=1$, $q_0=1$, $q_{-1}=0$ and
$$
p_j=a_jp_{j-1}+b_{j-1}p_{j-2},
\qquad
q_j=a_jq_{j-1}+b_{j-1}q_{j-2}.
$$
Then
$$
\begin{pmatrix}p_n&b_np_{n-1}\\q_n&b_nq_{n-1}\end{pmatrix}
=\prod_{j=0}^n
\begin{pmatrix}a_j&b_j\\1&0\end{pmatrix},
$$
and $p_n/q_n$ is the corresponding finite generalized continued fraction.
= Convergence of a positive simple continued fraction
{parent=Positive generalized continued fraction}
When $b_j=1$ and $a_j$ are positive integers, adjacent convergents satisfy
$$
p_nq_{n-1}-q_np_{n-1}=(-1)^{n+1}.
$$
Even and odd convergents are monotone from opposite sides, their separation is $1/(q_nq_{n+1})$, and $q_n\to\infty$. They therefore have a common limit $x$, with
$$
\left|\frac{p_n}{q_n}-x\right|
+\left|\frac{p_{n+1}}{q_{n+1}}-x\right|
=\frac1{q_nq_{n+1}}.
$$
= All-one continued fraction and Fibonacci ratios
{parent=Convergence of a positive simple continued fraction}
If every $a_j=b_j=1$, then $p_n=F_{n+2}$ and $q_n=F_{n+1}$. Binet's formula
$$
F_n=\frac{\phi^n-\psi^n}{\sqrt5},
\qquad
\phi=\frac{1+\sqrt5}{2},
\quad
\psi=-\phi^{-1},
$$
shows that the convergents tend to $\phi$ and gives sharp scaled errors through $F_{n+1}-\phi F_n=\psi^n$.
= Periodic continued fraction of a quadratic irrational
{parent=Continued fraction}
{wiki=Lagrange%27s_theorem_(number_theory)}
The simple continued fraction of a quadratic irrational is eventually periodic. For a nonsquare positive integer $D$, the continued fraction of $\sqrt D$ is periodic after its integer part.
= Continued fraction of the square root of three
{parent=Periodic continued fraction of a quadratic irrational}
Successive complete quotients repeat after two steps:
$$
\sqrt3=[1;\overline{1,2}].
$$
= Continued fraction of the square root of eleven
{parent=Periodic continued fraction of a quadratic irrational}
Rationalizing successive complete quotients gives
$$\sqrt{11}=[3;\overline{3,6}].$$
= Alternating multiplier recurrence for convergents of the square root of eleven
{parent=Continued fraction of the square root of eleven}
If $p_n/q_n$ are the convergents of $\sqrt{11}$, then
$$
p_{n+1}+q_{n+1}\sqrt{11}
=\begin{cases}
(3+\sqrt{11})(p_n+q_n\sqrt{11}),&n\text{ odd},\\
\dfrac{3+\sqrt{11}}2(p_n+q_n\sqrt{11}),&n\text{ even}.
\end{cases}
$$
= Pell-type norm from a periodic continued fraction
{parent=Continued fraction of the square root of eleven}
For the even convergents of $\sqrt{11}$,
$$p_{2m}+q_{2m}\sqrt{11}
=(3+\sqrt{11})(10+3\sqrt{11})^m.$$
Since the second factor has norm one, every such convergent satisfies $p_{2m}^2-11q_{2m}^2=-2$.
= Liouville approximation theorem
{c}
{parent=Number theory}
{wiki=Liouville_number}
If an irrational algebraic number has degree $d$, then $|\alpha-p/q|>C(\alpha)q^{-d}$. Approximations of arbitrarily larger polynomial order therefore prove transcendence.
= Proof of Liouville approximation theorem
{parent=Liouville approximation theorem}
For the degree-$d$ minimal polynomial $P\in\mathbb Z[X]$ of $\alpha$, the nonzero integer $q^dP(p/q)$ gives $|P(p/q)|\geq q^{-d}$. On a fixed neighbourhood of $\alpha$, the mean value theorem bounds
$$
|P(p/q)|\leq\max|P'|\,|p/q-\alpha|.
$$
Outside that neighbourhood the desired lower bound is immediate, giving $|\alpha-p/q|>c(\alpha)q^{-d}$ after decreasing the constant.
= Separation of distinct reduced fractions
{parent=Liouville approximation theorem}
For distinct reduced fractions $p/q$ and $u/v$,
$$
\left|\frac pq-\frac uv\right|
=\frac{|pv-qu|}{qv}\geq\frac1{qv}.
$$
If $q>v$, this is strictly greater than $q^{-2}$.
= Transcendental subseries of a positive rational convergent series
{parent=Liouville approximation theorem}
Every convergent series of positive rational terms has a subseries whose rational partial sums $p_j/q_j$ satisfy
$$
0<\alpha-\frac{p_j}{q_j}<2^{-j}q_j^{-j}.
$$
Choose each new term small enough to enforce all previous tail bounds. Separation of reduced fractions first makes $\alpha$ irrational, and the <Liouville approximation theorem> then rules out every finite algebraic degree.
= Binary quadratic form
{parent=Number theory}
{wiki}
A binary quadratic form is $ax^2+bxy+cy^2$; integral changes of variables organize forms into equivalence classes.
= Proper equivalence of binary quadratic forms
{parent=Binary quadratic form}
Integral forms $f$ and $g$ are properly equivalent when
$$g(x,y)=f(\alpha x+\beta y,\gamma x+\delta y)$$
for some $\left(\begin{smallmatrix}\alpha&\beta\\\gamma&\delta\end{smallmatrix}\right)\in\operatorname{SL}_2(\mathbb Z)$. Proper equivalence preserves both represented integers and orientation.
= Primitive binary quadratic form
{parent=Binary quadratic form}
An integral binary quadratic form $[a,b,c]$ is primitive when $\gcd(a,b,c)=1$. This property is invariant under proper equivalence because a unimodular change and its integral inverse express either coefficient triple as integer combinations of the other.
= Discriminant of a binary quadratic form
{parent=Binary quadratic form}
{wiki=Discriminant\#Quadratic_forms}
The discriminant of $[a,b,c]$ is $D=b^2-4ac$. It is invariant under proper equivalence, and a real form with $a>0$ is positive definite exactly when $D<0$.
= Reduced positive definite binary quadratic form
{parent=Binary quadratic form}
{wiki=Binary_quadratic_form\#Reduced_forms}
A positive definite integral form $[a,b,c]$ is reduced when $|b|\leq a\leq c$, with $b\geq0$ if $|b|=a$ or $a=c$. Every proper equivalence class has a unique reduced representative under this boundary convention.
= Enumeration of reduced binary quadratic forms
{parent=Reduced positive definite binary quadratic form}
For a reduced form of negative discriminant $D$, the inequalities imply $3a^2\leq|D|$. One can therefore enumerate all classes by checking the finite set
$$1\leq a\leq\sqrt{|D|/3},\qquad |b|\leq a,$$
and retaining integral $c=(b^2-D)/(4a)$ with $a\leq c$ and the boundary sign convention.
= Class number of a negative discriminant
{parent=Reduced positive definite binary quadratic form}
{wiki=Class_number_problem}
For a negative discriminant $D\equiv0$ or $1\pmod4$, the class number $h(D)$ is the number of proper equivalence classes of primitive positive definite integral binary quadratic forms of discriminant $D$. Equivalently, it is the number of reduced primitive forms of discriminant $D$.
= Two distinguished classes of discriminant minus eight q
{title2=$D=-8q$}
{parent=Class number of a negative discriminant}
For an odd <prime number> $q$, the primitive positive definite forms
$$
[1,0,2q]
\qquad\hbox{and}\qquad
[2,0,q]
$$
have discriminant $-8q$ and lie in distinct proper equivalence classes. The first represents one, whereas the second has minimum positive value two.
= Prime representation when h of minus eight q equals two
{title2=$h(-8q)=2$}
{parent=Two distinguished classes of discriminant minus eight q}
If $q\equiv3\pmod8$ is prime and $h(-8q)=2$, then for every prime $p>q$,
$$
p=x^2+2qy^2
$$
for some integers $x,y$ exactly when $p\equiv\pm1\pmod8$ and $p$ is a <quadratic residue> modulo $q$.
= Coprime-factorization lower bound for a quadratic-form class number
{parent=Class number of a negative discriminant}
Let $d$ be odd and have $k$ distinct prime divisors. Assigning each complete prime-power factor of $d$ to one of two factors gives $2^k$ ordered coprime factorizations $d=ac$. Interchanging $a$ and $c$ identifies pairs, and each unordered factorization gives a different reduced primitive form $[\min(a,c),0,\max(a,c)]$ of discriminant $-4d$. Hence
$$
h(-4d)\geq2^{k-1}.
$$
= Unimodular reduction of a discriminant-minus-four form to two squares
{parent=Binary quadratic form}
The identity
$$
5x^2+16xy+13y^2=(x+2y)^2+(2x+3y)^2
$$
comes from an integer change-of-variable matrix of determinant $-1$. It therefore preserves the set of integers represented and reduces the form to $u^2+v^2$.
= Euclid lemma
{parent=Number theory}
{c}
{wiki}
If a prime divides a product of integers, it divides at least one factor.
= Prime valuation
{parent=Number theory}
{wiki}
The prime valuation v_p(n) is the exponent of p in the prime factorization of n.
= Euler totient function
{title2=$\varphi(n)$}
{parent=Number theory}
{c}
{wiki}
Euler’s totient function counts residue classes modulo n that are coprime to n.
= Euler theorem
{parent=Euler totient function}
{c}
{wiki}
If a is coprime to n, then a raised to the power phi(n) is congruent to one modulo n.
Multiplication by a unit $a$ permutes the reduced residue classes modulo $n$. Multiplying all classes before and after this permutation and cancelling their unit product proves $a^{\phi(n)}\equiv1\pmod n$.
= Multiplicativity of the Euler totient function
{parent=Euler totient function}
{wiki}
For coprime positive integers m and n, the Chinese remainder theorem gives phi(mn)=phi(m)phi(n).
= Finite fibres of the Euler totient function
{parent=Euler totient function}
For each positive integer $k$, only finitely many $n$ satisfy $\varphi(n)=k$. Indeed, every prime $p\mid n$ has $p-1\mid k$, and the exponent of $p$ in $n$ is bounded because $p^{a-1}\mid k$.
= Jordan totient function
{title2=$J_k(n)$}
{parent=Number theory}
{c}
{wiki=Jordan%27s_totient_function}
The Jordan totient function counts ordered $k$-tuples modulo $n$ that together with $n$ have <greatest common divisor> one. The <inclusion-exclusion principle> gives
$$
J_k(n)=n^k\prod_{p\mid n}(1-p^{-k}).
$$
= Fermat little theorem
{parent=Number theory}
{c}
{wiki}
For a prime p, every integer a satisfies a^p congruent to a modulo p.
= Squarefree integer
{parent=Number theory}
{wiki}
A squarefree integer is not divisible by the square of any prime.
= Square factor
{parent=Number theory}
{wiki}
An integer has a square factor when some prime square divides it.
= Difference of two squares
{parent=Number theory}
{wiki}
The identity $r^2-s^2=(r-s)(r+s)$ converts a square difference into a factorization.
= Fermat factorization method
{parent=Difference of two squares}
{c}
{wiki=Fermat%27s_factorization_method}
Fermat factorization tests successive $r\geq\lceil\sqrt N\rceil$ until $r^2-N=s^2$, then returns $N=(r-s)(r+s)$.
= Rational number
{title2=$\mathbb Q$}
{parent=Number theory}
{wiki}
A rational number is a quotient of two integers with nonzero denominator.
= Density of the rational numbers
{parent=Rational number}
{wiki=Rational_number#Properties}
Between any two distinct real numbers lies a <rational number>.
= Eventually periodic decimal
{parent=Rational number}
{wiki=Repeating_decimal}
A real number is rational exactly when its expansion in any integer base is eventually periodic.
= Eventually periodic positional expansion of a rational number
{parent=Rational number}
A positional expansion in an integer base represents a rational number exactly when its digit sequence is eventually periodic. Long division proves the forward implication because only finitely many remainders occur; summing a periodic tail as a <geometric series> proves the converse.
= Carmichael function
{parent=Number theory}
{c}
{wiki}
The Carmichael function $\lambda(n)$ is the exponent of $(\mathbb Z/n\mathbb Z)^\times$, equivalently the least positive $m$ such that every unit $a$ satisfies $a^m\equiv1\pmod n$.
= Multiplicative order
{parent=Number theory}
{wiki=Multiplicative_order}
The multiplicative order of a unit $a$ modulo $N$ is the least positive $r$ for which $a^r\equiv1\pmod N$.
= Cyclic decimal divisibility
{parent=Multiplicative order}
For an $L$-digit decimal integer $n$, moving its leading digit to the end gives a cyclic rotation $c_1(n)$ satisfying
$$
c_1(n)\equiv10n\pmod{10^L-1}.
$$
Thus, when a modulus $d$ divides $10^L-1$, every rotation has the same divisibility by $d$ as $n$, up to multiplication by a power of ten.
= Periodic modular exponentiation
{parent=Multiplicative order}
For a unit $a$ modulo $N$, the function $x\mapsto a^x\bmod N$ is periodic on the integers.
= Order as the exact period of modular exponentiation
{parent=Periodic modular exponentiation}
Equality $a^x\equiv a^y\pmod N$ holds exactly when the multiplicative order divides $x-y$, so one period contains no repeated values.
= Order verification from divisors
{parent=Multiplicative order}
To verify a candidate order $r$, check $a^r\equiv1$ and rule out $a^{r/q}\equiv1$ for every prime divisor $q$ of $r$.
= Euclidean algorithm
{parent=Number theory}
{wiki}
The Euclidean algorithm repeatedly replaces $(a,b)$ by $(b,a\bmod b)$ and terminates at $\gcd(a,b)$.
= Linear Diophantine equation
{parent=Euclidean algorithm}
{wiki=Diophantine_equation\#Linear_Diophantine_equations}
A linear Diophantine equation in two variables has the form $ax+by=c$ with integer coefficients and seeks integer solutions.
= Linear Diophantine equation solvability criterion
{parent=Linear Diophantine equation}
The equation $ax+by=c$ has an integer solution exactly when $\gcd(a,b)$ divides $c$. Bézout's identity proves sufficiency, while every integer linear combination of $a,b$ is divisible by their greatest common divisor.
= Sum of two squares theorem
{parent=Number theory}
{wiki=Sum_of_two_squares_theorem}
A positive integer is a sum of two integer squares exactly when every prime factor congruent to $3$ modulo $4$ has even exponent in its prime factorization.