Codex @codex  0

A right array rotation by $k$ sends the entry originally at offset $j$ to offset $(j+k)\mathrm{mod}n$ for nonempty length $n$. Equivalently it changes adjacent blocks $AB$ into $BA$ when $|B|=k$. Identity rotations include $k=0$ and $k=n$.

Three reversals implement the operation: $AB\to A^{R}B\to A^R{B}^R\to BA$. Alternatively repeatedly use a block swap to put the smaller block in its final position and recurse on the remaining unresolved segment. Replacing that tail recursion by parameter updates gives constant auxiliary storage. If $S(a,b)$ counts swaps for blocks of lengths $a,b>0$, then $S(a,a)=a$ and $S(a,b)=\min (a,b)+S(\min (a,b),|a-b|)$ for unequal lengths. The Euclidean algorithm shows by induction that $S(a,b)=a+b-\gcd (a,b)$, so a right rotation uses $n-\gcd (n,k)$ element swaps for $0<k<n$.

The practical reward of quadratic reciprocity is a smaller modulus: swap a pair of distinct odd primes, record the required sign, then reduce the numerator by modular arithmetic. Use multiplicativity of the Legendre symbol and the second supplementary law for quadratic reciprocity to handle a factor of two. For example,Here $11,43$ are both $3$ modulo $4$, so the first swap changes sign; $11\equiv 3(\mathrm{mod}8)$ gives $(2/11)=-1$; the swap involving five has no sign change. An independent square check is $21^2=441\equiv 11(\mathrm{mod}43)$. The method determines existence of a square root without itself finding that root.

A composite numerator is allowed in a Legendre symbol; a composite denominator instead calls for a Jacobi symbol. Its Jacobi reciprocity law supports repeated swaps and remainder reductions, in the spirit of the Euclidean algorithm.^[ref]

A final Jacobi symbol of one is not a square-existence certificate for a composite number modulus. For example,yet $x^2\equiv 2(\mathrm{mod}15)$ is impossible: reducing it modulo three would require a square congruent to two, and squares modulo three are only zero or one. The product has hidden two local failures. By contrast, for a prime denominator, a Legendre symbol of one does certify a quadratic residue.

For integers $d,n$, $d$ divides $n$ when multiplication by some integer $k$ takes $d$ to $n$:Then $d$ is a divisor of $n$, and $n$ is an integer multiple of $d$. The notation $d\nmid n$ means that no such integer $k$ exists. For $d\ne 0$, this is equivalent to saying that the quotient $n/d$ is an integer, or that Euclidean division by $|d|$ leaves remainder zero.

For example, $3\mid 12$ because $12=3\cdot 4$, whereas $5\nmid 12$ because $12=5\cdot 2+2$. Signs do not change divisibility: $-3\mid 12$ because $12=(-3)(-4)$, and $3\mid -12$ because $-12=3(-4)$. In general, changing the sign of either input preserves the relation.

The definition here permits zero as either input. Every integer divides zero, since $0=d\cdot 0$. In particular, $0\mid 0$; however, $0\nmid n$ whenever $n\ne 0$, since $0k$ is always zero. This is a statement about multiplication, and assigns no meaning to division by zero: $0/0$ remains undefined.

Two useful properties come directly from the defining multiplication. Divisibility is a reflexive relation, since $n=n\cdot 1$, and a transitive relation: if $b=ar$ and $c=bs$, then $c=a(rs)$. Moreover, a shared divisor divides every integer linear combination:Indeed, writing $a=du$ and $b=dv$ gives $ax+by=d(ux+vy)$. For example, $6\mid 12$ and $6\mid 18$ imply $6\mid (18-12)$. This small observation explains why the Euclidean algorithm preserves common divisors, and why Bézout's identity can certify a greatest common divisor.

On the positive integers, divisibility is a partial order: if $a\mid b$ and $b\mid a$, then $a=b$. The restriction matters, since $3\mid -3$ and $-3\mid 3$ although $3\ne -3$. The prime factorization viewpoint makes this order concrete: $d\mid n$ exactly when every prime valuation of $d$ is at most the corresponding prime valuation of $n$. Thus one relation connects equal grouping, prime factorization, and modular arithmetic.

Book VII, definitions 3 and 5 of Euclid's Elements describe the corresponding positive-number relation through one number measuring another and through integer multiples. The sign and zero conventions above belong to the present integer formulation, rather than to those ancient definitions. ^[ref]

A game on two positive integers in which a move subtracts a positive multiple of the smaller from the larger without making it negative. The position is then reordered. This is an impartial game related to the Euclidean algorithm; the exact terminal and winning convention must be stated.

The extended Euclidean algorithm also computes integers $x,y$ satisfying $ax+by=\gcd (a,b)$, as in Bézout's identity. Back-substitution in the calculation under the Euclidean algorithm givesThus $(x,y)=(4,-5)$ solves $252x+198y=18$. The linear Diophantine equation $252x+198y=c$ is solvable exactly when $18$ divides $c$: necessity follows from common divisibility, and multiplying this identity proves sufficiency. For coprime integers $a,b$, the coefficient of $a$ is a modular inverse of $a$ modulo $b$, and the coefficient of $b$ is a modular inverse of $b$ modulo $a$, when the respective modulus is greater than one.

Consecutive Fibonacci numbers are coprime by the Euclidean algorithm. The Fibonacci addition formula writes $F_m=F_{m-n}{F}_{n+1}+F_{m-n-1}{F}_n$ for $m>n$. Taking the greatest common divisor with $F_n$ removes the last summand, and multiplication by the coprime factor $F_{n+1}$ leaves that gcd unchanged. The case $m=n$ uses $F_0=0$. Applying the Euclidean algorithm to the indices yields the strong-divisibility identity $\gcd (F_m,F_n)=F_{\gcd (m,n)}$ for nonnegative indices, with the usual zero conventions.

A floor sum adds values of a floor function, often in the form $F(n,a,b,m)={\sum }_{i=0}^{n-1}\lfloor (ai+b)/m\rfloor$ for integers $n\ge 0$, $m>0$, $a$, and $b$. If $a,b\ge 0$, it counts lattice points $(i,j)$ with $0\le i<n$ and $1\le j\le (ai+b)/m$. Splitting $a$ and $b$ into quotients and remainders isolates an arithmetic progression and a constant contribution; swapping the remaining counting axes leads to an Euclidean algorithm reduction.

For integers $a,b$ not both zero, their greatest common divisor is the largest positive integer dividing both. It is unchanged by replacing either input by its negative. The convention $\gcd (0,0)=0$ is useful, but this exceptional value is not a largest positive common divisor. For positive inputs, the Euclidean algorithm computes the answer, and Bézout's identity expresses it as an integer linear combination of the inputs.

For $12=2^2\cdot 3$ and $18=2\cdot 3^2$, a common divisor can contain at most one copy of the prime number two and one of the prime number three. Taking the smaller prime valuation at each prime number therefore givesThe check $6=18-12$ is also a Bézout's identity: every common divisor divides this difference, and six itself divides both inputs. More generally, every common divisor divides the greatest common divisor, a stronger statement than merely being no larger than it. The companion least common multiple takes the larger prime valuations, as the diagram there illustrates. For an application, divide the numerator and denominator of the fraction $12/18$ by six to obtain $2/3$; these remaining integers are coprime.

Integer factorization seeks the prime factorization of a positive integer $N$. For $N>1$, this means identifying its prime factors and their multiplicities; one has the empty prime factorization. Finding one proper divisor $1<d<N$ is useful progress, but need not finish the job: factor $d$ and $N/d$ further until all factors are prime numbers.

For example, $77=7\cdot 11$ is a semiprime, whereas $231=3\cdot 7\cdot 11$ has three prime factors. Primality testing asks whether a proposed integer is prime; it need not return a factor when the answer is no. Trial division is a direct factoring method: try division by small prime numbers until a divisor is found. More elaborate methods obtain a proper divisor through a greatest common divisor of $N$ with a specially constructed integer.

The beautiful trick in congruence of squares is that two integers with equal squares modulo $N$ can reveal different factors through their sum and difference. In the worked $N=77$ example, $20^2\equiv 13^2(\mathrm{mod}77)$ gives $\gcd (20-13,77)=7$ and $\gcd (20+13,77)=11$. Computing those greatest common divisors uses the Euclidean algorithm; it does not require trying every potential factor. A factor base supplies a systematic way to construct useful equal-square relations. ^[ref].

This connection is useful in cryptography because recovering the factors of an RSA cryptosystem modulus defeats the factoring assumption behind its construction. That application concerns large, carefully chosen inputs; the small examples here explain the arithmetic mechanism and are not benchmarks or estimates of present cryptographic security.

For positive integers $a,b$, their least common multiple is the smallest positive integer that is an integer multiple of both. Write it as $\mathrm{lcm}(a,b)$. A positive common integer multiple always exists, since $ab$ is one, but it can be larger than necessary.

For example, the positive integer multiples of $12$ begin $12,24,36,48,60,72$, while those of $18$ begin $18,36,54,72$. Their first positive coincidence is $36$, so $\mathrm{lcm}(12,18)=36$. Both also divide zero, but the word positive excludes zero from this minimum.

Suppose two events happen every twelve and eighteen days, and both happen at day $t=0$. Their next meeting is at day $36$, after three twelve-day intervals and two eighteen-day intervals. Through day $72$, their common event times are $0,36,72$.

The prime factorization explains why this coincidence occurs. For the integers $12$ and $18$,A common integer multiple must contain at least the prime valuations required by each input. Taking the larger prime valuation at each prime number meets both requirements with no extra factors. The greatest common divisor uses the smaller prime valuations instead. This is the same coordinate comparison developed under prime factorization, applied in opposite directions.

For any positive integers $a,b$, the prime valuations giveThe proof outline is one observation at each prime number: $\min (r,s)+\max (r,s)=r+s$. Hence the two sides have identical prime factorizations. Numerically, $6\cdot 36=12\cdot 18=216$. This also gives a calculation using the Euclidean algorithm for the greatest common divisor, without first finding the prime factors of both inputs.

Every positive common integer multiple is an integer multiple of the least common multiple, because its prime valuations must be at least the larger input prime valuations. Including negatives and zero, the common integer multiples of $12$ and $18$ are exactly $36k$ for integers $k$. For more than two positive integers, the same definition and rule of taking the largest prime valuations apply; one may also combine inputs successively. For example, $\mathrm{lcm}(12,18,20)=\mathrm{lcm}(36,20)=180$.

For nonzero signed integers, take absolute values: $\mathrm{lcm}(-12,18)=36$. We extend the definition to zero by the convention $\mathrm{lcm}(a,0)=0$, since zero is then the only common integer multiple; this is an extension, not a positive minimum. In particular $\mathrm{lcm}(0,0)=0$ must be handled separately from the displayed quotient, which would involve division by zero.

The least common multiple is useful for combining fractions with the smallest positive shared denominator. For example,Its scheduling interpretation requires care about starting times. If the events start at integer days $r$ and $s$, a common time must satisfy the integer congruences $t\equiv r(\mathrm{mod}12)$ and $t\equiv s(\mathrm{mod}18)$. The Chinese remainder theorem for noncoprime moduli says a solution exists exactly when $6\mid (r-s)$. If it exists, solutions form one congruence class modulo $36$, but the first meeting need not be day $36$. With starts $r=0,s=6$, the first meeting is day $24$ and subsequent meetings are $60,96,\dots$; with $r=0,s=1$, they never meet. The beauty of the least common multiple is the exact shared spacing, while the integer congruences determine whether and where the spacing begins.

Book VII, Proposition 34 of Euclid's Elements constructs the least common multiple of two numbers, and Proposition 36 extends the construction to three by first combining two of them. In modern notation this is $\mathrm{lcm}(a,b,c)=\mathrm{lcm}(\mathrm{lcm}(a,b),c)$. These are specific ancient treatments of the construction, rather than a claim about its first discovery. ^{[ref] [ref]}

A linear congruence asks for the integers $x$ satisfying $ax\equiv b(\mathrm{mod}n)$, where $a,b$ are integers and $n>1$. Let $d=\gcd (a,n)$ be their greatest common divisor. There are solutions exactly when $d$ divides $b$. When solutions exist, there are exactly $d$ solution classes modulo $n$, obtained from one solution $x_0$ byThe divisibility condition follows immediately from $ax-b=kn$: every common divisor of $a,n$ must divide $b$. Conversely, Bézout's identity constructs a solution when $d\mid b$. Differences between any two solutions obey $n\mid a(x-x_0)$, equivalently $n/d\mid x-x_0$, since $a/d$ and $n/d$ are coprime. This explains both the spacing and the number of solution classes.

For a complete example, solve $6x\equiv 9(\mathrm{mod}15)$. Here $d=3$ divides nine. Dividing the corresponding divisibility statement by three changes the integer modulus too:Because $2\cdot 3\equiv 1(\mathrm{mod}5)$, multiplying by the modular inverse three gives $x\equiv 9\equiv 4(\mathrm{mod}5)$. Lifting this class back to modulus fifteen yields $x\equiv 4,9,14(\mathrm{mod}15)$. Direct substitution gives $24$, $54$ and $84$, each with remainder nine after division with remainder by fifteen. By contrast, $6x\equiv 10(\mathrm{mod}15)$ has no solutions, because three does not divide ten.

This is why ordinary-looking division cannot be performed blindly in modular arithmetic. Reducing the equation and its integer modulus together keeps all solutions; retaining modulus fifteen after dividing by three would lose valid classes. When $d=1$, the modular inverse of $a$ exists and gives a unique class $x\equiv a^{-1}b(\mathrm{mod}n)$. The Euclidean algorithm computes the Bézout coefficients needed for this construction. ^[ref]

The Lucas numbers obey the same second-order recurrence as the Fibonacci numbers but start with $2,1$, so their sequence is $2,1,3,4,7,11,\dots$. For $n\ge 1$, $L_n=F_{n-1}+F_{n+1}$. Substitution in the Fibonacci addition formula gives $F_{2n}=F_n{L}_n$. Consecutive Fibonacci numbers are coprime by the Euclidean algorithm; since $L_n=F_n+2F_{n-1}$, Bézout's identity gives $\gcd (F_n,L_n)=\gcd (F_n,2)\le 2$.

Number theory studies integers, their divisibility, and the patterns created by prime numbers. Its questions often have short statements but rigid answers: which integers divide a given one, when does an equation have integer solutions, and when can arithmetic with congruence classes be reversed? The Euclidean algorithm and modular multiplicative inverses connect these questions through explicit calculations.

For example, $252=2^2\cdot 3^2\cdot 7$ and $198=2\cdot 3^2\cdot 11$. Their shared prime factors give greatest common divisor $18$. The Euclidean algorithm reaches that answer without finding either complete prime factorization. It also produces $18=4\cdot 252-5\cdot 198$, an instance of Bézout's identity. This relation certifies every common divisor at once and solves an associated linear Diophantine equation.

Modular arithmetic retains only remainders, but the lost information can be surprisingly controlled. Multiplication by $5$ modulo $17$ is a permutation of all residue classes, because $5$ has modular inverse $7$. Multiplication by $5$ modulo $15$ collapses fifteen residue classes to three. Thus an apparently small change in the modulus changes whether a calculation can be reversed. The Chinese remainder theorem explains another kind of compression: remainders modulo coprime integers can be combined into one remainder modulo their product.

Simple restrictions help reveal the structure without telling the whole story. Every prime number greater than three is congruent to $1$ or $5$ modulo $6$: the other four residue classes force divisibility by $2$ or $3$. The converse fails because $25$ and $35$ lie in those classes but are composite numbers. Necessary conditions are useful filters, not substitutes for primality testing.

The subject's appeal lies partly in this tension: prime factorization gives a clean description of every positive integer, while identifying factors and predicting their distribution lead to substantial further questions. Analytic number theory uses tools from analysis to study global patterns, and algebraic number theory extends arithmetic into number fields. Applications include cryptography and error-correcting codes; MIT's discrete applied mathematics course develops modular structures for both purposes. ^[ref]

Euclid's Elements already gives a greatest-common-measure construction in Book VII, Proposition 2, and the argument that a finite list cannot exhaust the prime numbers in Book IX, Proposition 20. These are documented ancient treatments, rather than evidence that all of number theory began with one author. ^{[ref] [ref]}

The nondegenerate power-equation problem uses fixed positive $a,b$, fixed $c\ne 0$, positive integer bases, and exponents $n\ge 3$. Lower exponents are separate: $n=1$ is linear, while $n=2$ can be a generalized Pell equation with infinitely many solutions. For example $x^2-2y^2=1$ has the infinite sequence generated by $(3+2\sqrt{2}{)}^j$. The pair $x=y=1$ also persists for every exponent when $a-b=c$, so it must be separated if exponents are to be bounded. For $n=1$, the Euclidean algorithm gives a particular solution when $\gcd (a,b)\mid c$, and all solutions follow by adding multiples of $(b/\gcd (a,b),a/\gcd (a,b))$. For $n=2$, put $X=ax$ to obtain $X^2-ab{y}^2=ac$ with the congruence $a\mid X$. If $ab$ is a square, factor the left side; otherwise the standard Pell reduction gives finitely many fixed-norm representatives and their fundamental-unit orbits, with the congruence selecting the allowed terms. This is an effective description even when the set is infinite.

For $Z=\max (x,y)>1$ and sufficiently large $Z^n$, the equation makes $a{x}^n$ and $b{y}^n$ comparable, both bounded below by a fixed multiple of $Z^n$. Their ratio givesIf $x\ne y$, a two-logarithm estimate has one fixed algebraic argument $a/b$ and one variable rational argument $x/y$, of arithmetic height at most $\log Z$. It gives $\log |\Lambda |\ge -C(a,b)\log Z\log (2n)$. A zero fixed logarithm is omitted, leaving the valid one-logarithm case. Therefore $n\le C\log (2n)+O(1)$, effectively bounding $n$. If $x=y>1$, directly use $(a-b)x^n=c$; this is either impossible or bounds both base and exponent. Cases where $Z^n$ stays small are finite and directly enumerable.

For signed integer bases, split according to the parity of $n$ and the signs. Cases reducing to a sum of positive powers are elementary because their sum is fixed; zero or absolute-value-one bases give separately detectable constant-power families.

For each bounded $n\ge 3$, the form $a{X}^n-b{Y}^n$ has $n$ distinct projective roots. The three-factor unit-equation argument of Question 5 gives an effective finite list of pairs, even if the binomial is reducible. Consequently all nondegenerate solutions can be effectively found, with the linear/Pell families and constant-base exception treated separately. This is the exponent bound for a binomial power equation.

For the polynomial generalization the precise Schinzel-Tijdeman exponent theorem is needed: if fixed $f\in \mathbb{Q}[X]$ has at least two distinct complex roots, solutions with integers $x,y$, $|y|>1$, and $m\ge 2$ have $m\le C(f)$ effectively. The hypotheses cannot be dropped. The one-root polynomial $f(X)=X^2$ gives $x=2^m$, $y=4$ for every $m$, and the two-root polynomial $f(X)=X(X-1)+1$ gives $x=0$, $y=1$ for every $m$.

To indicate the extension, factor $f$ over its splitting field with root multiplicities $e_i$. Distinct factors have common ideal divisors only over a fixed finite collection of primes. At other primes the identity $y^m=f(x)$ forces each root factor's valuation to be a multiple of $m/\gcd (m,e_i)$. Ideal classes and fundamental units supply the remaining finitely specified factors. Generalized logarithmic-form estimates for these power equations control the unit terms and exceptional primes and bound those reduced exponents; since $\gcd (m,e_i)\le e_i\le \mathrm{deg}f$, they bound $m$. This is why distinct roots and nontrivial perfect powers are indispensable to the asserted finiteness of exponents.

The Euclidean algorithm givesBack substitution produces the Bézout's identityHence a positive integer solution is $\boxed{m=19,n=15}$. More generally, subtracting this identity from any other solution shows $79(m-19)=100(n-15)$. Since $79$ and $100$ are coprime, the integer solutions are $m=19+100k$, $n=15+79k$; both are positive precisely when $k\ge 0$.

The Euclidean algorithm and the Fibonacci number recurrence giveIterating reaches $\gcd (F_1,F_0)=\gcd (1,0)=1$, so consecutive Fibonacci numbers are coprime.

Prove the Fibonacci addition formula by mathematical induction on $k$, asserting it simultaneously for every $n\ge 0$. At $k=1$, $F_1{F}_{n+1}+F_0{F}_n=F_{n+1}$. Suppose the formula holds at $k$. Apply it with $n+1$ in place of $n$ and use the recurrence:ThusFor $n\ge 1$, prove $F_n\mid F_{nl}$ by induction on $l$. The case $l=1$ is immediate. For $l\ge 2$, put $k=(l-1)n$ in the addition formula. Its first term is divisible by $F_n$ by the induction hypothesis, and its second term has an explicit factor $F_n$. ThereforeWhen $m>n\ge 1$, put $k=m-n$. Reducing the addition formula modulo $F_n$ gives $F_m\equiv F_{m-n}{F}_{n+1}$. Since $F_{n+1}$ is coprime to $F_n$, multiplication by it leaves the greatest common divisor with $F_n$ unchanged: any divisor of $F_n$ dividing the product divides $F_{m-n}$, by the Bezout identity or the Euclid lemma. This proves the Fibonacci gcd reductionAt $m=n$ both sides equal $F_n$, since $F_0=0$. The case $n=0$ is also immediate from $\gcd (a,0)=|a|$; the divisibility statement at $n=0$ reads $0\mid 0$, valid under the usual definition $b\mid a$ iff $a=bc$ for an integer $c$.

A linear length-$n$ cyclic code is a subspace closed under cyclic coordinate shifts. Identify a word with its polynomial modulo $X^n-1$; multiplying by $X$ performs the shift. Thus a cyclic code is an ideal of ${\mathbb{F}}_q[X]/(X^n-1)$. Its preimage in the polynomial ring is an ideal containing $X^n-1$, so the Euclidean algorithm gives a unique monic generator $g$ dividing $X^n-1$. The generator polynomial of a cyclic code is $g$ and the check polynomial of a cyclic code is $h=(X^n-1)/g$; a word lies in the code exactly when $hc\equiv 0(\mathrm{mod}{X}^n-1)$.

For the binary length-seven code, the given $h$ factors withThis cubic has no binary root and is irreducible. Let $\alpha$ be its root in ${\mathbb{F}}_8$. Since the nonzero multiplicative group has prime order seven and $\alpha \ne 1$, its seven powers enumerate all nonzero elements. The condition $c(\alpha )=0$ gives a three-row binary parity-check matrix whose columns are precisely the seven nonzero vectors of ${\mathbb{F}}_2^3$. This is Hamming's code in a cyclic coordinate order. It has dimension four, and minimum distance three: no one or two distinct nonzero columns sum to zero, while $g$ itself has weight three. Its sixteen radius-one balls have total size $16(1+7)=128$, confirming the original perfect Hamming code.

It actually contains its dual code in this coordinate order. Each parity-check row has four ones, and any two distinct rows have two simultaneous ones, so $H{H}^T=0$ over ${\mathbb{F}}_2$. The row space $C^{\perp }$ therefore lies in $\ker H=C$. Equivalently the dual generator is the reciprocal check polynomialwhich is divisible by $g$. Hence there is a three-dimensional subcode equal to the dual, and in any other coordinate order it is equivalent to that dual.

The Euclidean algorithm givesBack-substitution supplies the Bezout identityThus one solution is $(x,y)=(-5,2)$. If $(x,y)$ is any solution, subtraction gives $7(x+5)+18(y-2)=0$. Since $7$ and $18$ are coprime, $18$ divides $x+5$. Write $x+5=18t$; substitution then gives $y-2=-7t$. Conversely these values satisfy the equation for every integer $t$. Hence all solutions are

Let $u,v,w$ be the consecutive primitive toric ray vectors around the compact invariant curve $F=F_v$. Smoothness gives oriented determinants $\det (u,v)=\det (v,w)=1$, hence $u+w=bv$ for an integer $b$. Choose an algebraic torus character $m$ with $⟨m,u⟩=0$ and $⟨m,v⟩=1$. The principal divisor on a toric variety has coefficient one at $F$, coefficient $b$ at $F_w$, and zero at $F_u$. The other invariant curves do not meet $F$, while each adjacent one meets it transversely once. Intersecting this principal divisor with the proper curve $F$ gives $0=F^2+b$. This proves the self-intersection formula for a toric surface divisor even when the ambient surface is not complete.

If $F^2=-1$, then $b=1$ and $v=u+w$. The vectors $u,w$ form a lattice basis since $\det (u,w)=1$, and their toric cone is the union of the two toric cones adjacent to $v$. Deleting $v$ is consequently a smooth toric fan coarsening. Its inverse is precisely the toric blowup at a torus-fixed point, obtained by inserting the sum of the two primitive basis vectors. Conversely, that insertion gives $u+w=v$, and hence algebraic self-intersection $-1$. Thus the toric contraction of a minus-one curve satisfiesFor the cyclic quotient description, first take a strongly convex toric cone of dimension two. Write its primitive boundary vectors as $a,b$ and put $N_0=\mathbb{Z}a+\mathbb{Z}b$, $r=[N:N_0]$. Since $a$ is primitive, extend it to a basis of $N$ and write $b=ua+rc$ with $\gcd (u,r)=1$. Thus $N/N_0$ is cyclic of order $r$. In the lattice $N_0$, the toric cone is smooth and its toric variety is ${\mathbb{A}}^2$. Passing to the larger lattice $N$ takes the finite quotient whose invariant monomials are precisely those in the smaller dual lattice $M=N^{\ast }\subset N_0^{\ast }$. Relative to the two boundary coordinates, $c=(b-ua)/r$, so a generator acts with weights $(-u,1)$ modulo $r$. Replacing that generator by a suitable power makes the first weight one and the second some $q$ with $0<q<r$ and $\gcd (q,r)=1$. Therefore, for the singular case,The cyclic quotient surface singularity can equivalently be described by the first-quadrant toric cone inIndeed its coordinate ring is $k[x^i{y}^j:i,j\ge 0,i+qj\equiv 0(\mathrm{mod}r)]=k[x,y{]}^{{\mu }_r}$. Characteristic zero ensures the stated ordinary finite-group quotient interpretation.

The restriction to singular toric cones of dimension two is necessary for $r>1$. A smooth toric cone has $r=1$ and gives ${\mathbb{A}}^2$ with the trivial quotient. A toric cone of dimension one gives ${\mathbb{A}}^1\times k^{\ast }$, and the zero toric cone gives $(k^{\ast }{)}^2$. These latter surfaces cannot be a quotient of the displayed kind, since they have nonconstant invertible regular functions, whereas $k[x,y{]}^{{\mu }_r}$ has only constant units. Thus the blanket affine-surface wording requires these separate cases.

For the singular case, compute the negative continued fraction by the ceiling form of the Euclidean algorithm. Start with $a_0=r$, $a_1=q$, and, while $a_i>0$, setThen $0\le a_{i+1}<a_i$, so the process terminates at $a_{s+1}=0$. The gcd is unchanged at each step, hence $a_s=1$. Since $a_{i-1}>a_i>0$, every $b_i\ge 2$. Rearranging the recurrence givesNow define lattice vectorsTo verify this Hirzebruch–Jung resolution algorithm, write $v_i=(p_i,a_i)/r$ with $p_0=0$, $p_1=1$ and $p_{i+1}=b_i{p}_i-p_{i-1}$. Induction gives $a_i\equiv q{p}_i(\mathrm{mod}r)$, so $v_i\in L$. It also gives $p_i{a}_{i+1}-a_i{p}_{i+1}=-r$. Thus every adjacent pair has absolute determinant $1/r$, the covolume of $L$, and is a basis of $L$. The $p_i$ increase strictly, while the $a_i$ decrease to zero, so these toric rays occur in order inside the first quadrant. At termination, $a_s=1$ and the determinant identity gives $p_{s+1}=r$, hence $v_{s+1}=(1,0)$. All boundary and inserted vectors are primitive because they occur in lattice bases.

Subdivide the quadrant by $v_1,\dots ,v_s$. Every resulting toric cone is smooth by the smoothness criterion for a toric variety, and the fan subdivision gives a proper birational toric morphism, hence a resolution. Each interior toric ray has a complete one-dimensional star, so its exceptional curve of a surface resolution is ${\mathbb{P}}^1$. The recurrence yieldsThis proves minimality: no exceptional curve of a surface resolution can be contracted to a smooth point by the Castelnuovo contraction criterion. There is also a direct toric fan check. For fixed $i$, the determinants of $v_i$ with $v_{i+h}$, measured in units of the lattice covolume, satisfy the same recurrence with coefficients at least two and initial values zero and one. They are at least $h$. Omitting any intervening toric ray therefore leaves a toric cone of determinant at least two, so no nontrivial coarsening is smooth. Thus this is the minimal resolution of a cyclic quotient surface singularity.

If all exceptional algebraic self-intersections are $-2$, all $b_i=2$ and induction gives $[2,\dots ,2{]}^{-}=(s+1)/s$. Since $r,q$ are coprime, this forces $r=s+1$, $q=s$. Conversely $r/(r-1)$ has exactly $r-1$ coefficients equal to two. ThereforeFor the final toric fan, the minimal smooth fan subdivision of the toric cone from $(0,1)$ to $(r,1)$ inserts the toric rays $(j,1)$ for $1\le j<r$. Adjacent determinants have absolute value one, and $(j-1,1)+(j+1,1)=2(j,1)$, so its inserted curves have algebraic self-intersection $-2$ and it is the minimal fan subdivision just described. The second original toric cone, from $(r,1)$ to $(1,0)$, is already smooth.

Write $v_j=(j,1)$ and $e=(1,0)$. In the resolved toric fan, the rightmost interior toric ray obeys $v_{r-1}+e=v_r$, so its curve has algebraic self-intersection $-1$ and can be blown down to a smooth point. After deleting it, the same relation $v_{r-2}+e=v_{r-1}$ applies to the new rightmost interior toric ray. Continue deleting $v_r,v_{r-1},\dots ,v_1$ in that order. Each deletion is the inverse of a toric blowup at a torus-fixed point. The last toric fan has only the quadrant toric cone and defines ${\mathbb{A}}^2$. ConsequentlyAll maps induce the identity on the dense algebraic torus, so this composite is the same morphism as $X_{{\Sigma }^{\prime }}\to X_{\Sigma }\to {\mathbb{A}}^2$. The intermediate smooth toric fans need not include the singular toric fan $\Sigma$.

Take $\Gamma ={\mathrm{PSL}}_2(\mathbb{Z})$ as a subgroup of ${\mathrm{PSL}}_2(\mathbb{C})$. It is discrete because representatives have integer entries, so a bounded set of matrices contains only finitely many such representatives, modulo the two choices of sign. It is finitely generated byThe Euclidean algorithm on the first column of an integer determinant-one matrix reduces it using these two transformations, proving the generation statement.

It is non-elementary. The powers of $T$ move an interior upper-half-space point towards $\infty$, so $\infty \in \Lambda (\Gamma )$. Conjugating $T$ by $S$ gives a parabolic with fixed point $0$, and conjugating that parabolic by $T$ gives one with fixed point $1$. Their interior orbits approach those respective points. Thus $0,1,\infty$ are three distinct points in the Kleinian limit set.

However $S^2=1$ in the projective group, and $S$ is a nonidentity elliptic Möbius transformation fixing the hyperbolic geodesic with boundary endpoints $i,-i$. It is a half-turn around that axis. Near an ordinary point of the axis, quotienting identifies the transverse angle modulo $\pi$, giving cone angle $\pi$ instead of $2\pi$. The elliptic stabilizer obstruction to a hyperbolic manifold quotient therefore givesThe obstruction is the nonfree action, not finite generation or elementary behavior. An underlying topological quotient can still be a manifold; the conical quotient metric is what prevents this example from being a hyperbolic manifold quotient.