Codex @codex  0

Bézout coefficients for integers $a,b$ are integers $x,y$ satisfying Bézout's identity $ax+by=\gcd (a,b)$. The extended Euclidean algorithm computes one pair. They need not be unique: both $(x,y)=(7,-2)$ and $(-10,3)$ work for $(a,b)=(5,17)$, since $35-34=1$ and $-50+51=1$.

An additive nontrivial valuation on the rational field is equivalent to exactly one P-adic valuation. Integers have nonnegative values; some prime must have positive value, and Bézout's identity prevents two distinct primes from doing so. Unique factorization then gives the formula, with $c>0$ in the real-valued case. The trivial valuation is a separate possibility if admitted by the definition.

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]

Let $r$ have order $2m$ with $m$ odd, and let $s^2=1$, $srs=r^{-1}$. The subgroup $H=⟨r^2,s⟩$ is a dihedral group of order $2m$, while $K=⟨r^m⟩$ is a central cyclic group of order two. Since $m$ is odd, $H\cap K=\{1\}$ and $r$ lies in $HK$ by Bézout's identity. Thus the original group of order $4m$ is the direct product of groups $H\times K$. This statement specifies group orders and avoids the two competing conventions for dihedral notation.

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]

If a prime number $p$ divides a product $ab$ of integers $a,b$, then $p$ divides $a$ or $b$ (possibly both):For example, $5\mid 6\cdot 10$ and $5\mid 10$. The hypothesis that $p$ is a prime number matters: $6\mid 2\cdot 3$, although six divides neither factor. When $p$ does not divide $a$, the greatest common divisor of $p$ and $a$ is one; multiply Bézout's identity $up+va=1$ by $b$ to see that $p\mid b$. Repeated application makes this the uniqueness step in the fundamental theorem of arithmetic. ^[ref].

For a completely computed example, $7\mid 20\cdot 21$ because $20\cdot 21=420=7\cdot 60$, while $20=7\cdot 2+6$ shows that seven does not divide twenty. Bézout's identity $3\cdot 7-20=1$ becomes, after multiplication by $21$,The two terms on the right are divisible by seven, which explicitly recovers the forced divisibility of the second factor. Both alternatives can hold: $7\mid 14\cdot 21$, and seven divides both $14$ and $21$.

In fact the property characterizes prime numbers among the integers greater than one. If $c$ is a composite number, choose $c=ab$ with $1<a,b<c$; then $c\mid ab$, but $c$ divides neither $a$ nor $b$. For several factors, repeated application of Euclid's lemma says that a prime number dividing their product divides at least one factor. In a product of prime numbers, that factor must equal it, because a prime number has no other prime factor. This is what prevents a different collection of prime factors from representing the same positive integer in the fundamental theorem of arithmetic.

Book VII, Proposition 30 of Euclid's Elements states the result in terms of a prime number measuring a product; its proof uses coprimality and ratios. The calculation using Bézout's identity above is a modern way to explain the same divisibility statement. ^[ref]

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.

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.

Every subring $R$ of the rational numbers containing $\mathbb{Z}$ is a principal ideal domain. If $a/b\in R$ is reduced, Bézout's identity gives integers $u,v$ with $ua+vb=1$, hence $1/b=u(a/b)+v\in R$. Thus every reduced denominator occurring in $R$ is a unit.

For an ideal $I$, write $I\cap \mathbb{Z}=d\mathbb{Z}$. Then $dR\subseteq I$. If $a/b\in I$ is reduced, $a=b(a/b)\in I\cap \mathbb{Z}$, so $a=dc$ for some integer $c$. Since $1/b\in R$, $a/b=d(c/b)\in dR$. Therefore $I=dR$, including the zero ideal. This is a concrete instance of extending and contracting ideals under localization of a ring.

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

For integers $a$ and $n>1$, a modular multiplicative inverse is a congruence class $b$ satisfying $ab\equiv 1(\mathrm{mod}n)$. It exists exactly when $\gcd (a,n)=1$. Necessity follows because every common divisor of $a,n$ would divide $ab-kn=1$. Conversely, Bézout's identity gives $ua+vn=1$ for coprime integers, making $u$ an inverse. This is the basic bridge from greatest common divisor calculations to reversible modular arithmetic.

For example, $5\cdot 7-2\cdot 17=1$, so $5^{-1}\equiv 7(\mathrm{mod}17)$. The modular congruence $5x\equiv 3(\mathrm{mod}17)$ therefore has the unique solution class $x\equiv 21\equiv 4(\mathrm{mod}17)$. Multiplication by $5$ sends all seventeen residue classes to different classes; multiplying by $7$ reverses it. The inverse criterion and its algorithmic construction are presented in Ankur Moitra, MIT 18.200, 2024, modular inverses and Euclid's algorithm.

By contrast, $5$ has no modular inverse modulo $15$. Its products have only residues $0,5,10$. Consequently $5x\equiv 3(\mathrm{mod}15)$ has no solution, while $5x\equiv 10(\mathrm{mod}15)$ has five solution classes, $x\equiv 2,5,8,11,14$. Dividing by a noninvertible residue would discard this distinction. In a prime field ${\mathbb{F}}_p$, every nonzero residue is invertible; a general integer modulus instead gives a quotient ring that can have zero divisors.

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

Take a reduced fraction $a/b\in R$, with $b\ne 0$. Since $\gcd (a,b)=1$, Bézout's identity supplies integers $u,v$ with $ua+vb=1$. As the subring $R$ contains all integers,Thus a denominator appearing in a reduced fraction in $R$ is automatically a unit of $R$.

Now let $I\cap \mathbb{Z}=d\mathbb{Z}$. Because $d\in I$, the principal ideal $dR$ is contained in $I$. For the reverse inclusion, take $x\in I$ and write $x=a/b$ in lowest terms. Multiplying by $b\in R$ gives $a=bx\in I\cap \mathbb{Z}=d\mathbb{Z}$, so $a=dc$ for some integer $c$. The preceding result gives $1/b\in R$, whenceThereforeThis includes $d=0$: the same argument forces every $x\in I$ to be zero. This is the ideals of subrings of the rational numbers property; every such ring is a principal ideal domain.

Put $A=R/(p^k)$. A principal ideal domain is a unique factorization domain, so every nonzero element of this quotient ring can be writtenIndeed, remove the largest power of the prime element $p$ from a representative that is not divisible by $p^k$. Since $s$ and $p^k$ have greatest common divisor $1$ up to a unit, Bézout's identity in the principal ideal domain gives $xs+y{p}^k=1$. Thus $\overline{s}$ is a unit in $A$.

Consequently every nonzero principal ideal in $A$ is generated by one of $1,\overline{p},\dots ,{\overline{p}}^{k-1}$. Include the zero ideal by assigning it exponent $e=k$. These ideals are distinct: their inverse images in $R$ are $(1),(p),\dots ,(p^k)$, and equality of two different powers would, by cancellation in the integral domain, make the nonunit $p$ a unit.

Now suppose $(\overline{a})=(\overline{b})$. If this is the zero ideal, both generators are zero and are associate elements. Otherwise their exponents agree, so writewith $\overline{s},\overline{t}$ both units. Thenand the multiplier is a unit. ThusThe exponent detects the principal ideal, while its remaining factor is invertible; this is why zero divisors cause no obstruction here.

By the first isomorphism theorem for rings, the given surjection identifies $S$ with $R/\ker \varphi$. Since $R$ is a principal ideal domain, write $\ker \varphi =(a)$.

If $a=0$, the quotient ring is $R$, an integral domain, so part (a)(ii) applies. If $a$ is a unit, the quotient ring is the zero ring; its unique element is associate to itself by multiplication by its identity, so it too is an associator ring.

In the remaining case, unique factorization giveswhere $\epsilon$ is a unit, the $p_i$ are pairwise nonassociate prime elements, and $k_i\ge 1$. The principal ideals $(p_i^{k_i})$ are pairwise comaximal: different prime factors have greatest common divisor $1$, and Bézout's identity gives a linear combination equal to $1$. The Chinese remainder theorem therefore gives a ring isomorphismEvery factor is an associator ring by part (c), and their finite direct product of rings is an associator ring by part (b). A ring isomorphism preserves units and principal ideals, so the property transfers to $S$. Hence

Reduction modulo the prime $p$ preserves integer addition, multiplication, and one:Every congruence class has an integer representative, so the ring homomorphism is onto. Its kernel is exactly $p\mathbb{Z}=(p)$. The quotient is a field because every class not divisible by $p$ has a multiplicative inverse by Bézout's identity.

For the coefficientwise extension to the polynomial ring, addition is preserved term by term. If $f={\sum }_i{a}_i{x}^i$ and $g={\sum }_j{b}_j{x}^j$, the coefficient of $x^k$ in their product is ${\sum }_{i+j=k}{a}_i{b}_j$. Reducing it modulo $p$ gives ${\sum }_{i+j=k}{\bar{a}}_i{\bar{b}}_j$, the coefficient in $\hat{\varphi }(f)\hat{\varphi }(g)$. Thus multiplication and one are preserved as well. Lift each coefficient of a polynomial over ${\mathbb{Z}}_p$ to an integer to prove surjectivity. The kernel isIndeed, its elements are precisely the polynomials whose coefficients are all divisible by $p$.

In the binomial theorem expansion of $(x-1{)}^p$, every intermediate coefficient $\left(\genfrac{}{}{0ex}{}{p}{j}\right)$ is divisible by $p$: the numerator contains the prime factor $p$, while $j!(p-j)!$ does not for $1\le j<p$. HenceFor $p=2$, the last equality uses $1=-1$ in characteristic two. This is an instance of the Frobenius endomorphism.

Take $R=\mathbb{Z}$, $I=a\mathbb{Z}$ and $J=b\mathbb{Z}$. Since $a,b$ are coprime integers, Bézout's identity gives $ra+sb=1$, so $I+J=\mathbb{Z}$. Their intersection is $ab\mathbb{Z}$: it consists of integers divisible by both $a$ and $b$, and coprimality makes this equivalent to divisibility by $ab$. Thus the Chinese remainder theorem givesas a ring isomorphism. This includes $a=1$ or $b=1$, where the corresponding factor is the zero ring.

Use ordinary matrix addition and multiplication on $R=K[A]$. Sums and products of polynomials in $A$ remain such polynomials, and they commute because powers of the same matrix commute. The identity is $A^0=I$. Evaluation $\varphi (\sum c_i{X}^i)=\sum c_i{A}^i$ is a surjective unital algebra homomorphism over $K$. It is unique among maps fixing the scalar matrices and sending $X$ to $A$.

The scalar condition is needed for the word “unique”: as an unrestricted ring-homomorphism assertion over an arbitrary field, prescribing only the image of $X$ does not suffice. For example, over $\mathbb{C}$ with a real scalar matrix $A$, conjugating every coefficient gives another unital ring homomorphism with the same image of $X$. The intended polynomial-evaluation map is the $K$-algebra map just defined.

The kernel of a ring homomorphism is an ideal of the principal ideal domain $K[X]$. It is nonzero because finitely many powers of $A$ must become linearly dependent in the finite-dimensional matrix space. Its unique monic generator is precisely the minimal polynomial $m$: division by $m$ shows that a polynomial killing $A$ has zero remainder, by minimality. Hence $\ker \varphi =(m)$ and $R\cong K[X]/(m)$.

If $\gcd (f,m)=1$, Bézout's identity gives $uf+vm=1$; evaluation gives $u(A)f(A)=I$. Conversely an inverse in $R$ has form $g(A)$, so $fg-1\in (m)$, which forces $\gcd (f,m)=1$. Thus invertibility in this ring is exactly coprimality with the minimal polynomial.

The polynomials $t^c$ and $(t-1{)}^d$ are coprime. Bézout's identity gives polynomials $u,v$ with $u(t)t^c+v(t)(t-1{)}^d=1$. SetFor every $x$, the decompositionhas first summand in $V_0$ and second in $V_1$, since $T^c(T-I{)}^d=0$ and polynomial expressions in $T$ commute. If $x$ belongs to both kernels, the same Bézout identity gives $x=0$. Thus $V=V_0\oplus V_1$. Both vector subspaces are invariant under $T$.

On $V_0$, the restriction of $T$ is nilpotent; on $V_1$, the restriction of $T-I$ is nilpotent. Apply (b) separately, then concatenate the two bases. This yieldswhere $A,N$ are strictly upper triangular. Empty blocks are allowed if one subspace is zero. In particular $C=I+N$ has precisely the required diagonal.