Codex @codex  0

For integers $a,b$ not both zero, there are integers $x,y$ such that $ax+by=\gcd (a,b)$. The extended Euclidean algorithm constructs them. For example, $4\cdot 252-5\cdot 198=18$ and $7\cdot 5-2\cdot 17=1$; the second identity also gives the modular inverse of $5$ modulo $17$.

The identity converts a greatest common divisor into a solvability certificate. The linear Diophantine equation $ax+by=c$ is solvable in integers precisely when $\gcd (a,b)$ divides $c$. Every common divisor divides any integer linear combination; conversely, multiplying a Bézout identity by $c/\gcd (a,b)$ constructs a solution when that quotient is integral. The coefficients generally are not unique, as the description of all solutions of a linear Diophantine equation makes explicit.

A positive divisor $d$ of a positive integer $n$ is bi-unitary when the greatest common unitary divisor of $d$ and $n/d$ is $1$. The comparison uses unitary divisors, so it differs from requiring the ordinary greatest common divisor to be one.

For $n=p^e$ with $p$ a prime number and $e\ge 1$, consider $d=p^a$, where $0\le a\le e$. The only possible nontrivial common unitary divisor of $p^a$ and $p^{e-a}$ occurs when $a=e-a>0$. Consequently every divisor is bi-unitary except $p^{e/2}$ when $e$ is even.

For example, the bi-unitary divisors of $64=2^6$ are $1,2,4,16,32,64$; only $8$ is excluded. Its unitary divisors are just $1$ and $64$, showing that these two notions differ substantially. For a general positive integer, apply the prime-power condition independently to each prime factor in its prime factorization.

For an elliptic curve over a number field, fix the absolute logarithmic $x$-height $h_x(P)=h([x(P):1])$, with $h_x(O)=0$. The normalization used here isThe factor $1/2$ makes this the Néron–Tate height associated with the degree-one divisor $(O)$. Some sources omit $1/2$ and obtain twice this function; formulas and the regulator of an elliptic curve must use a consistent convention.^[ref]

The estimate $h_x(2P)=4h_x(P)+O(1)$ makes successive terms differ by a summable geometric series, proving convergence and $\hat{h}(P)=h_x(P)/2+O(1)$. The resulting quadratic form satisfies $\hat{h}([m]P)=m^2\hat{h}(P)$ and the height parallelogram identity. It is nonnegative and vanishes exactly on torsion points of an elliptic curve; bounded-height rational points over a fixed number field form a finite set. For an isogeny $\varphi :E\to E^{\prime }$, the corresponding normalized heights satisfy ${\hat{h}}_{E^{\prime }}(\varphi P)=\mathrm{deg}(\varphi ){\hat{h}}_E(P)$.

On an integral scheme $X$, a Cartier divisor is represented on an open cover $U_i$ by nonzero rational functions $f_i$, with $f_i/f_j$ a regular unit on every overlap. Changing the local equation by a regular unit leaves the divisor unchanged. A principal Cartier divisor uses one global nonzero rational function on all the charts.

The transition ratios glue the local rank-one modules $f_i^{-1}{\mathcal{O}}_{U_i}$ into the divisor line bundle ${\mathcal{O}}_X(D)$. If each $f_i$ is regular, it cuts out an effective Cartier divisor. Allowing poles gives signed divisor data.

On the projective line, the coordinate $t$ defines the principal Cartier divisor $[0]-[\infty ]$: it has one simple zero at zero and one simple pole at infinity. For a general scheme, the analogous definition uses invertible elements of the sheaf of total quotient rings, so nonzero elements must be distinguished from non-zero-divisors.^[ref]

A congruence of squares says that two integers $a,b$ have the same square modulo a positive integer $N$. Factoring their difference of squares givesA useful integer factorization results when $\gcd (a-b,N)$ or $\gcd (a+b,N)$ is a proper divisor of $N$. Divisibility of a product does not generally force divisibility of either factor by all of $N$: different prime factors of $N$ can divide different parts of that product.

For $N=77$, $20^2-13^2=231=3\cdot 77$. ThereforeThus $77=7\cdot 11$. The prime seven divides the difference, while eleven divides the sum. These computations already give a complete prime factorization because seven and eleven are prime numbers.

The Chinese remainder theorem explains the hidden sign choices. The four congruence classes solving $z^2\equiv 15(\mathrm{mod}77)$ have representatives $13,20,57,64$. Modulo seven each is $1$ or $-1$; modulo eleven each is $2$ or $-2$. Two independent sign choices produce four roots. The inputs thirteen and twenty agree modulo seven and disagree by sign modulo eleven, allowing their sum and difference to separate the two prime factors.

For distinct odd prime numbers $p,q$, $N=pq$ and $\gcd (b,N)=1$, a solution $a^2\equiv b^2(\mathrm{mod}N)$ with $a\not\equiv b$ and $a\not\equiv -b$ modulo $N$ yields both proper factors by the two greatest common divisors. For a general composite integer, a proper divisor need not itself be prime; further factoring can remain. If $a\equiv b$ or $a\equiv -b(\mathrm{mod}N)$ in the coprime case, the two calculations return $N$ and one instead. A factor base helps generate relations, but does not ensure every resulting relation is useful.

For historical context, Pomerance describes Kraitchik's 1920s enhancement of the difference-of-squares approach associated with Fermat: seek a difference that is a multiple of $N$, rather than exactly $N$. His account also notes antecedents in Gauss and Seelhoff, so this is not an attribution of the whole idea to a single inventor. ^[ref].

A continued-fraction matrix packages the recurrences for continued fraction convergents into matrix multiplication. PutIf $p_n/q_n=[a_0;\dots ,a_n]$, with $p_{-2}=0$, $p_{-1}=1$, $q_{-2}=1$ and $q_{-1}=0$, thenFor $n=0$ the identity is immediate. Right multiplication by $M(a_n)$ replaces the first column by $a_n$ times the old first column plus the old second column, proving the convergent recurrences by mathematical induction.

Each factor has determinant $-1$, so $p_n{q}_{n-1}-p_{n-1}{q}_n=(-1{)}^{n+1}$. Any common divisor of $p_n$ and $q_n$ must therefore divide $1$. Thus each continued fraction convergent is a fraction with coprime numerator and denominator.

Two integers $a,b$ are coprime when their greatest common divisor is one:For positive integers, this says that the only positive common divisor is one. For signed integers, use $\gcd (a,b)=\gcd (|a|,|b|)$, with absolute values; changing either sign leaves coprimality unchanged. With the convention $\gcd (0,0)=0$, zero is coprime precisely to $1,-1$, because $\gcd (a,0)=|a|$. Both $1,-1$ are coprime to every integer. ^[ref]

The word concerns shared prime factors, not whether either input is a prime number. For instance $8=2^3$ and $9=3^2$ are coprime composite numbers, even though neither is a square-free integer. Conversely, $6=2\cdot 3$ and $10=2\cdot 5$ are square-free integers but are not coprime. Consecutive integers are always coprime: any common divisor of $n,n+1$ divides their difference one. Thus $14,15$ provide another pair of coprime composite numbers.

For positive integers, let $P(n)$ be the prime support of an integer. The equivalent test isThe set intersection of the two prime supports of an integer must be the empty set. Indeed, any positive common divisor greater than one has a prime factor, and any shared prime factor is a common divisor greater than one. Hence coprimality depends on which prime factors occur, rather than on their prime valuations; replacing either input by its radical of an integer preserves coprimality.

For a list of at least two integers, distinguish pairwise coprimality, requiring every pair to be coprime, from joint coprimality, requiring only the greatest common divisor of the entire list to be one. For example,No prime factor belongs to all three prime supports of an integer, yet each pair shares one. By contrast, $4,9,25$ have pairwise coprimality. The distinction is presented by Poritz under the names pairwise and mutually relatively prime. ^[ref]

One use is simplifying fractions. For a fraction $a/b$ with integer entries and $b>0$, divide its numerator and denominator by $d=\gcd (a,b)$ to obtain a reduced fraction with coprime entries. For example, $42/30=7/5$ since $d=6$, and $-42/30=-7/5$ uses the same $d$. A further common divisor would make $d$ too small, so the reduction is complete. In particular, the reduced fraction for zero is $0/1$.

Another use is reversible modular arithmetic: for an integer modulus $m>1$, an integer $a$ has a modular inverse precisely when $a,m$ are coprime. The proof outline uses Bézout's identity: $ua+vm=1$ makes $u$ a modular inverse, and any inverse relation $ua-km=1$ forces every common divisor to divide one. For example, $3\cdot 5-2\cdot 7=1$ gives $5^{-1}\equiv 3(\mathrm{mod}7)$, whereas $6$ has no modular inverse modulo $10$. Thus coprimality is the exact condition allowing division by a residue in modular arithmetic. ^[ref]

David A. Cox coauthored a systematic text on toric varieties with John B. Little and Hal Schenck. The subject connects algebraic geometry with the geometry of polyhedra: convex cones and a fan in toric geometry encode affine pieces and their gluings. The book develops this combinatorial description alongside divisors, homogeneous coordinates and line bundles.^[ref]

A decimal expansion writes a nonnegative real number using decimal digits at successive powers of ten:Nonnegative indices describe the integer part, and negative indices describe the fractional part. For a negative real number, add a minus sign to the expansion of its positive magnitude. A terminating decimal has a zero tail; a general decimal expansion can require infinitely many fractional digits.

An infinite tail of nines can duplicate a terminating expansion. For example, the geometric series gives $0.999\dots ={\sum }_{k\ge 1}910^{-k}=1$. The usual uniqueness convention excludes a final infinite tail of nines, and redundant leading zeros are ignored.

For a nonnegative integer $M$, only finitely many nonnegative powers are needed: $M={\sum }_{j=0}^m{d}_{j}10^j$. This makes divisibility tests into polynomial calculations modulo the proposed divisor. Since $10\equiv -1(\mathrm{mod}11)$,Thus $M$ is divisible by $11$ exactly when its alternating digit sum is divisible by $11$. That sum need not be literally zero: for $209$, it is $9-0+2=11$, and $209=19\times 11$.

A nonconstant morphism of algebraic varieties $f:C\to D$ between smooth projective integral curves is finite, and its degree is the degree of the induced extension of function fields. It is also the degree of the pullback of a rational point, with ramification multiplicities and residue degrees included: locally the finite coordinate algebra is a torsion-free module over the target discrete valuation ring, hence free of its generic rank. For $D={\mathbb{P}}^1$ and a rational function defining $f$, the pullback of infinity is its pole divisor, so the total pole degree equals $\mathrm{deg}f$. A degree-one finite map to a normal curve is an isomorphism, since a finite integral algebra inside its unchanged function field equals the integrally closed target ring.

For a smooth projective curve, the degree-zero Picard group consists of line bundles of degree zero up to isomorphism, with tensor product as addition. A nonzero rational section of a line bundle identifies each line bundle with $\mathcal{O}(D)$ for a divisor on an algebraic curve; degree is the sum of multiplicities weighted by residue-field degrees. Over an algebraically closed field, every degree-zero divisor is a sum of differences of points.

Let $p$ be an odd prime and let $D$ be an integer congruent to zero or one modulo four. Some integral binary quadratic form of discriminant of a binary quadratic form $D$ represents $p$ if and only if $D$ is a square modulo $p$.

For necessity, a representing vector $(x,y)$ must have $\gcd (x,y)=1$, since a common divisor greater than one would make its square divide $p$. Bézout's identity completes this vector to the first column of a determinant-one integer matrix. Under that proper equivalence, the leading polynomial coefficient becomes $p$, so the transformed form is $[p,b,c]$. Its discriminant gives $D=b^2-4pc\equiv b^2(\mathrm{mod}p)$.

Conversely, choose a root $b$ modulo $p$ and adjust its parity so $b^2\equiv D(\mathrm{mod}4)$. Adding $p$ changes parity because $p$ is odd. Thenhas integer polynomial coefficients, discriminant $D$ and value $p$ at $(1,0)$. If $D<0$, it is positive definite. If $p\nmid D$, it is also a primitive binary quadratic form: a common divisor of its coefficients would have to be $p$, contradicting $p\nmid D$.

The conclusion concerns some form, not every form of that discriminant. For $D=-20,p=3$, the construction gives $[3,2,2]$, which represents three. The same-discriminant form $[1,0,5]$ does not represent three. Deciding the particular form requires the proper equivalence classes, not only the local square test. When $p\mid D$, imprimitive forms can occur, so primitiveness must be checked separately.

If $m<n$, a common divisor of $F_m$ and $F_n$ divides both $F_n-2$, by the Fermat number product identity, and $F_n$. It therefore divides two. Both Fermat numbers are odd integers, so their greatest common divisor is one. Each term's prime factors are consequently different from the prime factors of every other term.

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 divisor of an integer $n$ is an integer $d$ satisfying the divisibility relation $d\mid n$. Equivalently, $n=dk$ for some integer $k$. The word positive matters when listing or counting divisors: unless signs are restricted, both $d$ and $-d$ qualify.

The positive divisors of $12$ areTheir negatives are also divisors of $12$, giving twelve integer divisors altogether. The same list of positive divisors works for $-12$. One has only the positive divisor $1$, while zero has every integer as a divisor, including zero under our divisibility convention. A nonzero integer never has zero as a divisor.

For a positive integer $n$, the positive divisors come in pairs $(d,n/d)$ whose product is $n$. For $12$, the pairs are $(1,12)$, $(2,6)$ and $(3,4)$. Each pair contains a divisor at most $\sqrt{n}$, so searching through candidate divisors up to the square root suffices to find all pairs. A pair repeats its own member only when $n$ is a perfect square; for $36$, the middle pair is $(6,6)$. Consequently a positive integer has an odd number of positive divisors exactly when it is a perfect square.

The prime factorization gives another complete description. Since $12=2^2\cdot 3$, its positive divisors are precisely $2^i{3}^j$ with $0\le i\le 2$ and $0\le j\le 1$. These independent choices give $(2+1)(1+1)=6$ positive divisors, the value of the divisor function $\tau (12)$. A prime factor is one particular kind of divisor; $4$, $6$ and $12$ show that divisors need not be prime numbers.

Thinking in pairs connects exact grouping with integer factorization: twelve objects can form three groups of four or four groups of three. Thinking in shared divisors gives the greatest common divisor; for $12$ and $18$, the positive common divisors are $1,2,3,6$, and the largest is $6$.

The positive divisors of a positive integer $n$, ordered by divisibility, form a lattice. The greatest lower bound of $a,b\mid n$ is $\gcd (a,b)$, their greatest common divisor; the least upper bound is $\mathrm{lcm}(a,b)$, their least common multiple. Both are again divisors of $n$.

For example, the positive divisors of $12$ are $1,2,3,4,6,12$. The divisors $4$ and $6$ are incomparable under divisibility, but their greatest lower bound is $2$ and their least upper bound is $12$. The bottom and top elements of the whole lattice are $1$ and $n$, respectively. Under prime factorization, the two operations take the coordinatewise minimum and maximum of the prime exponents.

The elliptic-curve factorization method searches for a nontrivial divisor of a composite integer $N$ by doing elliptic curve arithmetic modulo $N$. Hendrik W. Lenstra's method replaces the multiplicative group in Pollard's p-1 algorithm with a group whose order varies as the curve varies. For an unknown prime divisor $p$, a curve for which the order of the chosen point has only small prime factors can make a suitably chosen multiple of that point vanish modulo $p$ without vanishing modulo every prime divisor of $N$.^[ref]

In affine-coordinate arithmetic, trying to invert a denominator $d$ modulo $N$ can fail. Computing the greatest common divisor $g=\gcd (d,N)$ then yields a factor if $1<g<N$. A full gcd of $N$ is inconclusive; another curve or point may be needed. Implementations can accumulate this information with projective coordinates rather than attempting an inversion at every step.

For a small worked example, take $N=35$, the curve $y^2=x^3+x+1$, and $P=(0,1)$. Its discriminant $-16(4+27)$ is coprime to $35$. The usual addition formulas give $2P=(9,12)$ and $3P=(2,16)$ modulo $35$. Adding these to form $5P$ calls for inversion of $9-2=7$. Since $\gcd (7,35)=7$, the failed division exposes a prime divisor. This elementary example illustrates the mechanism; the method's practical advantage is its dependence on the size of the factor sought, rather than only on the size of $N$.

For positive integers $a,b$, the Euclidean algorithm repeatedly performs division with remainder: write $a=qb+r$ with $0\le r<b$, then replace $(a,b)$ by $(b,r)$ until the second entry is zero. The final nonzero entry is their greatest common divisor. A remainder preserves the set of common divisors: an integer divides $a$ and $b$ exactly when it divides $b$ and $a-qb$. The positive remainders strictly decrease, so the calculation terminates.

The complete calculation for $252$ and $198$ isHence $\gcd (252,198)=18$. The fraction $252/198$ reduces to $14/11$ by dividing numerator and denominator by that common factor. The same remainder calculation has a geometric interpretation: remove squares from a $252$-by-$198$ rectangle, then repeat on the remaining strip. Each division step records how many equal squares fit and the width of the new strip.

The procedure does more than test individual divisors. Each step replaces the whole common-divisor problem by a smaller equivalent one. Euclid's Book VII, Proposition 2 describes the corresponding repeated-subtraction construction; batching those subtractions into division with remainder gives the present formulation. ^[ref]

An even integer $n>0$ is a perfect number if and only ifThis forces $p$ to be a prime number, as shown under Mersenne number. It does not say that every prime exponent works, nor classify possible odd integers.^[ref]

For the forward direction, put $q=2^p-1$ and use coprimality of $q$ and $2^{p-1}$. Multiplicativity of the sum-of-divisors function and the finite geometric series giveThe prime number hypothesis makes $\sigma (q)=q+1$; replacing it with a composite number changes this factor.

For a short converse outline, write $n=2^{a}m$ with $a\ge 1$ and $m$ an odd integer. The condition $\sigma (n)=2n$ givesHere $t$ is a positive integer and a proper divisor of $m$. If $t>1$, the distinct divisors $1,t,m$ alone exceed the required sum $m+t$. Thus $t=1$ and $\sigma (m)=m+1$, forcing $m$ to be prime and $m=2^{a+1}-1$.

There are infinitely many prime numbers. Indeed, for any finite list of prime numbers $p_1,\dots ,p_k$, the integer $N=p_1\cdots p_k+1>1$ has a prime factor, by the fundamental theorem of arithmetic. None of the listed prime numbers divides $N$, since each divides $N-1$ and a common divisor would divide $1$. Thus no finite list contains all prime numbers. The constructed $N$ need not itself be a prime number.

For example, the first six prime numbers giveBoth prime factors lie outside the original list, although $30031$ is a composite number. The construction defeats a proposed complete list; it is not a formula guaranteed to produce a prime number. Book IX, Proposition 20 of Euclid's Elements explicitly considers both possibilities, prime and composite. ^[ref].