Bézout's identity

wiki

\(a, b\)가 nonzero integer이고, \(d\)가 \(a, b\)의 greatest common divisor일 때, $$ ax + by = d$$ 를 만족하는 정수 \(x, y\)가 존재한다. 이 때, \(d\) 는 \(ax + by\) 형태로 표현 가능한 최소의 자연수이고, \(ax + by\)로 표현되는 모든 수는 \(d\)의 배수로 표현 가능하다.

\((a, b)\)를 Bézout coefficients라고 하고 유일하지 않다. 한 쌍의 \((x, y)\)만 찾으면, 모든 쌍은 다음과 같이 표현된다. $$\left(x+k\frac{b}{\gcd(a,b)},\ y-k\frac{a}{\gcd(a,b)}\right) $$

\(k\)는 임의의 정수이고 분수는 정수로 약분 가능하다.