Math/Number Theory

Bézout's identity - 베주 항등식(Part. 1)

# Definition Bézout's identity — Let a and b be integers or polynomials with greatest common divisor a. Then there exist integers or polynomials x and y such that ax + by = d. Moreover, the integers or polynomials of the form az + bt are exactly the multiples of d. (reference) Extended Euclidean과 연결되는 정수론의 기본 정리 중 하나이다. 증명부터 해보자. $Lemma \ 1)$ $ For \ \forall a, b \in \mathbb{N} \left(a \neq 0 \l..

Euclidean Algorithm - 유클리드 호제법

# Definition $ a = bq + r(0 \le r = b,$ $GCD(a, b) = GCD(a-b, b) $ $g=GCD(a,b),$ $ \ a = gA,$ $ \ b =gB$ 라 두자. $ GCD(a-b, b) $ $= GCD(g(A-B), gB) $ 이기에 A-B와 B가 서로소임을 보이면 Lemma 1은 증명된다. 귀류법으로 $ GCD(A-B, B) = g_{A,B},$ $A-B = g_{A,B}M,\ B $ $= g_{A,B}N,\ g_{A,B} \neq 1$ 를 만족하는 $\exist..