Bezout's identity
Bézout’s Identity
Bézout’s identity states that for any two integers \( a \) and \( b \), not both zero, there exist integers \( x \) and \( y \) such that: \[ ax + by = \gcd(a, b) \] In other words, the greatest common divisor of \( a \) and \( b \) can be expressed as a linear combination of \( a \) and \( b \).
The identity follows from Euclid’s algorithm and can be obtained by working backwards through the division steps.
The Process to find integers \( x \) and \( y \):
1. Apply Euclid’s algorithm to compute \( \gcd(a, b) \).
2. Write each remainder as a combination of the previous two numbers.
3. Substitute backward until the GCD is written in the form \( ax + by \).
Example: \( \gcd(252, 105) \) From Euclid’s algorithm: \[ 252 = 105 \times 2 + 42 \] \[ 105 = 42 \times 2 + 21 \] \[ 42 = 21 \times 2 + 0 \] Thus, \( \gcd(252, 105) = 21 \). Now work backwards: \[ 21 = 105 - 42 \times 2 \] \[ 42 = 252 - 105 \times 2 \] Substitute: \[ 21 = 105 - 2(252 - 105 \times 2) \] \[ 21 = 105 \times 5 - 252 \times 2 \] Hence, one representation is: \[ 21 = (-2)\cdot 252 + 5 \cdot 105 \] So \( x = -2 \) and \( y = 5 \).
Bézout’s identity states that for any two integers \( a \) and \( b \), not both zero, there exist integers \( x \) and \( y \) such that: \[ ax + by = \gcd(a, b) \] In other words, the greatest common divisor of \( a \) and \( b \) can be expressed as a linear combination of \( a \) and \( b \).
The identity follows from Euclid’s algorithm and can be obtained by working backwards through the division steps.
The Process to find integers \( x \) and \( y \):
1. Apply Euclid’s algorithm to compute \( \gcd(a, b) \).
2. Write each remainder as a combination of the previous two numbers.
3. Substitute backward until the GCD is written in the form \( ax + by \).
Example: \( \gcd(252, 105) \) From Euclid’s algorithm: \[ 252 = 105 \times 2 + 42 \] \[ 105 = 42 \times 2 + 21 \] \[ 42 = 21 \times 2 + 0 \] Thus, \( \gcd(252, 105) = 21 \). Now work backwards: \[ 21 = 105 - 42 \times 2 \] \[ 42 = 252 - 105 \times 2 \] Substitute: \[ 21 = 105 - 2(252 - 105 \times 2) \] \[ 21 = 105 \times 5 - 252 \times 2 \] Hence, one representation is: \[ 21 = (-2)\cdot 252 + 5 \cdot 105 \] So \( x = -2 \) and \( y = 5 \).
A good video on this:
https://www.youtube.com/watch?v=9PRPr6J_btM
Comments
Post a Comment