[이산수학] 베주의 항등식(Bezout's identity)

 

 

베주의 항등식(Bezout's identity)

---

1. 베주의 항등식

베주의 항등식은 0이 아닌 두 a, b의 최대공약수는 임의의 정수 x, y에 의해 아래와 같은 항등식을 의미합니다.

$$ax + by = gcd(a, b)$$

 

2. 예시

① a = 12, b = 8

$$gcd(a, b) = 4 = a * 1 + b * (-1)$$

 

② a = 3, b = 7

$$gcd(a, b) = 1 = a * (-2) + b * 1$$

---

연관 게시글

[이산수학] 정수론

[이산수학] 정수론

---

참조

•