"Bézout's identity"의 두 판 사이의 차이
ph
잔글 |
잔글 |
||
| 5번째 줄: | 5번째 줄: | ||
를 만족하는 정수 \(x, y\)가 존재한다. 이 때, \(d\) 는 \(ax + by\) 형태로 표현 가능한 최소의 자연수이고, \(ax + by\)로 표현되는 모든 수는 \(d\)의 배수로 표현 가능하다. | 를 만족하는 정수 \(x, y\)가 존재한다. 이 때, \(d\) 는 \(ax + by\) 형태로 표현 가능한 최소의 자연수이고, \(ax + by\)로 표현되는 모든 수는 \(d\)의 배수로 표현 가능하다. | ||
| − | \((a, b)\)를 '''Bézout coefficients'''라고 하고 유일하지 않다. 한 쌍의 \((x, y)\)만 찾으면<ref>[ | + | \((a, b)\)를 '''Bézout coefficients'''라고 하고 유일하지 않다. 한 쌍의 \((x, y)\)만 찾으면<ref>[https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm extended Euclidean algorithm]으로 찾는다</ref>, 모든 쌍은 다음과 같이 표현된다. |
$$\left(x+k\frac{b}{\gcd(a,b)},\ y-k\frac{a}{\gcd(a,b)}\right) $$ | $$\left(x+k\frac{b}{\gcd(a,b)},\ y-k\frac{a}{\gcd(a,b)}\right) $$ | ||
\(k\)는 임의의 정수이고 분수는 정수로 약분 가능하다. | \(k\)는 임의의 정수이고 분수는 정수로 약분 가능하다. | ||
2017년 8월 8일 (화) 18:59 판
\(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)\)만 찾으면[1], 모든 쌍은 다음과 같이 표현된다. $$\left(x+k\frac{b}{\gcd(a,b)},\ y-k\frac{a}{\gcd(a,b)}\right) $$
\(k\)는 임의의 정수이고 분수는 정수로 약분 가능하다.