Track integer Bézout coefficients through binary gcd

Try

Knowing that the gcd of 14 and 10 is 2 is useful. Knowing the identity 2=3·14−4·10 gives a second kind of evidence: every common divisor must divide 2 because it divides every integer linear combination of the inputs. We will produce such coefficients while binary gcd halves and subtracts remainders.

Negative coefficients are allowed. They are weights in an integer identity, not numbers of physical objects. The challenge is to keep them integral when an even remainder is halved. Dividing its two coefficients by two may introduce fractions even though the represented value is even.

Start with positive inputs x=14,y=10. Remove their common power of two q=2, giving fixed bases a=7,b=5. These bases remain unchanged throughout the coefficient calculation. Only the current remainders and their coefficient rows change.

Predict

The initial remainder u=7 has row (1,0), meaning u=1·a+0·b. The other remainder v=5 has row (0,1). Subtract v from u: the new remainder is 2 and its row is (1,−1). Predict how to represent half of this remainder with integer coefficients.

Directly halving the row gives (1/2,−1/2). Instead, add the zero-valued row (b,−a)=(5,−7) first. The resulting row (6,−8) still represents 2, since 5a−7b=0. Now divide both entries by two: (3,−4) represents 1. This repair preserves the value before division and makes division integral.

Experiment

Use the explorer to inspect a remainder together with its coefficient identity. Before each halving, decide whether both coefficients are even or whether repair is necessary. The following static example is a separate worked trace with fixed bases 7 and 5; playground inputs may differ.

Preserve the value and its coefficients

Enter whole numbers from 0 through 255, not both zero. Predict the next subtraction or halving, then advance one operation. Coefficients can be negative even though the two current values remain nonnegative. This exact bounded integer trace uses no rounding.

Original input xOriginal input yPrepare traceReset to 14 and 10

Normalization: Divide both original inputs by 2 exactly 1 time: a=7, b=5, scale=2^1=2. At least one of a,b is odd. Thus x=2·7 and y=2·5.

The displayed identities are u=Aa+Bb and v=Ca+Db. The columns A,B,C,D are coefficients relative to a,b, not an independent new pair of inputs. Until a value becomes zero, halve a positive even value first (u before v); otherwise subtract the smaller odd value from the larger. Equal odd values are subtracted to produce zero.

Previous operationNext operationRewind trace

Step 0: Initialize coefficients relative to the normalized inputs.

Current exact checks: u = (1)·7 + (0)·5 = 7; v = (0)·7 + (1)·5 = 5.

Only the initial state and operations reached manually are shown

Step	Operation	u	A	B	v	C	D
0	Initialize coefficients relative to the normalized inputs.	7	1	0	5	0	1

The terminal certificate is hidden until the trace reaches a zero value. Predict the next coefficient pair before advancing.

Why the odd-coefficient halving repair preserves the identity

When u=Aa+Bb is even, halve A and B if both are even. Otherwise replace them by (A+b)/2 and (B−a)/2. The extra terms cancel: ba−ab=0. Since a,b are not both even, parity of the even identity guarantees both repaired numerators are even. The same rule applies to C,D when halving v. This normalization premise is why common powers of 2 are removed first. The zero-input branch uses no repair.

Preserving coefficients alone does not prove that halving preserves the gcd. That proof also uses parity of the other value and the invariant that the normalized gcd is odd; the lesson supplies the general argument. This finite trace is an example, not a proof for all unbounded integer inputs.

Try 14 and 10: after subtracting, u=2 has coefficients (1,−1). Predict the repaired coefficients before halving. Then compare 24 and 24, and finally 0 and 15. Explain the common factor, equality and zero cases separately. Controls are temporary; no work is stored and no completion is awarded.

Operation	u and its row	v and its row
Initialize	7: (1,0)	5: (0,1)
u minus v	2: (1,−1)	5: (0,1)
Repair and halve u	1: (3,−4)	5: (0,1)
v minus u	1: (3,−4)	4: (−3,5)
Repair and halve v	1: (3,−4)	2: (1,−1)
Repair and halve v	1: (3,−4)	1: (3,−4)
v minus u	1: (3,−4)	0: (0,0)

Check every row by multiplying its entries by 7 and 5. This static trace chooses v−u when the remainders become equal; the explorer chooses u−v at equality. Both are valid, but the zero remainder appears in a different column. Then multiply the final nonzero identity by q=2 to recover 2=3·14−4·10. The coefficients do not themselves get multiplied by q when the bases are replaced by the original inputs.

Understand

For positive original inputs, write x=qa,y=qb, where q is their largest common power of two. At least one of a,b is odd. Maintain two identities u=Aa+Bb and v=Ca+Db, initially with rows (1,0) and (0,1). Subtracting v from u replaces its row by (A−C,B−D); the other row stays unchanged. This follows by distributing subtraction over the two fixed-base expressions.

When u is even and both A,B are even, halve both coefficients. Otherwise use the repaired row ((A+b)/2,(B−a)/2). Its value is u/2 because the added terms ba and −ab cancel. But algebraic equality alone does not prove integrality. Check all possible base parities:

• If a and b are odd, even u forces A and B to have the same parity. Since they are not both even, both are odd, so A+b and B−a are even.
• If a is odd and b is even, even u forces A even. The failed both-even branch forces B odd. Both repaired numerators are even.
• If a is even and b is odd, even u forces B even, while A is odd. Again both repaired numerators are even.

These exhaust the cases because normalization excludes two even bases. Use the identical rule with C,D when halving v. The repair uses fixed a,b, not the changing u,v.

The coefficient identities accompany the gcd-preserving remainder algorithm; they do not replace its proof. Initially the normalized remainders are not both even. This remains true before every nonterminal step: halving an even remainder leaves the other, odd remainder unchanged; subtracting two odd remainders leaves the unchanged one odd. Thus an even remainder is always paired with an odd remainder when halved. This parity argument justifies the halving guard without assuming the result we are proving. Subtraction and permitted halving preserve the current gcd, and the positive remainder sum decreases until a zero remainder is reached. Equivalently, the preserved normalized gcd is odd. The nonzero remainder d is the normalized gcd. Multiplying d=Aa+Bb by q gives qd=Ax+By, an identity in the original inputs.

Handle a zero input before this positive-input normalization: gcd(0,y)=y for positive y with coefficients (0,1), and gcd(x,0)=x with coefficients (1,0). The all-zero pair is outside this lesson’s input contract. Repeatedly asking for the largest power of two dividing zero alone is not a terminating normalization procedure.

Apply

With fixed bases 7 and 5, row (1,1) represents 12. Find integer rows for 6 and then 3. Review: the two repairs give (3,−3), then (4,−5). Check 21−15=6 and 28−25=3. Even represented values do not require even coefficients.

Finally test the reported certificate independently. A positive candidate d must divide both original inputs and be an integer linear combination of them. The first condition makes it a common divisor; the second makes every common divisor divide d. Together they prove that d is the greatest common divisor. A true identity alone is insufficient: 12=−2·30+4·18, yet 12 divides neither 30 nor 18.

Continue

The practice includes alternate repairs, normalization failures and a changed full trace. Track remainder correctness and coefficient correctness as separate obligations, then verify the final certificate without trusting the trace. These proofs concern exact integers. The bounded explorer illustrates them on supported inputs; it does not establish overflow safety or runtime guarantees for an unrestricted machine implementation.