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 Principle Well-Ordering Principle. Let $\emptyset \neq S \subseteq \mathbb{N} \cup \{0\}$. Then $\exists a \in S$ such that $a \leq b, \forall b \in S$. 정렬 원리라고도 하며, 집합 내에서 최소 원소의 존재성을 보장해준다.

Equivalence of the system of linear equations Definition 1. Two systems of linear equations are called equivalent if they have the same solution set. Theroem 1 Theorem 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..

Reduced Row Echelon Form Definition 1. A matrix is said to be in reduced row echelon form(RREF) if the following three conditions are satisfied: i) Any row containing a nonzero entry precedes any row in which all the entries are zero. ii) The first nonzero entry in each row is the only nonzero entry in its column. iii) The first nonzero entry in each row is 1 and it occurs in a column to the rig..

Homogeneous System Definition 1. A system $Ax = b$ is said to be homogeneous if $b = 0$. Otherwise it is said to be nonhomogeneous. 번역하면 homogeneous는 '동차', 즉 차수가 같다는 말이다. $b$는 방정식에서 상수항에 해당되고, 그 외의 항들은 모두 차수가 1인 미지수들이 곱해져 있다. 즉 $b$에 해당하는 항들을 제외하면 모두 미지수의 차수가 같으므로, 만일 상수항이 0이라면 상수항에 동일한 차수의 미지수를 곱한 것으로 생각할 수 있으므로 시스템 자체를 차수가 같은, 즉 동차 연립방정식이라고 볼 수 있다. Theorem 1 Theorem 1. Let $Ax = \mathbf{0}$ be ..

A System of Linear Equations Definition 1. The system of equations $$a_{11}x_1 + \cdots + a_{1n}x_n = b_1 \\ \vdots \\ a_{m1}x_1 + \cdots + a_{mn}x_n = b_m,$$ where $a_{ij}, b_i \in F$ and $x_j$ are $n$ variables taking value in $F$, is called a system of $m$ linear equations in $n$ unknowns over $F$. 번역하면 선형 연립방정식이며, $A = \begin{pmatrix} a_{11} & \cdots & a_{1n} \\ \vdots & \text{} & \vdots \\ ..