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 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].

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]

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.

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$.

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].

A pair of positive integers $(a,b)$ with $ab=n$ for a specified positive integer $n$. Pairing each divisor $a$ with $n/a$ gives $\tau (n)/2$ unordered factor pairs for nonsquare $n$, and $(\tau (n)+1)/2$ for a perfect square, where $\tau (n)$ is the divisor function.

A Fermat number is the positive integer $F_n=2^{2^n}+1$, indexed by a nonnegative integer $n$. The first five are $3,5,17,257,65537$, all prime numbers; the next is the composite number $F_5=4294967297=641\cdot 6700417$. This family offers a compact lesson in number theory: a very persuasive finite pattern can fail, while an exact divisibility relation settles a gigantic case with little computation.

Why does the exponent itself have the form $2^n$? Suppose $m=ab$ is a positive integer with an odd integer factor $b>1$. The polynomial factorization $x^b+1=(x+1)(x^{b-1}-x^{b-2}+\cdots -x+1)$ shows that $2^a+1$ is a proper divisor of $2^m+1$. Consequently, if $2^m+1$ is a prime number, $m$ must be a power of two. That is a necessary condition, rather than a promise that the surviving candidates are prime.

The Fermat number product identity makes distinct Fermat numbers coprime integers. Thus every term has a prime factor absent from all earlier terms, whether or not that term is itself a prime number. This gives an explicit route to infinitely many different prime numbers, without establishing that infinitely many terms of this particular sequence are prime. Meanwhile the prime divisor of a Fermat number criterion filters possible factors through a small multiplicative order calculation.

The family also links arithmetic to Euclidean geometry: a constructible regular polygon can have a number of sides equal to a power of two times a product of distinct Fermat primes. The Gauss-Wantzel theorem gives the precise criterion. For instance, $15=3\cdot 5$ and $17$ qualify, but $9=3^2$ does not. The word "distinct" matters. Carl Pomerance describes this connection in Primality testing: then and now by Carl Pomerance (slide 18).

Historically, Leonhard Euler records Pierre de Fermat's proposed primality pattern, then refutes it by finding the factor $641$ of $F_5$. His paper was presented in 1732 and published in 1738; those are different events, not competing dates for one publication.^[ref]

A short modern check needs only two representations of $641$:In modular arithmetic these give $5^4{2}^{28}\equiv 1$ and $5^4\equiv -2^4(\mathrm{mod}641)$. Substitution yields $2^{32}\equiv -1(\mathrm{mod}641)$, so $641\mid F_5$. This verifies the factor directly; it does not claim to reconstruct Euler's search process.

A Fermat prime is a Fermat number that is also a prime number:The defining form alone does not imply primality. For example, $65537$ is a Fermat prime, while $4294967297$ is a Fermat number with proper divisors. For $k\ge 1$, every Fermat prime is one modulo four and two modulo three. Pépin's test gives an exact primality testing criterion for these candidates, rather than relying on their form.

Every integer $n>1$ is a product of prime numbers, uniquely up to reordering the factors. More precisely, there are unique distinct prime numbers $p_1<\cdots <p_r$ and unique positive integer exponents $a_1,\dots ,a_r$ such thatIn the header's displayed form, $v_p(n)$ is the prime valuation, the exponent of $p$ in this prime factorization; it is zero when $p$ does not divide $n$. Reordering or regrouping the prime factors does not give a different prime factorization.

For $360$, repeated division gives $360/2=180$, $180/2=90$, $90/2=45$, then $45/3=15$, $15/3=5$, and $5/5=1$. ThusIts nonzero prime valuations are $v_2(360)=3$, $v_3(360)=2$ and $v_5(360)=1$. Recording only the distinct prime factors $2,3,5$ would lose the difference between $30$ and $360$.

This turns divisibility into coordinatewise comparison of nonnegative exponents. A positive divisor of $360$ chooses an exponent from $0,1,2,3$ for $2$, from $0,1,2$ for $3$, and from $0,1$ for $5$, giving $4\cdot 3\cdot 2=24$ positive divisors. The greatest common divisor takes the smaller exponent at each prime number; the least common multiple takes the larger. The theorem is a structural description, not an assertion that finding the factors of every large integer is computationally easy.

In general, for positive integers $d,n$, the exact divisibility criterion isFor example, $72=2^3\cdot 3^2$ divides $360$, with quotient $5$, whereas $48=2^4\cdot 3$ does not: it requires four factors of two, but $360$ supplies only three. Both use only prime factors of $360$, so membership in that list alone does not establish divisibility. Every positive divisor of $360$ is uniquely $2^a{3}^b{5}^c$ with $0\le a\le 3$, $0\le b\le 2$, $0\le c\le 1$. Sorted, all 24 positive divisors areThus the divisor function gives $\tau (360)=(3+1)(2+1)(1+1)=24$. These include divisors that are composite numbers, as well as the prime factors and one.

For another positive integer $m$, the prime valuations give exact formulas for the greatest common divisor and least common multiple:With $n=360$ and $m=84=2^2\cdot 3\cdot 7$, their prime valuations at $2,3,5,7$ are $(3,2,1,0)$ and $(2,1,0,1)$. The smaller exponents give $(2,1,0,0)$, and the larger give $(3,2,1,1)$, henceIndeed, $360/12=30$, $84/12=7$, $2520/360=7$ and $2520/84=30$. The same rules also explain $\gcd (n,m)\mathrm{lcm}(n,m)=nm$: the smaller and larger exponents sum to the two original exponents. Here $12\cdot 2520=360\cdot 84=30240$.

The useful change of viewpoint is that multiplication becomes addition of prime valuations, $v_p(nm)=v_p(n)+v_p(m)$, and divisibility becomes comparison. Many different-looking calculations therefore share one representation. The prime valuations are coordinates for multiplication, rather than digits in positional notation: they do not turn ordinary addition of integers into coordinatewise addition.

Different intermediate splits lead to the same prime ingredients. Starting with $360=36\cdot 10$ gives $36=6\cdot 6$ and $10=2\cdot 5$; starting with $360=8\cdot 45$ gives $8=2\cdot 4$ and $45=5\cdot 9$. Continuing to split the composite numbers produces the same multiset of prime factors: three twos, two threes, and one five. The factorization tree records choices in the calculation, while the prime factorization records the invariant result.

The proof outline explains the uniqueness. Existence follows by splitting a composite number into smaller factors until only prime numbers remain. For uniqueness, Euclid's lemma says that a prime factor of one product must divide one factor of any other prime product equal to it. That factor must be the same prime number; cancel it and repeat. The crucial divisibility step appears in Book VII, Proposition 30 of Euclid's Elements. ^[ref]

The ancient text supplies specific precursors to the modern statement: Book VII, Proposition 31 establishes that every composite number has a prime factor, and Book IX, Proposition 14 excludes any new prime factor from the least common multiple of given prime numbers. These are the propositions being cited, rather than the complete modern exponent formulation of the fundamental theorem of arithmetic. ^{[ref] [ref]}

Excluding one from the prime numbers keeps uniqueness meaningful: otherwise $360=2^3\cdot 3^2\cdot 5=1\cdot 2^3\cdot 3^2\cdot 5=1\cdot 1\cdot 2^3\cdot 3^2\cdot 5$ would give different collections of supposed prime factors. For $n=1$, the natural convention is the empty product, equal to one, with no prime factors and all prime valuations zero.

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.

A positive integer whose divisor count strictly exceeds that of every smaller positive integer. A record scan maintains the largest earlier value of the divisor function and emits exactly candidates exceeding it. Equality does not create a new record; the first candidate is handled by a zero initial record.

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.

An integer multiple of an integer $d$ is a product $dk$ with $k$ an integer; equivalently, $d$ is a divisor of that product. The integer multiples of $12$ are $\dots ,-24,-12,0,12,24,\dots$. Zero is an integer multiple of every integer, and the only integer multiple of zero is zero. Shared positive integer multiples lead to the least common multiple.

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]