This is a rapid-fire trap deck. Each line is a claim or question; read it, decide before you peek, then reveal. The goal is not arithmetic (that lives in the parent note's worked tables) — it's the thinking about signs, base cases, uniqueness, and edge inputs that people get wrong.
Every trap below leans on the same handful of symbols. Let's pin them down and draw them, so nothing is used before it's earned.
The picture below is the whole vocabulary in one glance. Read it as: the left column is the remainder chain r0=56,r1=15,… shrinking downward until it hits 0; the row just above the 0 (green) is the gcd; the right column is each remainder's receipt(xi,yi) telling you how that remainder is built from a and b. Follow the white down-arrows to watch each remainder feed the next.
Figure 1 — The remainder chain for gcd(56,15) descending to g=1, with the Bézout receipt riding alongside each rung. The green rung is the last nonzero remainder (the gcd); the red rung is the terminating 0.
The second diagram shows why the arithmetic is forced. Read it as: each receipt is a point (x,y) in "coefficient space". The new receipt (green) is literally the two-steps-ago receipt (yellow) minusqi times the one-step-ago receipt (blue) — the red dashed arrow is that −qi× term. Because remainders obey ri=ri−2−qiri−1, their receipts must obey the identical subtraction.
Figure 2 — The coefficient recurrence as vector subtraction: (xi,yi)=(xi−2,yi−2)−qi(xi−1,yi−1), shown for the step (1,−3)−2⋅(−1,4)=(3,−11).
With ri, qi, xi, yi, g and the recurrence all defined, the traps make sense.
"I start my coefficient table at the first division a=qb+r, so my first row is that step." — what's wrong?
The base cases come before any division: r0=a has (x0,y0)=(1,0) and r1=b has (x1,y1)=(0,1). Skipping them corrupts every later recurrence.
"Using xi=xi−2−qixi−1 with xi−1=−4, xi−2=1, qi=2 I get 1−2⋅4=−7." — spot it.
The sign was dropped: xi−1=−4, so xi=1−2⋅(−4)=1+8=9. Always substitute the coefficient with its sign in parentheses.
"The gcd of 56 and 15 came out as ri=0 in the last row, so the gcd is 0." — error?
0 is the terminating remainder, not the gcd. The gcd is 1, the last nonzero remainder ri−1 above it.
"To solve 6x+4y=5 I just find Bézout coefficients for gcd(6,4)=2 and scale." — error?
5 is not a multiple of 2, so no integer solution exists at all — scaling by 5/2 produces non-integers. Check divisibility of c by the gcd first (see Linear Diophantine Equations).
"For the recurrence I only track xi; yi I'll recover at the end from y=(g−ax)/b." — is this safe?
It works arithmetically as a shortcut only ifb=0, but it hides sign/rounding errors; tracking both columns via the twin recurrences is safer and standard.
"gcd(0,7): the algorithm needs two positive inputs, so this is undefined." — error?
gcd(0,7)=7 is perfectly defined; the receipt is 0⋅0+1⋅7=7, i.e. (x,y)=(0,1). Zero is a legitimate input.
Why does every remainder ri end up expressible as xia+yib?
Because r0=a and r1=b already are, and each new remainder ri=ri−2−qiri−1 is a combination of the previous two — the property propagates by induction.
Why does the recurrence subtract qi times the previous coefficient rather than add?
Because the division step itself is ri=ri−2−qiri−1 (a subtraction), and the coefficients xi,yi simply inherit the exact same arithmetic.
Why do we need Extended Euclid at all for modular inverses instead of just trying values?
Trial takes up to m attempts; Extended Euclid finds x with ax≡1(modm) in about logm steps, which is why RSA relies on it for large keys.
Why is the smallest positive value of ax+by exactly gcd(a,b) and never smaller, and how does Extended Euclid actually attain it?
Any ax+by is divisible by every common divisor of a,b, hence by g, so no positive value beats g; and the algorithm attains g because it carries the receipt ri=xia+yib on every row — when the chain reaches the row holding r=g, that row's (x,y) is an explicit combination summing to g.
gcd(a,a)=a, and the algorithm's first step a=1⋅a+0 leaves remainder 0 immediately, so the gcd sits in the r1=b row whose receipt is (0,1) — the algorithm returns (x,y)=(0,1) (i.e. 0⋅a+1⋅a=a), the minimal-magnitude pair.
What happens if a<b at the start?
Nothing breaks — the first division gives quotient q=0 and remainder a, which simply swaps them; the base cases (1,0) and (0,1) still hold.
What does the algorithm return for gcd(0,0)?
It's undefined (conventionally 0): with both inputs zero there is no nonzero remainder to call a gcd and no meaningful receipt, so it's excluded from Bézout's identity.
If a or b is negative, are Bézout coefficients still valid, and why?
Yes — gcd is defined via absolute values, so run Euclid on ∣a∣,∣b∣ to get ∣a∣x+∣b∣y=g; if a was negative, then ∣a∣=−a and substituting gives a(−x)+∣b∣y=g, so flipping that coefficient's sign restores a genuine solution of ax+by=g — Bézout's identity is preserved because the equality still holds term-for-term.
For gcd(a,1), what is the receipt?
gcd(a,1)=1 with 0⋅a+1⋅1=1, so (x,y)=(0,1) — a degenerate case where one coefficient is zero.
Since infinitely many pairs work, which one does the algorithm hand back, and how do I recognize the "canonical" one?
Extended Euclid returns the pair with the smallest magnitudes: for a>b>0 they satisfy ∣x∣≤2gb and ∣y∣≤2ga, so it is the minimal-magnitude solution — no shifting needed.
Why do those bounds ∣x∣≤2gb and ∣y∣≤2ga hold?
All solutions form a lattice, spaced gb apart in x and ga apart in y (see next item); the algorithm's output lands in one spacing-window around 0, so its distance from 0 is at most half a spacing, giving ∣x∣≤2gb and correspondingly ∣y∣≤2ga.
I have one solution (x0,y0); how do I list all of them?
Every solution is (x0+tgb,y0−tga) for integer t: adding gb to x and subtracting ga from y changes ax+by by agb−bga=0, so the equation still holds.
Sweeping t to minimise ∣x∣+∣y∣ — why need I check only one or two integer values of t?
∣x0+tgb∣ is a "V-shaped" function of the real variable t (decreasing then increasing), so its integer minimum is at one of the two integers straddling the real minimiser; checking those one or two t suffices, because moving further only increases ∣x∣ (and typically ∣y∣ too).
For 56x+15y=1 the algorithm gives (−4,15); is there a smaller-looking pair?
Shift by t=1: (−4+15,15−56)=(11,−41) grows, and t=−1 gives (−19,71) — both larger, so (−4,15) is already the minimal-magnitude canonical pair the algorithm returns.
Recall The five traps in one breath
Base cases come before division; the gcd is the second-to-last remainder; substitute negatives in parentheses; check c divisible by g before scaling; inverses need g=1.
