The Prime Number Definition 1. An integer $p > 1$ is called a prime number (or prime) if its only positive divisors are 1 and $p$. An integer greater than 1 that is not a prime is called a composite. 양의 약수로 1과 자기 자신 밖에 가지지 않는 수를 소수라고 하고, 그렇지 않은 수를 합성수라 한다. 나눗셈이라는 연산의 관점에서 볼 때 더이상 쪼개지지 않는, 마치 원자와 동일한 역할을 수행하는 대상이다. 소인수분해라는 개념이 괜히 있는 것이 아니다. 정수들을 이루는 벽돌과도 같은 기본 단위가 소수이기 때문에 소수를 기준으로 정수를 분해하는 것이다. ..

The Linear Diophantine Equation Definition 1. Let $a, b, c \in \mathbb{Z}$ with $a \neq 0, b \neq 0$. The equation $$ax + by = c$$ that is to be solved in the integers is called the linear diophatine equation in two unknowns. 교과과정에서는 일차 부정방정식으로 소개되는 선형 디오판토스 방정식이다. 보통 정수를 계수로 가지는 다항식의 정수해를 찾는 것을 의미한다. 해를 가지는 조건과 해의 구체적인 형태가 깔끔하게 알려져 있다. Theorem 1 Theorem 1. The linear diophantine equation $ax + ..

Least Common Multiple Definition 1. Let $a, b \in \mathbb{Z}$, with $a \neq 0, b \neq 0$. The least common multiple of $a$ and $b$, denoted by lcm($a, b$), is $m \in \mathbb{N}$ satisfying the following: (a) $a \,|\, m \wedge b \,|\, m$. (b) $a \,|\, c \wedge b \,|\, c (c > 0) \Longrightarrow m \leq c$. 최대공약수와 마찬가지의 방법으로 lcm, 즉 최소공배수를 정의할 수 있다. 공배수이면서 ((a)) 공배수 중 가장 작은 수를 ((b)) 최소공배수라고 한다. Theor..

주어진 두 수의 최대공약수는 보통 소인수분해를 하여 구한다. 그러나 숫자가 커져가면 소인수분해가 힘들어지고, 최대공약수를 구하는 것 또한 만만찮은 작업이 된다. 이때 직접 소인수분해를 하지 않고도 최대공약수를 제시해주는 방법이 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, $..