Worked Examples

Signed Euclid certificate

For 84 and 30, remainders are 24,6,0. Back substitution gives 6 = 30 - (84 - 2*30) = -84 + 3*30. For -84 and 30, coefficients (1,3) yield the same nonnegative gcd. Checking only the absolute-valued identity would miss the sign error.

An inverse and a nonexistent inverse

19*11 - 8*26 = 1, so 19 is the inverse of 11 modulo 26. For 10 modulo 26 the gcd is 2; every integer combination is even, so none can equal 1. The correct result is a reported failure, not 0 or a floating-point reciprocal.

Complete cyclic solution

For 8x ≡ 4 (mod 12), g=4. Reduce to 2x ≡ 1 (mod 3), giving x0=2. Lift to [2,5,8,11]. Substitution verifies the witnesses; the reduced equation proves that no other residue is possible. Changing the target to 3 makes the equation impossible because 4 does not divide 3.

A bounded verification strategy

For small moduli, enumerate every candidate independently and compare the entire sorted list. For larger cases, verify each witness, number of representatives, their spacing, and the theorem's preconditions. A supplied count alone is insufficient unless the uniqueness/completeness argument is valid. Keep this distinction in your report.