Use division to control ideals and gcds

Try

Divide ninety-one by thirty-five, then divide thirty-five by the remainder. The remainders decrease until zero appears. The last nonzero remainder is seven. This familiar algorithm contains more than a way to calculate a gcd: it constructs a linear combination and explains why every ideal of Z has one generator.

A Euclidean domain is a domain with a nonnegative integer-valued function on nonzero elements supporting division with smaller remainder. The function need not be an ordinary absolute value; polynomial degree supplies another example.

Predict

If d is a nonzero member of an ideal with the smallest possible Euclidean value, what happens when another ideal member is divided by d? Predict why the remainder belongs to the ideal and why it cannot be a smaller nonzero element. This is the central proof mechanism behind the principal-ideal conclusion.

Experiment

Trace the integer example and reverse its equations.

Division	Remainder
91=2·35+21	21
35=1·21+14	14
21=1·14+7	7
14=2·7	0

Back-substitution gives 7=21−14=2·21−35=2·91−5·35. Verify the arithmetic directly. Every common divisor of ninety-one and thirty-five divides seven because it divides this combination. Seven divides both inputs, so it is a gcd.

The identity also shows that the ideal generated by the two inputs equals (7): every combination is a multiple of seven, and seven itself is a combination.

Understand

The Euclidean condition says that for a and nonzero b there exist q,r with a=qb+r, where r=0 or its Euclidean value is smaller than that of b. Repeated division terminates because a strictly decreasing sequence of nonnegative integers cannot continue indefinitely. Gcds are preserved when a pair (a,b) is replaced by (b,a−qb): a common divisor of either pair divides the other pair too.

To prove every Euclidean domain is a principal ideal domain, handle the zero ideal first. For a nonzero ideal I, choose nonzero d∈I minimizing the Euclidean value. For any a∈I, division gives a=qd+r. Since r=a−qd lies in I, minimality forces r=0. Hence a∈(d), so I⊆(d). The reverse inclusion follows from d∈I and absorption. Thus I=(d).

In a PID, let (a,b)=(d). Then d divides a and b. Any common divisor c divides every linear combination ra+sb, including d, so d is a gcd. Conversely d∈(a,b) gives a Bézout identity d=ra+sb. Gcds in a general domain are only determined up to multiplication by a unit; the positive gcd convention is specific to integers.

For F[x], division cancels the leading term of a remainder using the inverse of the divisor’s leading coefficient. Each subtraction decreases degree, so the process terminates. This proves F[x] is Euclidean with degree as the function. The field assumption matters: over Z[x], dividing x by 2x would require the unavailable coefficient one half.

Apply

Use a Bézout identity for relatively prime integers a,n to find an inverse of a modulo n. The coefficient multiplying a is an inverse because the other term vanishes modulo n. Check it by multiplication rather than trusting the backward substitutions.

Explain the difference between a Euclidean algorithm and the abstract PID property. The former supplies a particular division mechanism; the latter only asserts that each ideal is generated by one element. We have proved one implication, not that every PID comes with a chosen Euclidean function.

Continue

The next lesson proves unique factorization in a PID. Existence of irreducible factors and uniqueness of their arrangement require separate arguments; neither follows merely from seeing familiar integer examples.