약수(Divisor), 배수(Multiple)

정리1(나눗셈 정리)

임의의 정수 $a,b \in \mathbb{Z}$에 대해 다음이 성립한다.

1. $a >0$이면 $0 \le r < a$와 $b = q\cdot a + r$를 만족하는 $q,r \in \mathbb{Z}$은 유일하게 존재한다.

2. $a < 0$이면 $a<r \le 0$와 $b = q\cdot a + r$를 만족하는 $q,r \in \mathbb{Z}$은 유일하게 존재한다.

증명

1.

$a > 0$일때 $q,r \in \mathbb{Z}$의 존재성을 보인다.

집합 $S = \{ b - x\cdot a  :  x \in \mathbb{Z} \text{ 이고 } b - x\cdot a \ge 0 \} \subseteq \mathbb{Z}$를 정의할때

자연수 부등식 정리로 $a \ge 1$이고 절댓값 정리로 $|b| \ge 0$에 대해 

부등식 정리로 $|b|\cdot a \ge |b| \cdot 1 = |b|$와 $b - (-|b|)\cdot a = b + |b|\cdot a \ge b + |b| $가 성립하여

절댓값 정리로 $b \ge -|b|$이므로 $b -(-|b|)\cdot a  \ge b + |b| \ge 0$이고 $-|b| \in S$가 되어 $S$는 공집합이 아니다.

$S\ne \emptyset$이고 $S \subseteq \mathbb{N}$이므로 정렬성으로 모든 $s \in S$에 대해 $r\le s$인 최소원소 $r \in S$이 존재하고

$r \in \{ b - x\cdot a : x \in \mathbb{Z} \text{ 이고 } b - x\cdot a \ge 0 \}$이므로

$r = b - q \cdot a \ge 0$인 $q \in \mathbb{Z}$가 존재하여 $b = q\cdot a + r$이다.

$a \le r$이라고 가정하면 $0 \le r- a = (b - q\cdot a) - a = b - (q +1)\cdot a$이므로 $r -a \in S$인데

$a > 0$이므로 $r - a < r $가 되어 $r\in S$이 $S$의 최소 원소라는 가정에 모순이므로 $0 \le r < a$이다.

$a > 0$일때 $q,r \in \mathbb{Z}$의 유일성을 보인다.

$q_1,q_2,r_1,r_2  \in \mathbb{Z}$이 $b = q_1\cdot a + r_1$이고 $b = q_2\cdot a +r_2$라고 가정하면

$q_1\cdot a + r_1=b = q_2\cdot a +r_2$이므로 $(q_2 -q_1) \cdot a = r_2 - r_1$이다.

또 $0 \le r_1 < a$이고 $0 \le r_2 < a$이므로 부등식 정리로

$-r_1 \le -0$에 $a$를 더하면 $a - r_1 \le a - 0 = a$이고 $r_2 < a$에 $-r_1$을 더하면 $r_2 - r_1 < a - r_1 \le a$이다.

비슷하게 $-r_2 \le -0$에 $a$를 더하면 $a - r_2 \le a - 0 =a$이고 $r_1 < a$에 $-r_2$을 더하면 $r_1 - r_2 < a - r_2 \le a$가 되어

$-a < r_2 - r_1 = (q_2 - q_1)\cdot a < a$이고 $a > 0$이므로 부등식 정리로 $-1 < q_2 - q_1 < 1$이다. 

정수 정리로 $0 < c <1$ 또는 $-1 < c < 0$인 정수 $c \in \mathbb{Z}$는 존재하지 않고

정수집합의 정의로 $q_2 - q_1 \in \mathbb{Z}$이므로 $q_2 - q_1 = 0$이고 $a \ne 0$이므로 정수 정리로 $r_2 - r_1 = 0$이 되어

$b = q\cdot a + r $인 $q_1 = q_2 = q \in \mathbb{Z} $와 $r_1 = r_2 = r \in \mathbb{Z}$은 유일하다.

2.

$a < 0$일때 $-a > 0$이므로 $-a, b  \in \mathbb{Z}$에 대해 1번으로

$b = q\cdot (-a) + (-r) = (-q) \cdot a +(- r)$인 $-q, -r \in \mathbb{Z}$이 유일하게 존재하고 $0 \le -r < -a$이므로 $a < r \le 0$이다.

 

 

 

정리18

임의의 정수 $a,b \in \mathbb{Z}$에 대해 다음이 성립한다.

1. $ a >0$에 대해 $0 \le r < a$와 $b = q\cdot a + r$를 만족하는 $q,r \in \mathbb{Z}$이 존재할때

$r = 0$이면 $\dfrac{b}{a} \in \mathbb{Z}$이고 $r > 0$이면 $\dfrac{b}{a} \notin \mathbb{Z}$이다.

2. $a < 0$에 대해 $a<r \le 0$와 $b = q\cdot a + r$를 만족하는 $q,r \in \mathbb{Z}$이 존재할때

$r = 0$이면 $\dfrac{b}{a} \in \mathbb{Z}$이고 $r < 0$이면 $\dfrac{b}{a} \notin \mathbb{Z}$이다.

증명

$a \ne 0$인 $a \in \mathbb{Z}$는 유리수의 정의로 $a \in \mathbb{Q}$이고

유리수 정리로 $a \cdot \dfrac{1}{a} = a\cdot a^{-1} = 1$인 유리수 $a^{-1} = \dfrac{1}{a} \in \mathbb{Q}$가 존재하여

유리수 부등식 정리로 $a > 0$이면 $\dfrac{1}{a} > 0$이고 $a < 0$이면 $\dfrac{1}{a} < 0$이다.

$r = 0$이면 $b = q\cdot a + r = q\cdot a$이고 $a \ne 0$이므로 $\dfrac{b}{a} = q \in \mathbb{Z}$이다.

1.

$r > 0$이면 $b = q\cdot a + r$이고 $a > 0$이므로 $\dfrac{b}{a} = q + \dfrac{r}{a}$이다.

$0<r < a$이므로 부등식 정리로 $0<\dfrac{r}{a} < 1$이고 $q <  \dfrac{b}{a} = q + \dfrac{r}{a} < q + 1$이 되어

정수 정리로 $\dfrac{b}{a} \notin \mathbb{Z}$이다.

2.

$r < 0$이면 $b = q\cdot a + r$이고 $a < 0$이므로 $\dfrac{b}{a} = q + \dfrac{r}{a}$이다.

$a<r < 0$이므로 부등식 정리로 $0<\dfrac{r}{a} < 1$이고 $q < \dfrac{b}{a} = q + \dfrac{r}{a} < q + 1$이 되어 

정수 정리로 $\dfrac{b}{a} \notin \mathbb{Z}$이다.

 

 

 

정의2

임의의 정수 $a,b \in \mathbb{Z}$에 대해 $a \ne 0$일때

$b = q\cdot a$인 정수 $q \in \mathbb{Z}$가 존재하면 $b$를 $a$로 나눌 수 있다고 하고 $b / a \in \mathbb{Z}$로 표기한다.

$a$를 $b$의 약수(divisor)라고 정의하고 $b$를 $a$의 배수(multiple)라고 정의한다.

 

나눗셈 정리에 나온 $b = q\cdot a + r$이고 $0\le |r| < |a|$인

$q$를 $b$를 $a$로 나누었을 때의 몫(quotient)이라 하고

$r$을 $b$를 $a$로 나누었을 때의 나머지(remainder)라 한다.

나머지가 $r \ne 0$이면 $b$를 $a$로 나눌 수 없다고 하고 $b / a \notin \mathbb{Z}$로 표기한다.

 

 

 

정리2

임의의 정수 $a,b,c \in \mathbb{Z}$에 대해 다음이 성립한다.

1. $a / 1 \in \mathbb{Z}$

2. $a\ne 0$일때 $0/ a\in \mathbb{Z}$이고 $a / a\in \mathbb{Z}$이다.

3. $a\ne 0$일때 $1 / a \in \mathbb{Z}$이기 위한 필요충분조건은 $a = 1$이거나 $a = -1$인 것이다.

4. $a\ne 0$이고 $c \ne 0$일때 $b / a \in \mathbb{Z}$이고 $d / c \in \mathbb{Z}$이면 $(b\cdot d) / (a\cdot c) \in \mathbb{Z}$이다.

5. $a\ne 0$이고 $b \ne 0$일때 $b / a \in \mathbb{Z}$이고 $c/b \in \mathbb{Z}$이면 $c /a\in \mathbb{Z}$이다.

6. $a\ne 0$이고 $b \ne 0$일때 $b / a\in \mathbb{Z}$이고 $a /b\in \mathbb{Z}$이기 위한 필요충분조건은 $a = b$이거나 $a = -b$인 것이다.

7. $a\ne 0$일때 $b / a\in \mathbb{Z}$이고 $b \ne 0$이면 $|a| \le |b|$이다.

8. $a\ne 0$일때 $b / a\in \mathbb{Z}$이고 $c /a\in \mathbb{Z}$이면 모든 $x , y \in \mathbb{Z}$에 대해 $(b\cdot x + c\cdot y) / a \in \mathbb{Z}$이다.

9. $a\ne 0$일때 $b / a \in \mathbb{Z}$와 $ |b|/a \in \mathbb{Z}$와 $b/|a| \in \mathbb{Z}$는 동치이다.

증명

1.

$a = a \cdot 1$이므로 $a/1 \in \mathbb{Z}$이다.

2.

$0 = 0\cdot a$이므로 $ 0 / a \in \mathbb{Z}$이고

$a = 1\cdot a$이므로 $a/a \in \mathbb{Z}$이다.

3.

$a = 1$이면 $1 = 1\cdot 1$로 $1/a \in \mathbb{Z}$이고 $a = -1$이면 $1 = (-1) \cdot (-1)$로 $ 1/a \in \mathbb{Z}$이다.

역으로 $1 / a \in \mathbb{Z}$이면 $1 = q \cdot a$인 $q \in \mathbb{Z}$가 존재하고

모든 $n \in \mathbb{Z}^+$은 $n\ne 0$이고 $n = 0+n$이므로 부등식의 정의로 $n > 0$이고 부등식 덧셈 정리로 $n +1  > 1$이다.

부등식 정리로 임의의 $p \in \mathbb{Z}^+$에 대해 $(n+1)\cdot (p+1) > 1\cdot (p +1 ) = p +1 > 1$이므로

$1$보다 큰 모든 두 정수의 곱은 $1$이 아니다.

부등식 정리로 $ - n - 1 = -(n+1)< -1 $이고 $ (- (n+1)) \cdot (-(p+1)) > (-1)\cdot (-(p+1)) = p+1 > 1$이므로

$-1$보다 작은 모든 두 정수의 곱도 $1$이 아니다.

또 부등식 정리와 곱셈 정리로 $(-(n+1))\cdot (p+1) =(n+1) \cdot (-(p+1))  < -1$이므로 남은 정수는 $ -1, 0 , 1 $인데

$a \ne 0$이고 $1\cdot 1 = 1 = (-1)\cdot (-1)$이 성립하므로 $a = 1$ 또는 $a = -1$이다.

4.

$b / a \in \mathbb{Z}$이고 $d / c \in \mathbb{Z}$이면 $b = q_1\cdot a$이고 $d = q_2\cdot c$인 정수 $q_1, q_2 \in \mathbb{Z} $가 존재하므로

양변을 곱하면 $b\cdot d = (q_1 \cdot q_2) \cdot (a\cdot c)$이고 $q_1\cdot q_2 \in \mathbb{Z}$이므로 $(b\cdot d) / (a\cdot c) \in \mathbb{Z}$이다.

5.

$b / a\in \mathbb{Z}$이고 $c/b\in \mathbb{Z}$이면 3번으로 $(b\cdot c)/ (b\cdot a) \in \mathbb{Z}$이므로

$b\cdot c = q \cdot (b\cdot a) = b\cdot (q\cdot a) $인 $q \in \mathbb{Z}$가 존재하고 $c = q \cdot a$가 되어 $c / a \in \mathbb{Z}$이다.

6.

$a =b$이면 2번으로 $b / a \in \mathbb{Z}$이고 $a /b \in \mathbb{Z}$이다.

$a = -b$이면 $a =(-1)\cdot b$이므로 $a / b \in \mathbb{Z}$이고 $b = (-1)\cdot a$이므로 $b/a \in \mathbb{Z}$이다.

역으로 $b / a \in \mathbb{Z}$이고 $a /b \in \mathbb{Z}$이면

$b = q_1 \cdot a$이고 $a = q_2 \cdot b$인 정수 $q_1, q_2 \in \mathbb{Z} $가 존재하여

$a = q_2\cdot b = q_2 \cdot (q_1 \cdot a) = q_1\cdot q_2 \cdot a$이므로 $q_1 \cdot q_2 = 1$이다.

따라서 $q_1 = 1 = q_2$이거나 $q_1 = -1 = q_2$이 되어 $a = b$이거나 $a = -b$이다.

7.

$b / a \in \mathbb{Z}$이고 $b \ne 0$이면 $b  = q \cdot a$인 정수 $q \in \mathbb{Z}$가 존재하여

$q = 0$이면 $b = 0$이 되어 모순이므로 $q \ne 0$이고

절댓값 정리로 $|q| \ge 0$이므로 부등식의 정의로 $|q |>0$이고 자연수 부등식 정리로 $|q| \ge 1 $이다.

따라서 절댓값 정리로 $|b| = |q\cdot a| = |q|\cdot |a|$이고

절댓값 정리로 $|a| \ge 0$에 대해 부등식 곱셈 정리로 $|b| = |q|\cdot |a| \ge 1 \cdot |a| = |a|$이다.

8.

$b / a \in \mathbb{Z}$이고 $c /a \in \mathbb{Z}$이면 $b = q_1 \cdot a$이고 $c = q_2 \cdot a$인 정수 $q_1, q_2 \in \mathbb{Z} $가 존재하여

모든 $x , y \in \mathbb{Z}$에 대해 $b\cdot x + c\cdot y = (q_1\cdot a) \cdot x + (q_2\cdot a)\cdot y = (q_1\cdot x + q_2\cdot y)\cdot a$이고

$q_1\cdot x + q_2\cdot y \in \mathbb{Z}$이므로 $(b\cdot x + c\cdot y) / a \in \mathbb{Z}$이다.

9.

$b/a \in \mathbb{Z} \leftrightarrow |b| / a\in \mathbb{Z}$

$b/a \in \mathbb{Z}$이면 $b = q\cdot a$인 정수 $q \in \mathbb{Z}$가 존재하여 절댓값 정리로 $|b| = |q\cdot a| = |q|\cdot |a|$이므로

절댓값의 정의로

$a > 0$이면 $|a| = a$이고 $|b| = |q|\cdot |a| = |q| \cdot a$가 되어 $|b| / a \in \mathbb{Z}$이고

$a < 0$이면 $|a| = -a$이므로 $|b| = |q|\cdot |a|  = |q|\cdot (-a) = -|q| \cdot a$가 되어 $|b| / a \in \mathbb{Z}$이다.

역으로 $|b| /a \in \mathbb{Z}$이면 $|b| = q\cdot a$인 정수 $q \in \mathbb{Z}$가 존재하여

$b \ge 0$이면 $b =|b| = q\cdot a$이므로 $b/a \in \mathbb{Z}$이고

$b < 0$이면 $-b = |b| = q\cdot a$이므로 $b = -q\cdot a$가 되어 $b/a \in \mathbb{Z}$이다.

$b/a \in \mathbb{Z} \leftrightarrow b / |a| \in \mathbb{Z}$

$b/a \in \mathbb{Z}$이면 $b = q\cdot a$인 정수 $q \in \mathbb{Z}$가 존재하여 절댓값 정리로 $|b| = |q\cdot a| = |q|\cdot |a|$이므로

$b \ge 0$이면 $b =|b| = |q|\cdot |a|$이므로 $b/|a| \in \mathbb{Z}$이고

$b < 0$이면 $-b = |b| = |q|\cdot |a|$이므로 $b = -|q|\cdot |a|$가 되어 $b/|a| \in \mathbb{Z}$이다.

역으로 $b/|a| \in \mathbb{Z}$이면 $b = q\cdot |a|$인 정수 $q \in \mathbb{Z}$가 존재하여

$a > 0$이면 $|a| = a$이고 $b = q\cdot |a| = q \cdot a$가 되어 $b / a \in \mathbb{Z}$이고

$a < 0$이면 $|a| = -a$이므로 $b = q\cdot (-a) = -q \cdot a$가 되어 $b / a \in \mathbb{Z}$이다.

 

 

 

정의3

최대 공약수(greatest common divisor) :

$a\ne 0$ 또는 $b \ne 0$인 임의의 정수 $a,b \in \mathbb{Z}$에 대해 

$a / d \in \mathbb{Z}$와 $b / d \in \mathbb{Z}$가 성립하는 영이 아닌 정수 $d \in  $ $\mathbb{Z} \setminus \{ 0\}$를 $a$와 $b$의 공약수(common divisor)로 정의하고

$\gcd(a,b) = $ $\max$$\{ d \in \mathbb{Z}^+ : a / d \in \mathbb{Z} \text{ 이고 } b / d \in \mathbb{Z} \}$를 최대 공약수로 정의한다.

최소 공배수(least common multiple) :

임의의 영이 아닌 정수 $a,b \in \mathbb{Z} \setminus \{ 0 \}$에 대해 

$m / a \in \mathbb{Z}$와 $m / b \in \mathbb{Z}$가 성립하는 양의 정수 $m \in \mathbb{Z}^+$을 $a$와 $b$의 공배수(common multiple)로 정의하고

$\operatorname{lcm}(a,b) = $ $\min$$\{ m \in \mathbb{Z}^+ : m / a \in \mathbb{Z} \text{ 이고 } m / b\in \mathbb{Z} \}$를 최소 공배수로 정의한다.

 

 

 

정리4(베주[Bézout] 항등식)

$a \ne 0 $ 또는 $b \ne 0$인 임의의 정수 $a,b \in \mathbb{Z}$에 대해 $\gcd(a,b)$가 유일하게 존재하여

$\gcd(a,b) = a\cdot x + b\cdot y$가 되는 정수 $x,y \in \mathbb{Z}$가 존재한다.

증명

일반성을 잃지 않고 $a \ne 0$이라 가정하면 절댓값은 $|a| = a$ 또는 $|a| = -a$이고 $|a| > 0$이므로

$S = \{ a\cdot u + b\cdot v  : u,v \in \mathbb{Z} \text{ 이고 }  a\cdot u + b\cdot v > 0 \} \subseteq \mathbb{Z}$인 집합은 $v = 0$일때

$a\cdot u + b\cdot v = a\cdot u = |a| > 0$이 되는 $u = 1$ 또는 $u  = -1$인 정수 $u \in \mathbb{Z}$가 존재하여 $S$는 공집합이 아니다.

또 $a\cdot u + b\cdot v \in \mathbb{Z}$이고 $a\cdot u + b\cdot v > 0$이므로 정수 부등식 정리로 $a\cdot u + b\cdot v \in \mathbb{Z}^+$이 되어

정렬성으로 모든 $s \in S$에 대해 $d \le s$인 최소원소 $d \in S$가 유일하게 존재하고

$d \in S$이므로 $d = a\cdot x + b\cdot y$인 정수 $x,y \in \mathbb{Z}$가 존재한다.

$d > 0$이므로 나눗셈 정리로 $a = q\cdot d + r$와 $0\le r < d$를 만족하는 정수 $q,r\in \mathbb{Z}$이 존재하고

$r = a - q\cdot d = a - q\cdot (a\cdot x + b\cdot y) = a\cdot (1 -q\cdot x) + b\cdot (-q\cdot y)$이다.

$r =  a\cdot (1 -q\cdot x) + b\cdot (-q\cdot y) > 0$이면 $r \in S$인데 $r < d$이므로

$d$가 $S$의 최소원소라는 가정에 모순이 되어 $r = 0$이고 $a = q\cdot d$이다.

따라서 $a / d \in \mathbb{Z}$가 성립하고 $b = 0$이면 위 정리로 $0/ d\in \mathbb{Z}$이고 $b \ne 0$이면 $a$처럼 $b/d\in \mathbb{Z}$임을 보일 수 있으므로

$a /d\in \mathbb{Z}$와 $b/d\in \mathbb{Z}$가 성립하여 $d \in \mathbb{Z}^+$는 $a,b$의 공약수이다.

$a/ c\in \mathbb{Z}$이고 $b /c\in \mathbb{Z}$인 임의의 정수 $c \in \mathbb{Z}$에 대해 위 정리로 $(a\cdot x + b\cdot y) / c \in \mathbb{Z}$가 성립하므로 $d / c \in \mathbb{Z}$이고

$d > 0$이므로 위 정리로 $c \le |c| \le |d| = d $가 되어 $d$는 $a$와 $b$를 나누는 수 중 가장 큰 수이므로

$\gcd(a,b) = d = a\cdot x + b\cdot y$가 성립한다.

 

 

 

정리3

모든 $a,b \in \mathbb{Z}$에 대해 다음이 성립한다.

1. $a \ne 0 $ 또는 $b \ne 0$이면 $\gcd(a,b) \in \mathbb{Z}^+$이 유일하게 존재한다.

2. $a \ne 0 $이고 $b \ne 0$이면 $\operatorname{lcm}(a,b) \in \mathbb{Z}^+$이 유일하게 존재한다.

3. $a \ne 0 $ 또는 $b \ne 0$이면 $\gcd(a,b) = \gcd(b,a)$이다.

4. $a \ne 0 $이고 $b \ne 0$이면 $\operatorname{lcm}(a,b) = \operatorname{lcm}(b,a)$이다.

5. $a \ne 0 $이면 $\gcd(a, 0) = |a| = \gcd(a,a)$이다.

6. $\gcd(a,1) = 1$

7. $b \ne 0$이고 $a / b \in \mathbb{Z}$이면 $\gcd(a,b) = |b|$이다.

증명

1.

위 정리로 $a / 1 \in \mathbb{Z}$이고 $b / 1 \in \mathbb{Z}$이므로 $G = \{ d \in \mathbb{Z}^+ : a / d \in \mathbb{Z} \text{ 이고 } b / d \in \mathbb{Z} \}$인 집합은 공집합이 아니고

$a \ne 0 $ 또는 $b \ne 0$이면

위 정리로 모든 $n \in G$에 대해 $|n| \le |a|$이거나 $|n| \le |b|$이므로 위로 유계가 되어 상한성으로 $\sup G \in \mathbb{R}$가 존재한다.

또 상한 정리로 $\sup G -1 < n_1 \le \sup G$인 $n_1 \in G$이 존재하고 정수집합의 순서성질로 $n_1 +1 \in \mathbb{Z}^+$이다.

부등식 덧셈 정리로 $\sup G -1 +1 = \sup G < n_1 +1$이므로 $n_1 \le \sup G < n_1 + 1$이고 

$n_1 < \sup G$라고 가정하면 상한 정리로 모든 $\epsilon > 0$에 대해 $\sup G - \epsilon < n_\epsilon \le \sup G$인 $n_\epsilon \in G$이 존재해야 하는데 

$n_1 < \sup G - \epsilon_0 < n_{\epsilon_0} \le \sup G < n_1 +1$인 임의의 $\epsilon_0 > 0$에 대해

정수 정리로 $n_{\epsilon_0}$은 정수일 수 없으므로 $n_{\epsilon_0} \notin G$이다.

따라서 $n_1 < \sup G$이면 모순이므로 $\sup G = n_1  \in G$가 되어 최대원소 정리로

$\gcd(a,b) = $ $\max$$\{ d \in \mathbb{Z}^+ : a / d \in \mathbb{Z}\text{ 이고 } b / d\in \mathbb{Z} \} = \max G=\sup G$가 유일하게 존재한다.

2.

절댓값 정리로 $|a \cdot b| \ge 0$에 대해

$a \ne 0 $이고 $b \ne 0$이면 $a\cdot b \ne 0$이므로 정수 부등식 정리로 $|a \cdot b| \in \mathbb{Z}^+$이고

$|a \cdot b| = q_1\cdot a$와 $|a \cdot b| = q_2\cdot b$를 만족하는 정수 $q_1, q_2 \in \mathbb{Z}$가 존재하여

$L = \{ m \in \mathbb{Z}^+ : m / a\in \mathbb{Z} \text{ 이고 } m / b\in \mathbb{Z} \}$인 집합은 공집합이 아니다.

따라서 $L \subseteq \mathbb{Z}^+$이므로 정렬성으로 

$\operatorname{lcm}(a,b) = $ $\min$$\{ m \in \mathbb{Z}^+ : m / a\in \mathbb{Z} \text{ 이고 } m / b \in \mathbb{Z}\} = \min L $이 유일하게 존재한다.

3.

$a \ne 0 $ 또는 $b \ne 0$이므로 베주 항등식으로 $\gcd(a,b)$가 존재하고

명제 정리로 $\{ d \in \mathbb{Z}^+ : (a / d \in \mathbb{Z}) \land (b / d \in \mathbb{Z}) \} = \{ d \in \mathbb{Z}^+ : (b / d \in \mathbb{Z}) \land (a / d \in \mathbb{Z}) \} $이므로

$\gcd(a,b) = \gcd(b,a)$이다.

4.

$a \ne 0 $이고 $b \ne 0$이므로 2번으로 $\operatorname{lcm}(a,b)$가 존재하고

명제 정리로 $\{ m \in \mathbb{Z}^+ : (m / a \in \mathbb{Z}) \land (m / b \in \mathbb{Z}) \} = \{ m \in \mathbb{Z}^+ : (m / b \in \mathbb{Z}) \land (m / a \in \mathbb{Z}) \} $이므로

$\operatorname{lcm}(a,b) = \operatorname{lcm}(b,a)$이다.

5.

$a \ne 0 $이므로 베주 항등식으로 $\gcd(a,0) = $ $\max$$\{ d \in \mathbb{Z}^+ : a / d\in \mathbb{Z} \text{ 이고 } 0 / d\in \mathbb{Z} \}$이 존재하고

위 정리로 모든 $n\in \mathbb{Z}^+$에 대해 $0/n\in \mathbb{Z}$이 성립하므로 $G = \{ d \in \mathbb{Z}^+ : a/d \in \mathbb{Z} \}$로 둘때 $\gcd(a, 0) = \max G$이다.

모든 $d \in G$에 대해 $d > 0$이고 $a / d\in \mathbb{Z}$이므로 위 정리로 $d = |d| \le |a|$이고 절댓값은 $|a| \in \mathbb{Z}$이다.

$a\ne 0$이므로 $|a | > 0$이 되어 정수 부등식 정리로 $|a| \in \mathbb{Z}^+$이고 $|a| = q\cdot a$인 $q \in \mathbb{Z}$가 존재하므로 $|a| \in G$이다.

따라서 모든 $d \in G$에 대해 $d  \le |a|$이고 $|a| \in G$이므로 최대원소의 정의로 $\gcd(a, 0) = \max G = |a|$가 성립한다.

또 $\gcd(a,a) = \max \{ d \in \mathbb{Z}^+ : a/d \in \mathbb{Z} \text{ 이고 } a/d \in \mathbb{Z}\} = \max G = \gcd(a,0) = |a|$이다.

6.

$1 \ne 0$이므로 베주 항등식으로 모든 $a \in \mathbb{Z}$에 대해 $\gcd(a,1) = d \in \mathbb{Z}^+$가 존재하여

$1 / d\in \mathbb{Z}$이고 $d \in \mathbb{Z}^+$이므로 위 정리로 $d = 1$이다.

7.

$b \ne 0$이므로 베주 항등식으로 모든 $a \in \mathbb{Z}$에 대해 $\gcd(a,b) = d  \in \mathbb{Z}^+$가 존재하여

$ b /d \in \mathbb{Z}$이므로 위 정리로 $d =|d| \le |b|$이고

$a / b , b/b \in \mathbb{Z}$이므로 위 정리로 $a / |b| , b/ |b| \in \mathbb{Z}$가 되어 최대공약수의 정의로 $\gcd(a,b)=d = |b| $이다.

 

 

 

정리5

$a \ne 0 $ 또는 $b \ne 0$인 임의의 정수 $a,b \in \mathbb{Z}$에 대해 집합 $T = \{ a\cdot x + b\cdot y : x,y \in \mathbb{Z} \}\subseteq \mathbb{Z}$가 정의되면

모든 $c \in T$에 대해 $c / \gcd(a,b) \in \mathbb{Z}$가 성립한다.

증명

최대공약수의 정의로 $a / \gcd(a,b) \in \mathbb{Z}$이고 $b/\gcd(a,b) \in \mathbb{Z}$이므로 

위 정리로 모든 $x , y \in \mathbb{Z}$에 대해 $(a\cdot x + b\cdot y) / \gcd(a,b) \in \mathbb{Z}$이다.

따라서 모든 $c \in T$에 대해 $c / \gcd(a,b) \in \mathbb{Z}$가 성립한다.

 

 

 

정의4

$\gcd(a,b) $ $ = 1$이 되는 $a \ne 0 $ 또는 $b \ne 0$인 정수 $a,b \in \mathbb{Z}$가 존재할때

$a$와 $b$를 서로소(relative prime)라고 정의한다. 

 

 

 

정리6

$a \ne 0 $ 또는 $b \ne 0$인 임의의 정수 $a,b \in \mathbb{Z}$에 대해

$a$와 $b$가 서로소이기 위한 필요충분조건은 $a\cdot x + b\cdot y = 1$이 되는 정수 $x,y \in \mathbb{Z}$가 존재하는 것이다.

증명

$a$와 $b$가 서로소이면

$\gcd(a,b) $ $ = 1$이고 위 정리로 $\gcd(a,b) $ $= 1= a\cdot x + b\cdot y$가 되는 정수 $x,y \in \mathbb{Z}$가 존재한다.

역으로 $a\cdot x + b\cdot y = 1$이 되는 정수 $x,y \in \mathbb{Z}$가 존재할때

최대공약수의 정의로 $a / \gcd(a,b) \in \mathbb{Z}$이고 $b/\gcd(a,b) \in \mathbb{Z}$이므로

위 정리로 $(a\cdot x + b\cdot y) / \gcd(a,b) \in \mathbb{Z}$이고 $1/\gcd(a,b) \in \mathbb{Z}$이다.

따라서 $1 = q\cdot \gcd(a,b)$인 정수 $q \in \mathbb{Z}$가 존재하고 $\gcd(a,b)$는 양의 정수이므로

$q = 1$이고 $1 = \gcd(a,b)$이 되어 $a$와 $b$는 서로소이다.

 

 

 

정리7

$a \ne 0 $ 또는 $b \ne 0$인 임의의 정수 $a,b \in \mathbb{Z}$에 대해

$\gcd(a,b) $ $= d$이면 $\dfrac{a}{d},\dfrac{b}{d} \in \mathbb{Z}$이고 $\gcd(\frac{a}{d}, \frac{b}{d}) = 1$이다.

증명

$ \gcd(a,b) = d$이면 $a / d\in \mathbb{Z}$이고 $b/d \in \mathbb{Z}$이므로 $a = q_1\cdot d$이고 $b = q_2 \cdot d$인 정수 $q_1, q_2 \in \mathbb{Z}$가 존재하고

최대공약수의 정의로 $d \in \mathbb{Z}^+$는 양의 정수이므로 $d \ne 0$이고 유리수의 정의로 $d \in \mathbb{Q}$이므로

유리수 정리로 곱셈역원 $d^{-1} = \dfrac{1}{d} \in \mathbb{Q}$이 존재하여 $ \dfrac{a}{d} = q_1 \in \mathbb{Z}$이고 $ \dfrac{b}{d} = q_2 \in \mathbb{Z}$이다.

또 $a \ne 0 $ 또는 $b \ne 0$이고 $d \ne 0$이므로 유리수의 정의로 $\dfrac{a}{d},\dfrac{b}{d} \in \mathbb{Q}$이고 $\dfrac{a}{d} \ne 0$ 또는 $ \dfrac{b}{d} \ne 0$이다.

따라서 위 정리로 $d = \gcd(a,b) = a\cdot x + b\cdot y$인 정수 $x,y \in \mathbb{Z}$가 존재하고

$1 = \dfrac{a}{d}\cdot x + \dfrac{b}{d}\cdot y$가 되어 서로소 정리로 $\gcd(\frac{a}{d}, \frac{b}{d}) = 1$이다.

 

 

 

정리8

$a \ne 0 $이고 $b \ne 0$인 임의의 정수 $a,b \in \mathbb{Z}$가 $\gcd(a,b) $ $= 1$일때 $c / a \in \mathbb{Z}$이고 $c/ b \in \mathbb{Z}$이면 $c / (a\cdot b) \in \mathbb{Z}$이다.

증명

위 정리로 $1 = \gcd(a,b) = a\cdot x + b\cdot y$인 정수 $x,y \in \mathbb{Z}$가 존재하고

$c / a\in \mathbb{Z}$이고 $c/ b\in \mathbb{Z}$이므로 $c = q_1\cdot a$와 $c = q_2\cdot b$가 성립하는 정수 $q_1,q_2 \in \mathbb{Z}$가 존재하여

$\begin{align*}c  &= c\cdot 1\\[0.5em] & = c\cdot (a\cdot x + b\cdot y) \\[0.5em] & = c\cdot a \cdot x + c\cdot b\cdot y \\[0.5em] & = (q_2\cdot b)\cdot a\cdot x + (q_1\cdot a)\cdot b\cdot y \\[0.5em] & = q_2\cdot x \cdot (a\cdot b) + q_1 \cdot y\cdot (a\cdot b) \\[0.5em] & =  (q_2\cdot x + q_1\cdot y) \cdot (a\cdot b) \text{ 이고 }\end{align*}$

$q_2\cdot x + q_1\cdot y \in \mathbb{Z}$이므로 $c / (a\cdot b)\in \mathbb{Z}$이다.

 

 

 

정리9(유클리드[Euclid] 보조정리)

$a \ne 0 $인 임의의 정수 $a,b \in \mathbb{Z}$가 $\gcd(a,b) $ $= 1$이고 $(b\cdot c) / a \in \mathbb{Z}$이면 $c / a \in \mathbb{Z}$이다.

증명

위 정리로 $1 = \gcd(a,b) = a\cdot x + b\cdot y$인 정수 $x,y \in \mathbb{Z}$가 존재하여

$c = c\cdot 1 = c\cdot (a\cdot x + b\cdot y) = a\cdot c\cdot x + b\cdot c \cdot y$이다.

따라서 $(a\cdot c) / a \in \mathbb{Z}$임은 자명하고 $(b\cdot c) /a \in \mathbb{Z}$를 가정하였으므로

위 정리로 $(a\cdot c \cdot x + b\cdot c\cdot y) / a \in \mathbb{Z}$가 되어 $c/a \in \mathbb{Z}$이다.

 

 

 

정리10

$a \ne 0 $ 또는 $b \ne 0$인 임의의 정수 $a,b \in \mathbb{Z}$에 대해 

양의 정수 $d \in \mathbb{Z}^+$가 $\gcd(a,b) $ $= d$이기 위한 필요충분조건은 다음을 모두 만족하는 것이다.

1. $a / d \in \mathbb{Z}$이고 $b / d \in \mathbb{Z}$이다.

2. $a/c \in \mathbb{Z}$와 $b/c \in \mathbb{Z}$가 성립하는 $0$이 아닌 모든 정수 $c \in $ $\mathbb{Z} \setminus \{ 0\}$에 대해 $d / c \in \mathbb{Z}$이다.

증명

$\gcd(a,b) = d$이면

최대공약수의 정의로 $a / d \in \mathbb{Z}$와 $b / d \in \mathbb{Z}$가 성립하고

위 정리로 $d = \gcd(a,b) = a\cdot x + b\cdot y$인 정수 $x,y \in \mathbb{Z}$가 존재한다.

따라서 $a/c \in \mathbb{Z}$이고 $b/c\in \mathbb{Z}$인 모든 정수 $c \in \mathbb{Z} \setminus \{0\}$가 존재하면

위 정리로 $(a\cdot x + b\cdot y) /c \in \mathbb{Z}$이므로 $d /c \in \mathbb{Z}$이다.

역으로 조건 1,2가 만족하면

$a/c \in \mathbb{Z}$이고 $b/c \in \mathbb{Z}$인 모든 정수 $c \in \mathbb{Z} \setminus \{ 0 \}$에 대해 $d / c \in \mathbb{Z}$이므로

위 정리로 $c \le |c| \le |d| = d$가 되어 $d = \gcd(a,b)$이다.

 

 

 

정리11

$b \ne 0$이고 $a = q\cdot b + r$인 임의의 정수 $a,b,q,r \in \mathbb{Z}$에 대해 $\gcd(a,b) $ $=  \gcd(b,r)$이다.

증명

$b \ne 0$이므로 베주 항등식으로 $\gcd(a,b) = d \in \mathbb{Z}^+$가 존재하여

위 정리로 $a / c\in \mathbb{Z}$이고 $b/c \in \mathbb{Z}$인 모든 $c \in \mathbb{Z} \setminus \{0 \}$에 대해 $d/ c\in \mathbb{Z}$이다.

최대공약수의 정의로 $a / d\in \mathbb{Z}$와 $b / d\in \mathbb{Z}$가 성립하므로 위 정리로 $(a - q\cdot b) / d\in \mathbb{Z}$가 되어 $r/d\in \mathbb{Z}$이다.

따라서 $\gcd(a,b) = d$는 $b/d\in \mathbb{Z}$와 $r/d\in \mathbb{Z}$가 성립하고

$b/c\in \mathbb{Z}$이고 $r/c\in \mathbb{Z}$인 모든 $c \in \mathbb{Z} \setminus \{0 \}$는 위 정리로 $(q\cdot b +r) / c\in \mathbb{Z}$가 되어 $a/c\in \mathbb{Z}$이므로 $d/c\in \mathbb{Z}$이고

위 정리로 $\gcd(a,b) = d = \gcd(b,r)$이다.

 

 

 

정리12(유클리드[Euclid] 호제법)

$r_0 \ne 0$인 임의의 정수 $r_{-1} , r_0 \in \mathbb{Z}$와 어떤 $n \in \mathbb{N}$에 대해

$r_{-1} = q_0\cdot r_0 +  r_1,$ 

$r_0 = q_1\cdot r_1 +  r_2,$

$r_1 = q_2\cdot r_2 + r_3,$

           $\vdots$

$r_{n-1} = q_n\cdot r_n + r_{n+1} = q_n\cdot r_n + 0$이고

$\gcd(r_{-1},r_0) $ $= \gcd(r_0,r_1) = \gcd(r_1,r_2) = \cdots = \gcd(r_{n-1},r_n) = \gcd(r_n,r_{n+1}) = \gcd(r_n, 0) = |r_n|$인

유한개의 정수 $q_0,q_1,\cdots q_{n},r_0, r_1,\cdots r_n, r_{n+1} = 0 \in \mathbb{Z}$이 존재한다.

이때 $r_0 > 0$이면 $r_0 > r_1 > r_2 > \cdots > r_n  > 0$이고 $r_0 < 0$이면 $  r_0 < r_1 <r_2 < \cdots < r_n < 0$이다.

증명

$n \ge m \ge 0$인 정수 $m \in \mathbb{Z}$에 대해 $r_m > 0$이라고 가정하면

나눗셈 정리로 $r_{m-1} = q_m\cdot r_m +  r_{m+1}$이고 $0\le r_{m+1} < r_m$인 $q_m,r_{m+1} \in \mathbb{Z}$이 존재하여

위 정리로 $\gcd(r_{m-1},r_m ) = \gcd(r_m,r_{m+1})$이다.

$r_{m+1} = 0$이면 $r_{m-1} =  q_m \cdot r_m$이고 $ r_m > 0$이므로

위 정리로 $\gcd(r_{m-1},r_m ) = \gcd(r_m,r_{m+1}) = \gcd(r_m,0) = |r_m| = r_m$이다.

$r_{m+1} > 0$이면 위 과정을 반복하여 $r_n > 0$일때

나눗셈 정리로 $r_{n-1} = q_n\cdot r_n +  r_{n+1}$이고 $0\le r_{n+1} < r_n<\cdots < r_2 < r_1 < r_0$인 $q_n, r_{n+1} \in \mathbb{Z}$이 존재하고

위 정리로 $\gcd(r_{-1},r_0 ) = \gcd(r_0,r_1) = \gcd(r_1,r_2) = \cdots = \gcd(r_{n-1},r_n) = \gcd(r_n,r_{n+1})$이다.

$r_{n+1} = 0$이면 $r_{n-1} =  q_n \cdot r_n$이고 $ r_n > 0$이므로 위 정리로

$\gcd(r_{-1},r_0)= \gcd(r_0,r_1) = \gcd(r_1,r_2) = \cdots = \gcd(r_{n-1},r_n) = \gcd(r_n, r_{n+1}) = \gcd(r_n,0) = |r_n| = r_n$이다.

$r_{n+1} = r_{k} = 0$이 되는 양의 정수 $k \in \mathbb{Z}^+$가 존재하지 않는다고 가정하면

모든 $k \in \mathbb{Z}^+$에 대해 $0< \cdots < r_{k+1} < r_k < \cdots < r_1< r_0$이므로 무한강하법에 모순이다.

따라서 $r_{n+1}=r_k = 0$이 되는 양의 정수 $k \in \mathbb{Z}^+$가 존재하여 정리가 성립한다.

 

비슷하게 $n \ge m \ge 0$인 정수 $m \in \mathbb{Z}$에 대해 $r_m < 0$이라고 가정하면

나눗셈 정리로 $r_{m-1} = q_m\cdot r_m +  r_{m+1}$이고 $r_m< r_{m+1} \le 0$인 $q_m,r_{m+1} \in \mathbb{Z}$이 존재하여

위 정리로 $\gcd(r_{m-1},r_m ) = \gcd(r_m,r_{m+1})$이다.

$r_{m+1} = 0$이면 $r_{m-1} =  q_m \cdot r_m$이고 $ -r_m > 0$이므로

위 정리로 $\gcd(r_{m-1},r_m ) = \gcd(r_m,r_{m+1}) = \gcd(r_m,0) = |r_m| = -r_m$이다.

$r_{m+1} < 0$이면 위 과정을 반복하여 $r_n < 0$일때

나눗셈 정리로 $r_{n-1} = q_n\cdot r_n +  r_{n+1}$이고 $ r_0<r_1<r_2 <\cdots<r_n <r_{n+1} \le  0$인 $q_n, r_{n+1} \in \mathbb{Z}$이 존재하고

위 정리로 $\gcd(r_{-1},r_0 ) = \gcd(r_0,r_1) = \gcd(r_1,r_2) = \cdots = \gcd(r_{n-1},r_n) = \gcd(r_n,r_{n+1})$이다.

$r_{n+1} = 0$이면 $r_{n-1} =  q_n \cdot r_n$이고 $ -r_n > 0$이므로 위 정리로

$\gcd(r_{-1},r_0)= \gcd(r_0,r_1) = \gcd(r_1,r_2) = \cdots = \gcd(r_{n-1},r_n) = \gcd(r_n, r_{n+1}) = \gcd(r_n,0) = |r_n| = -r_n$이다.

 

 

 

정리13

$a \ne 0 $ 또는 $b \ne 0$인 모든 정수 $a,b \in \mathbb{Z}$에 대해 

임의의 정수 $k \in \mathbb{Z}$가 $k \ne 0$이면 $\gcd(k\cdot a,k \cdot b) $ $ = |k|\cdot \gcd(a,b)$이다.

증명

일반성을 잃지 않고 $b \ne 0$이라 가정하면 위 정리로 

$a = q_0\cdot b +  r_1,$ 

$b = q_1\cdot r_1 +  r_2,$

$r_1 = q_2\cdot r_2 + r_3,$

           $\vdots$

$r_{n-1} = q_n\cdot r_n + 0$이고

 $ \gcd(a,b)= \gcd(b,r_1) = \gcd(r_1,r_2) = \cdots = \gcd(r_{n-1},r_n) = \gcd(r_n, 0) = |r_n|$인

유한개의 정수 $q_0,q_1,\cdots q_{n},r_1,\cdots r_n, \in \mathbb{Z}$이 존재하고 $b,r_1,r_2,\cdots ,r_n$은 모두 $0$이 아니다.

따라서 $k\ne 0$이면 $k\cdot b, k\cdot r_1,k\cdot r_2,\cdots , k\cdot r_n$은 모두 $0$이 아니므로 위 식에 $k$를 곱하여

$k\cdot a = q_0\cdot (k\cdot b) +  k\cdot r_1,$ 

$k\cdot b = q_1\cdot (k\cdot r_1) + k\cdot r_2,$

$k\cdot r_1 = q_2\cdot (k\cdot r_2) + k\cdot r_3,$

           $\vdots$

$k\cdot r_{n-1} = q_n\cdot (k\cdot r_n) + 0$이고 위 정리로

$ \gcd(k\cdot a,k\cdot b)= \gcd(k\cdot b,k\cdot r_1) = \gcd(k\cdot r_1,k\cdot r_2) = \cdots = \gcd(k\cdot r_{n-1},k\cdot r_n) = \gcd(k\cdot r_n, 0) = |k\cdot r_n| \text{ 이 되어} $

절댓값 정리로 $\gcd(k\cdot a, k\cdot b)  = |k\cdot r_n| = |k|\cdot |r_n|= |k|\cdot \gcd(a,b)$이다.

 

 

 

정리14

$a \ne 0 $ 또는 $b \ne 0$인 모든 정수 $a,b \in \mathbb{Z}$에 대해 $\gcd( a, b) $ $ = \gcd(|a|,|b|)$이다.

증명

$a \ne 0 $ 또는 $b \ne 0$이므로 베주 항등식으로 $\gcd(a,b) = d \in \mathbb{Z}^+$가 존재하여

위 정리로 $a / c\in \mathbb{Z}$이고 $b/c \in \mathbb{Z}$인 모든 $c \in \mathbb{Z} \setminus \{0 \}$에 대해 $d/ c\in \mathbb{Z}$이다.

최대공약수의 정의로 $a / d\in \mathbb{Z}$와 $b / d\in \mathbb{Z}$가 성립하므로 위 정리로 $|a| / d\in \mathbb{Z}$이고 $|b|/d\in \mathbb{Z}$이다.

따라서 $\gcd(a,b) = d$는 $|a|/d\in \mathbb{Z}$와 $|b|/d\in \mathbb{Z}$가 성립하고

$|a|/c\in \mathbb{Z}$이고 $|b|/c\in \mathbb{Z}$인 모든 $c \in \mathbb{Z} \setminus \{0 \}$는 위 정리로 $a / c\in \mathbb{Z}$이고 $b/c\in \mathbb{Z}$가 되어 $d/c\in \mathbb{Z}$이므로

위 정리로 $\gcd(a,b) = d = \gcd(|a|,|b|)$이다.

 

 

 

정리15

$0$이 아닌 모든 정수 $a,b \in \mathbb{Z} \setminus \{ 0\}$에 대해 $\gcd(a,b) \cdot \operatorname{lcm}(a,b) $ $ = |a\cdot b|$이다.

증명

$a\ne 0$이고 $b \ne 0$이므로 베주 항등식으로 $\gcd(a,b) = d \in \mathbb{Z}^+$가 존재하고

$a / d\in \mathbb{Z}$와 $b/d\in \mathbb{Z}$가 성립하므로 $a = q_1\cdot d$이고 $b = q_2 \cdot d$인 영이 아닌 정수 $q_1,q_2 \in \mathbb{Z} \setminus \{ 0 \}$가 존재한다.

$d > 0$이므로 $|a|  = |q_1 \cdot d|= |q_1|\cdot d$와 $|b | = |q_2 \cdot d|= |q_2|\cdot d$가 성립하여

순서성질로 $\dfrac{|a|\cdot |b|}{d} = |q_1|\cdot |q_2| \cdot d \in \mathbb{Z}^+$이므로 $m = \dfrac{|a|\cdot |b|}{d} = |q_1|\cdot |q_2| \cdot d$으로 두면

$|b|\cdot |q_1| = m = |a|\cdot |q_2|$이고 $m/|a|\in \mathbb{Z}$와 $m/|b|\in \mathbb{Z}$는

위 정리로 $m/a\in \mathbb{Z}$와 $m/b\in \mathbb{Z}$가 되어 $m$은 $a$와 $b$의 공배수이다.

$a$와 $b$의 임의의 공배수 $c \in \mathbb{Z}^+$는 $c/a\in \mathbb{Z}$이고 $c/b\in \mathbb{Z}$이므로 $s_1\cdot a = c = s_2 \cdot b$인 정수 $s_1,s_2\in \mathbb{Z}$가 존재하고

$c > 0$이므로 $c = |c| = |s_1|\cdot |a| = |s_2|\cdot |b|$이다.

또 위 정리와 베주 항등식으로 $d = \gcd(a,b) = \gcd(|a|,|b|) = |a|\cdot x + |b|\cdot y$인 정수 $x,y \in \mathbb{Z}$가 존재하여

$\begin{align*} \frac{c}{m} &= |c| \cdot \frac{d}{|a|\cdot |b|} \\[0.5em] & = \frac{ |c| \cdot (|a|\cdot x + |b|\cdot y)}{|a|\cdot |b|} \\[0.5em] & = |c|\cdot \frac{|a|\cdot x}{|a|\cdot |b|} + |c|\cdot \frac{|b|\cdot y}{ |a|\cdot |b|} \\[0.5em] & = |s_2|\cdot |b|\cdot \frac{|a|\cdot x}{|a|\cdot |b|} + |s_1|\cdot |a|\cdot \frac{|b|\cdot y}{ |a|\cdot |b|} \\[0.5em] & = |s_2|\cdot x + |s_1|\cdot y \text{ 이다.} \end{align*}$

$|s_2|\cdot x + |s_1|\cdot y \in \mathbb{Z}$이므로 $c =  (|s_2|\cdot x + |s_2|\cdot y)\cdot m$이 되어 $c/ m\in \mathbb{Z}$이고

$a$와 $b$의 모든 공배수 $c \in \mathbb{Z}^+$에 대해 $c/m\in \mathbb{Z}$이므로 

위 정리로 $  0 < m= |m| \le |c| = c$가 되어 $m = \operatorname{lcm}(a,b)$이다.

따라서 $\operatorname{lcm}(a,b) = m = \dfrac{|a|\cdot |b|}{d} = \dfrac{|a|\cdot |b|}{\gcd(a,b)}$이므로 $\gcd(a,b) \cdot \operatorname{lcm}(a,b)  = |a\cdot b|$이다.

 

 

 

정리16

$0$이 아닌 모든 정수 $a,b \in \mathbb{Z} \setminus \{ 0\}$에 대해

$\operatorname{lcm}(a,b) $ $ = |a\cdot b|$이기 위한 필요충분조건은 $\gcd(a,b) $ $= 1$로 $a,b$가 서로소인 것이다.

증명

위 정리로 $\gcd(a,b) \cdot \operatorname{lcm}(a,b)  = |a\cdot b|$이므로

$ \operatorname{lcm}(a,b)  = |a\cdot b|$이면 $\gcd(a,b) = 1$이고 $\gcd(a,b) = 1$이면 $ \operatorname{lcm}(a,b)  = |a\cdot b|$이다.

 

 

 

정리17

임의의 양의 정수 $r  \in \mathbb{Z}^+$과 임의의 정수 $n_1,n_2,\cdots, n_r , N\in \mathbb{Z}$에 대해

모든 $i = 1,2,\cdots, r$가 $\gcd(N, n_i)$ $= 1$이기 위한 필요충분조건은 $ \gcd(N, n_1\cdot n_2 \cdot \; \cdots \; \cdot n_r ) = 1$인 것이다.

증명

$N = 0$일때

모든 $i = 1,2,\cdots, r$가 $\gcd(N,n_i) = 1$이면 위 정리로 $1 = \gcd(N,n_i) = \gcd(0,n_i) = |n_i|$이므로

$ \gcd(N, n_1\cdot n_2 \cdot \; \cdots \; \cdot n_r ) = \gcd(0,n_1\cdot n_2\cdot \; \cdots\; \cdot n_r) = |n_1|\cdot |n_2|\cdot \; \cdots \; \cdot |n_r| = 1$이다.

역으로 $ \gcd(N, n_1\cdot n_2 \cdot \; \cdots \; \cdot n_r ) = 1$이면 $ 1 =\gcd(N, n_1\cdot n_2 \cdot \; \cdots \; \cdot n_r ) = |n_1|\cdot |n_2|\cdot \; \cdots \; \cdot |n_r| $이므로

모든 $i = 1,2,\cdots, r$에 대해 $|n_i| = 1$이 되어 $\gcd(N,n_i) = \gcd(0,n_i) = |n_i| = 1$이다.

$N \ne 0$일때

$r = 1$이면 자명하게 성립하고 $r \ge 2$인 $r \in \mathbb{Z}^+$에 대해서는 귀납법을 사용한다.

$r = 2$일때 $ \gcd(N, n_1\cdot n_2) = 1$이면 

$\gcd(N,n_1) = d$는 $N /d \in \mathbb{Z}$이고 $n_1/d \in \mathbb{Z}$이므로 $n_1 =q\cdot d$인 $q \in \mathbb{Z}$가 존재하여

$n_1\cdot n_2 =(q\cdot n_2)\cdot d$이므로 $(n_1\cdot n_2)/d \in \mathbb{Z}$이고 최대공약수의 정의로 $ \gcd(N, n_1\cdot n_2) = 1 \ge d$임에 따라

$\gcd(N,n_1) = d = 1$이고 비슷하게 $\gcd(N,n_2) = 1$이다.

역으로 $\gcd(N,n_1) = 1 = \gcd(N,n_2)$일때

$n_1 = 0$ 또는 $n_2 = 0$이면 위 정리로 $1 =\gcd(N,0) = |N|$이고 $\gcd(N,n_1\cdot n_2) = \gcd(N,0) = |N| = 1$이다.

$n_1 \ne 0$이고 $n_2 \ne 0$일때 $\gcd(N,n_1\cdot n_2) = d > 1$이라고 가정하면

$0\ne N = d \cdot p$이고 $0 \ne n_1 \cdot n_2 = d\cdot q$인 $p,q \in \mathbb{Z}\setminus \{0\}$가 존재하므로

$d = \dfrac{N}{p}$이고 $n_1 \cdot n_2 = d\cdot q = \dfrac{N}{p}\cdot q$가 되어 $p\cdot n_1\cdot n_2 = N\cdot q$이므로 $(N \cdot q) /n_1  \in \mathbb{Z}$이다.

$\gcd(N,n_1) = 1$이므로 유클리드 보조정리로 $q / n_1 \in \mathbb{Z}$이고 $n_1 \cdot n_2 = d\cdot q = d\cdot n_1 \cdot k$인 $k \in \mathbb{Z} \setminus \{ 0 \}$가 존재하여

$n_2 = d\cdot k$이므로 $N / d \in \mathbb{Z}$이고 $n_2 / d \in \mathbb{Z}$인 $d > 1$가 존재하여 $\gcd(N,n_2) = 1$임에 모순이다.

따라서 $\gcd(N,n_1) = 1 = \gcd(N,n_2)$이기 위한 필요충분조건은 $\gcd(N, n_1\cdot n_2) = 1$인 것이다.

$m \ge 2$인 $m \in \mathbb{Z}^+$에 대해 정리가 성립한다고 가정할때

모든 $i = 1,2,\cdots, m,m+1$에 대해 $\gcd(N,n_i) = 1$이면

$\gcd(N, n_{m+1}) = 1$이고 귀납가정으로 $\gcd(N, n_1\cdot n_2 \cdot \; \cdots \; \cdot n_m ) = 1$이므로

$r = 2$일때처럼 $1 = \gcd(N, (n_1 \cdot n_2 \cdot \; \cdots \; \cdot n_m ) \cdot n_{m+1}) = \gcd(N,n_1\cdot n_2 \cdot \; \cdots \; \cdot n_m \cdot n_{m+1})$이다.

역으로 $\gcd(N,n_1\cdot n_2 \cdot \; \cdots \; \cdot n_m \cdot n_{m+1}) = 1$이면

$r = 2$일때처럼 $\gcd(N,n_1\cdot n_2 \cdot \; \cdots \; \cdot n_m) = 1 = \gcd(N,n_{m+1})$이고

귀납가정으로 모든 $i = 1,2,\cdots, m$에 대해 $\gcd(N,n_i) = 1$이므로 

모든 $i = 1,2,\cdots, m,m+1$에 대해 $\gcd(N,n_i) = 1$이다.

따라서 모든 $r \in \mathbb{Z}^+$에 대해 정리가 성립한다.

 

 

 

-------------------------------------------------------------------------------

정의의 링크 : 

https://openknowledgevl.tistory.com/49#def번호

번호는 해당 정의 옆에 붙어있는 작은 숫자입니다.

 

정리의 링크 : 

https://openknowledgevl.tistory.com/49#thm번호

번호는 해당 정리 옆에 붙어있는 작은 숫자입니다.

 

위 내용은 아래의 출처를 기반으로 정리한 내용입니다.

틀린 내용이 존재할 수 있습니다.

 

출처(저자 - 제목 - ISBN13)

David M. Burton - Elementary Number Theory - 9780073383149