Motivation
An equation such as asks for integer coefficients, so ordinary division cannot settle it. Over the rational numbers there are infinitely many answers; over the integers, divisibility creates an obstruction. The greatest common divisor measures that obstruction exactly. Its computation also supplies coefficients that make the obstruction sufficient.
Definitions
Definition 1.1.1
(Divisibility, greatest common divisor and primes)
For integers , write if for some integer . For not both zero, is their greatest positive common divisor. Integers are coprime when their gcd is . A prime is an integer whose only positive divisors are and ; an integer greater than that is not prime is composite.
The positivity requirement makes the gcd unique; signs of the inputs do not matter. In particular for nonzero . We leave outside the definition used here. Divisibility is transitive, and a common divisor of divides every integer combination . That elementary observation is the bridge between arithmetic and equations.
For signed inputs, first take absolute values; if either input is zero, the other absolute value is the gcd and already gives a Bézout identity. Otherwise order the two positive absolute values before starting division, and restore signs in the final coefficients. For and , division gives unique integers with and . Existence follows by taking the largest multiple of not exceeding . If two such expressions existed, subtracting would give a multiple of with absolute value smaller than , forcing the remainders and then quotients to agree.
Theorem/Proposition
Theorem 1.1.2
(Euclidean algorithm and Bézout identity)
Let be integers not both zero and let . Repeated division terminates, and its last nonzero remainder equals . There exist integers such that . Consequently has an integer solution exactly when .
Theorem 1.1.3
(Euclid's lemma and unique factorization)
If a prime divides , then or . Every integer is a product of primes, and the multiset of its prime factors is unique.
Proof sketch or proof idea
Proof
(Common divisors survive each division)
If , a number divides both exactly when it divides both . Thus each Euclidean division preserves the set of common divisors. The positive remainders strictly decrease, so the process terminates. At the final pair , the positive common divisors are the divisors of itself. Back substitution expresses every remainder, and hence , as an integer combination of the original inputs. Necessity for the equation follows because divides every combination; sufficiency follows by multiplying by .
Proof
(Euclid's lemma from Bézout, then factorization by descent and cancellation)
To prove Euclid's lemma, suppose . Since is prime, . Write and multiply by . Both and are divisible by if , so .
Existence of factorization follows by strong induction: if is composite, write with and factor the smaller integers. For uniqueness, compare two prime products. The first prime on one side divides the product on the other, so repeated use of Euclid's lemma shows it equals a prime there. Cancel that prime in the integers and repeat. The process exhausts both lists, since a nonempty prime product exceeds .
Proof X-ray
Where each hypothesis enters unique factorization
Positivity makes induction on size possible. Composite inputs split into strictly smaller positive factors, giving existence. Primality together with Bézout gives Euclid's lemma, allowing matching factors in competing products. Cancellation then reduces the comparison to a shorter one. The conclusion is independent of the order in which trial factors were found, because every valid decomposition has the same prime multiplicities.
Worked examples
Worked example 1.1.4
(Computing the obstruction and a solution)
The divisions , , , give gcd . Back substitution yields
Thus solves . In contrast, the same left side cannot equal , because .
Worked example 1.1.5
(Describing every integer solution)
From the previous solution, . Divide by to obtain . Coprimality of forces . Hence every solution is
Substitution verifies all these pairs. The argument also proves there are no others.
Worked example 1.1.6
(Valuations turn gcd and lcm into coordinate operations)
For a prime and a positive integer , let be the exponent of in its factorization. Since and , their gcd is and their least positive common multiple is . Minimum exponents give the gcd; maximum exponents give the lcm. Therefore for positive .
Reading a gcd as a complete obstruction
There are two assertions hidden inside the phrase “the gcd controls the equation.” First, every attainable right side is divisible by the gcd. This is a necessary condition and follows before any algorithm is run. Second, every multiple of the gcd is attainable. That is a sufficiency statement, and it requires the Bézout identity. Keeping the two directions separate prevents a common logical gap: finding an obstruction does not by itself prove there are no further obstructions.
Consider all integers that can be written as combinations of the two inputs. This set contains zero, is closed under addition, and is closed under taking negatives. If the inputs are not both zero, it contains a positive integer. Choose its least positive element and call it . Dividing any attainable integer by leaves an attainable remainder; minimality forces that remainder to vanish. Thus the entire set of attainable integers consists precisely of the multiples of . Because the inputs themselves are attainable, divides both. Because every common divisor divides every combination, no larger positive common divisor is possible. This gives a second proof of Bézout, emphasizing the structure of all combinations rather than a particular computation.
Concept lensStructural
The same gcd through two descriptions
The order definition chooses the greatest positive common divisor. The combination description chooses the least positive attainable linear combination. The argument above proves these descriptions agree. Their words “greatest” and “least” refer to different sets. Confusing those sets makes the result sound contradictory; identifying the sets explains why the equivalence is useful.
This second proof also clarifies why the integers matter. A nonempty set of positive rational combinations need not have a least element. Over the rationals, dividing coefficients by another positive integer produces smaller positive combinations. The discrete ordering of the integers is doing genuine work, even when an elementary calculation conceals it.
From one solution to every solution
A particular solution is useful, but it is rarely the end of an integer-equation problem. Suppose both coefficients are nonzero, the gcd is positive, and one solution has been found. Subtract its equation from an arbitrary second solution. The right sides cancel, leaving a homogeneous equation. Divide both coefficients by the gcd; they are now coprime. One reduced coefficient must divide the change in the other variable. Introduce the resulting integer parameter and substitute back. This is the reason that the parameters in the worked example are the coefficients divided by their gcd, rather than the original coefficients themselves.
The signs of those parameters are linked. Increasing the first variable by the reduced second coefficient must decrease the second variable by the reduced first coefficient; otherwise the left side changes instead of staying fixed. A quick substitution is therefore a useful check on a proposed parametrization. It verifies sufficiency, while the coprimality argument verifies completeness. Neither check replaces the other.
Additional constraints can then be imposed on the parameter. For example, a problem asking for nonnegative solutions becomes a pair of linear inequalities in a single integer parameter. If the lower bound exceeds the upper bound, there are no nonnegative solutions even though there may be infinitely many unrestricted integer solutions. Divisibility answers whether a line meets the integer lattice; sign constraints ask which of those lattice points lie in a specified region. These are related but different questions.
Why unique factorization is a theorem
It is easy to regard a factorization as an unambiguous notation because familiar computations have always produced the same answer. The proof is what licenses that practice. Existence uses descent to smaller positive factors. Uniqueness uses a different ingredient: a prime dividing a product must divide one factor. Without that implication, the step aligning a prime in one list with a prime in the other list would be unjustified.
Notice also that a prime in one list cannot merely divide a prime on the other side without equaling it. Both are positive primes, so the only positive divisors of the second are one and itself. This tiny step matters when generalizing factorization arguments to settings where irreducible elements and prime elements may differ. No such generalization is assumed here; the integer proof is complete within its stated setting.
A practical consequence is the divisibility test using exponents. For positive integers, one divides the other exactly when each prime exponent in the first is no larger than the corresponding exponent in the second. The forward direction follows by factoring the quotient. The reverse direction constructs the quotient by subtracting exponents, all of which remain nonnegative. This proves, rather than merely suggests, the minimum and maximum rules for gcd and lcm.
A certificate is easier to check than to discover
Suppose a calculation reports a positive candidate gcd and two coefficients expressing it as an input combination. To certify the answer, check that the candidate divides each input and check the linear-combination identity. The first check says the candidate is a common divisor. The second says every common divisor divides the candidate. Together they imply it is greatest. Merely printing a common divisor, or merely printing a combination, would provide only half the certificate.
This style of verification is useful even when the algorithm is implemented in software. A transcription error in a remainder table may be difficult to spot by reading every quotient, but a final certificate has only two divisibility checks and one exact identity. The mathematical proof explains why those small checks suffice; it does not require trust in the history of the computation.
History of an idea
An older formulation of the same reduction
In Book VII, Proposition 2 of the Elements, Euclid treats greatest common measure by repeated subtraction and tracks common measures through remainders. Modern quotient–remainder notation groups repeated subtractions into one step. This is a comparison with a surviving written formulation, not a claim of first discovery.
Common mistakes
Common mistake
(A common divisor is not the greatest one)
A gcd is not merely some common divisor: divides both and , but it is not their gcd. Nor does identify a unique solution of ; it guarantees existence. One must retain the integer parameter to describe all solutions.
Common mistake
(Coprime does not mean prime)
Another tempting claim is that coprimality of makes each prime. It only says their prime supports are disjoint: and are coprime composite integers. When using unique factorization, specify positive integers or separate off the sign first; needs a factor in addition to its positive prime factors.
Counterexample mode
Euclid's lemma needs a prime divisor
Claim: if , then or . Take , and : then is divisible by , but and . The proof breaks at its first step, since does not give ; in fact . Treating a composite divisor as if it were prime would break both the lemma and the uniqueness argument. The repaired statements are Euclid's lemma for a prime , and its coprime version: if and , then .
Summary
The Euclidean algorithm preserves common divisors while reducing the inputs. Back substitution gives a certificate for the gcd and solves the corresponding integer equation. Bézout's identity proves Euclid's lemma, which makes prime factorization unique and turns divisibility questions into comparisons of exponents.
Exercises
Quick check
(Find every integer solution of .)
Compute the gcd and one solution before introducing a parameter.
Solution · Answer
Since and , . One solution is . Dividing the homogeneous difference equation by gives . Thus , for . Each pair works, and coprimality of proves completeness.
Quick check
(Prove that if and , then . Give a counterexample when coprimality is removed.)
Here are integers and .
Solution · Answer
Choose with . Multiplication by gives . The assumption makes both terms on the right divisible by , hence . Without coprimality take : but .
Quick check
(Does have an integer solution? Does ? Give one solution in the solvable case.)
Use the gcd computed in the first worked example.
Solution · Answer
The gcd is . Since , the first equation has no integer solution. Since , multiply by : the pair solves the second equation, and indeed .