gen-define-bezout-s-identity-and-give-one-short-worked-example-a43d

Define Bezout's identity and give one short worked example.

# Bézout's Identity **Definition:** For any two integers *a* and *b* with greatest common divisor *d* = gcd(*a*, *b*), there exist integers *x* and *y* such that: $$ax + by = d$$ In particular, two integers are coprime (gcd = 1) if and only if there exist integers *x* and *y* such that *ax* + *by* = 1. ## Worked Example Find integers *x* and *y* such that **21***x* + **15***y* = gcd(21, 15). **Solution using the Extended Euclidean Algorithm:** First, find gcd(21, 15): - 21 = 1(15) + 6 - 15 = 2(6) + 3 - 6 = 2(3) + 0 So gcd(21, 15) = **3**. Now work backwards to express 3 as a combination of 21 and 15: From step 2: **3** = 15 - 2(6) Substitute 6 from step 1: 3 = 15 - 2(**21 - 15**) Simplify: 3 = 15 - 2(21) + 2(15) = 3(15) - 2(21) Rearranging: **21(-2) + 15(3) = 3** ✓ Therefore: *x* = -2 and *y* = 3.