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