Math/Number Theory

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

# DefinitionBézout's identity — Let a and b be integers or polynomials with greatest common divisor d. 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 \lor..

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..