Bezout's identity uses Euclid's algorithm to give an expression for d = gcd(a, b) in terms of a and b. Theorem: If a and b are both integers (not equal to zero), then there exists integers x and y such that gcd(a, b) = ax + by. We can also call Bezout's Identity the Extended Euclidean Algorithm as we work backwards, from a known value d, to find x and y. Example: To calculate x and y from d = gcd(102, 38), we first use the Euclidean Algorithm to calculate d: 102 = (2 x 38) + 26 38 = (1 x 26) + 12 26 = (2 x 12) + 2 12 = (6 x 2) + 0 The last non-zero remainder is 2, so d = 2. Now work backwards substituting the numbers we have above; 2 = 26 - (2 x 12) = 26 - (2 x (38 - (1 x 26))) = (3 x 26) - (2 x 38) = (3 x (102 - (2 x 38))) - (2 x 38) = (3 x 102) - (8 x 38) Therefore, we can see that x = 3 and y = -8. Corollary: If a and b are relatively prime integers, we have gcd(a, b) = 1 and by Bézout's identity, there are integers x and y such that ax + by = 1. Example: Find a pair of integers x and y such that 2014x + 4021y = 1. 4021 = (1 x 2014) + 2007 2014 = (1 x 2007) + 7 2007 = (286 x 7) + 5 7 = (1 x 5) + 2 5 = (2 x 2) + 1 This gives us d = 1. Working backwards; 1 = 5 - (2 x 2) = 5 - (2 x (7 - (1 x 5))) = (3 x 5) - (2 x 7) = (3 x (2007 - (286 x 7))) - (2 x 7) = (3 x 2007) - (860 x 7) = (3 x 2007) - (860 x (2014 - (1 x 2007))) = (863 x 2007) - (860 x 2014) = (863 x (4021 - (1 x 2014))) - (860 x 2014) = (863 x 4021) - (1723 x 2014) Therefore, we can see that x = -1723 and y = 863. Being able to use and understand Bezout's identity allows us to determine if two numbers are coprime. If you fancy having a go at the calculations yourself, see the Division Quiz for more examples and you can always come back and check your answers!
Written by JaneW