주어진 두 수의 최대공약수는 보통 소인수분해를 하여 구한다. 그러나 숫자가 커져가면 소인수분해가 힘들어지고, 최대공약수를 구하는 것 또한 만만찮은 작업이 된다. 이때 직접 소인수분해를 하지 않고도 최대공약수를 제시해주는 방법이 Euclidean Algorithm, 즉 유클리드 호제법이다. 기본적으로 알고리즘이므로 일련의 과정을 제시하고, 이 과정을 따라가면 반드시 최대공약수를 구할 수 있다. Euclidean Algorithm 주어진 두 정수 $a, b$에 대해 gcd($|a|, |b|$) = gcd($a, b$)이므로 편의상 $a \geq b > 0$이라 가정해도 문제가 되지 않는다. Division Algorithm에 의해 $$a = q_1b + r_1 (0 \leq r_1 < b)$$를 만족하는 $..

Euclid's Lemma Theorem 1. (Euclid's Lemma) Let $a, b \in \mathbb{Z}$, not both zero. If $a \,|\, bc$ for $c \in \mathbb{Z}$, with gcd($a, b$) = 1, then $a \,|\, c$. Proof. By Theorem 3, $1 = ax + by$ for some $x, y \in \mathbb{Z}$. Let $bc = ka$ for some $k \in \mathbb{Z}$. Then $c = c \cdot 1 = c(ax + by) = acx + bcy = acx + kay = a(cx + ky) \Longrightarrow a \,|\, c$. $\blacksquare$ $a$와 $b$는 ..

Relatively Prime Definition 1. (Relatively Prime) Let $a, b \in \mathbb{Z}$, not both zero. Then $a$ and $b$ are relatively prime if gcd($a, b$) = 1. 두 정수의 최대공약수가 1일 경우 두 수를 relatively prime, 즉 서로소라고 부른다. 최대공약수를 두 수가 나눗셈이라는 연산에서 가지는 공통되는 성질의 최대치라고 생각해보자. 이러한 관점에서 서로소는 두 수가 더 이상 나눗셈에서 봤을 때 공통되는 성질을 가지지 않는다는 것으로 이해할 수 있다. Theorem 1 Theorem 1. Let $a, b \in \mathbb{Z}$, not both zero. Then $a$ and ..

Divisible Definition 1. $b \in \mathbb{Z}$ is divisible by $a \neq 0$, denoted $a \,|\, b$, if $\exists c \in \mathbb{Z}$ such that $b = ca$. We write $a \nmid b$ if $b$ is not divisible by $a$. $b$가 $a$로 divisible, 즉 나누어 떨어진다는 것은 $a$의 적당한 정수배가 $b$와 같다는 뜻이다. 이때 어떠한 정수라도 가능하며, 따라서 0은 모든 정수로 나누어 떨어진다. Theorem 1 Theorem 1. For $a, b, c \in \mathbb{Z}$, the following hold: (a) $a \,|\, 0, 1 \,|\, a,..

Division Algorithm Theorem 1. (Division Algorithm) Let $a, b \in \mathbb{Z}$, with $b \neq 0$. Then $! \exists q, r \in \mathbb{Z}$ such that $a = qb + r (0 \leq r 0$, and let $S := \{a - xb \geq 0 \, | \, x \in \mathbb{Z}\}$. Since $b \geq 1$, $0 \leq a + |a| \leq a + |a|b $= $a - (-|a|)b$. Thus $S \neq \emptyset$. By Well-Ordering Principle, there is the least element $r \in S$. Then $\exists ..

Mathematical Induction Mathematical Induction. Let $S \subseteq \mathbb{N}$ with the following properties: (a) $n_0 \in S$ for some $n_0 \in \mathbb{N}$. (b) $k \in S \Longrightarrow k+1 \in S$. Then $S = \mathbb{N} \backslash \{1, ..., n_0 - 1\}$. $n_0 = 1$로 택하면 흔히 볼 수 있는 수학적 귀납법이 된다. Proof. Suppose that $T := (\mathbb{N} \backslash \{1, ..., n_0 - 1\}) \backslash S \neq \emptyset$. Then $T \su..

Archimedean Property Archimedean Property. Let $a, b \in \mathbb{N}$. Then $\exists n \in \mathbb{N}$ such that $na > b$. 해석학에서 언급하는 아르키메데스의 성질의 정수론 버전이며, $a, b$를 자연수로 가져온 것 말고 차이는 없다. Proof. Suppose that $\forall n \in \mathbb{N}, na \leq b$. Let $S := \{b - na \, | \, n \in \mathbb{N}\}$. Since $b - na > 0$, $\emptyset \neq S \subseteq \mathbb{N} \cup \{0\}$. Then by Well-Ordering Principle, $..

Well-Ordering PrincipleWell-Ordering Principle. Let $\emptyset \neq S \subseteq \mathbb{N} \cup \{0\}$. Then $S$ is well-ordered, that is, $\exists a \in S$ such that $a \leq b, \forall b \in S$.정렬 원리라고도 하며, 집합 내에서 최소 원소의 존재성을 보장해준다. 선택 공리와 동치이므로 ZFC 공리계에서 문제없이 받아들일 수 있다.

Determinant, 무엇을 결정(determine)한다는 말일까? 그 답을 찾기 위해서 우리는 the system of linear equations로 돌아가야 한다. Square matrix $A$에 대해서 $A \textbf{x} = \textbf{b}$라는 system이 주어져 있다. 이때 적절한 elementary row operation을 통해 $A$를 identity matrix $I$와 row-equivalent하도록 변형할 수 있는 경우가 존재할 수 있다. 그말인즉슨 $A$가 invertible하여서 사용한 elementary matrix들의 곱이 $A$의 inverse가 된다는 말이고, 역으로 어떻게 elementary row operation을 하여도 $I$와 row-equivale..

Equivalence of the system of linear equationsDefinition 1. Two systems of linear equations are called equivalent if they have the same solution set.Theroem 1Theorem 1. Let $Ax = b$ be a system of $m$ linear equations in $n$ unknowns, and let $C$ be an invertible $m \times m$ matrix. Then the system $(CA)x = Cb$ is equivalent to $Ax = b$.Proof. Denote $K$ and $K_C$ the solution set to $Ax = b$ an..