나눗셈정리

Outline

나눗셈 정리

최대공약수

유클리드 알고리즘

디오판투스 방정식

---

나눗셈 정리

주어진 정수 a, b에 대해, b>0, 다음을 만족하는 유일한 정수 q, r이 존재한다.

$$a=qb+r \ \ \ \ 0\leq r<b$$

a를 b로 나누는 연산에서, q를 몫(quotient), r을 나머지(reminder)라 부른다.

pf)

* 존재성

아래 집합이 공집합이 아님을 보이자.

$$S=\{a-xb | x는 정수;a-xb\geq0\}$$

$b\geq 1$이므로 $|a|b\geq |a|$이며

$$a-(-|a|)b=a+|a|b\geq a+|a|\geq 0$$

$x=-|a|$라 하면 $a-xb$는 $S$에 속한다.

정렬성의 원리를 이용하자.

집합 $S$는 가장 작은 정수 $r$을 포함하며, $S$의 정의에 의해 다음을 만족하는 정수 $q$가 존재한다.

$$r=a-qb \ \ \ \ 0\leq r$$

$r<b$임을 보이자. 만일 아니라면 $r\geq b$이고 다음 식

$$a-(q+1)b=(a-qb)-b=r-b\geq 0$$

을 만족하고, $a-(q+1)b$는 집합 $S$에 속한다.

하지만, $a-(q+1)b=r-b<r$이고 $r$이 $S$의 가장 작은 원소라는데서 모순이다.

 

* 유일성

$a$가 다음 두 가지의 형태로 표현될 수 있다고 가정하자.

$$a=qb+r = q'b+r', \ \ \ \ 0\leq r<b,0\leq r'<b$$

그러면 $r'-r = b(q-q')$이고, 다음과 같다.

$$|r'-r|=b|q-q'|$$

이를 통해 $|r'-r|<b$를 얻을 수 있고, $b|q-b'|<b$이며 다음을 나타낸다.

$$0\leq |q-q'|<1$$

$|q-q'|$이 음이 아닌 정수이므로, $|q-q'|=0$ 즉 $q=q'$이며 $r=r'$이다.

---

최대공약수

정수 $a, b$ 둘 중 하나가 적어도 0이 아닌 정수일 때, 최대공약수는 $gcd(a,b)$이며 다음 조건을 만족하는 정수 $d$이다.

(a) $d|a,d|b$

(b) $c|a$이고 $c|b$이면 $c\leq d$

---

정수 $a,b$ 둘 중 하나가 적어도 0이 아닐 때 다음을 만족하는 정수 $x, y$가 존재한다.

$$gcd(a,b)=ax+by$$

pf)

$$S=\{au+bv|au+bv>0;u,v는 정수\}$$

$a\neq 0$이면 $|a|=au+b\cdot 0$은 $u$를 1 또는 -1로 택할 때 $S$에 속하므로 $S$는 공집합이 아니다.

정렬성의 원리에 의해 $S$는 가장 작은 원소 $d$를 가진다.

$S$의 정의에 의해 $d=ax+by$를 만족하는 $x,y$가 존재한다.

 

$d=gcd(a,b)$임을 보이자.

나눗셈 정리를 이용하면 $a=qd+r, \ \ \ 0\leq r<d$가 존재한다. $r$은 다음과 같이 바뀐다.

$$r=a-qd=q-q(ax+by)=a(1-qx)+b(-qy)$$

$r>0$이면 $r$은 $S$의 원소이고 $d$가 $S$의 가장 작은 원소라는데 모순이다. 즉, $r=0$이며 $a=qd$이다.

$d|a$이고 $d|b$이므로 $d$는 $a,b$의 공약수이다.

 

$c$가 $a,b$의 임의의 공약수라 하면, $c|(ax+by)$이고 $c|d$이다.

$c=|c|\leq |d|=d$이므로 $d$는 가장 큰 공약수이다.

즉, $d=gcd(a,b)$이다.

즉, 다음과 같이 표기될 수 있다.

$$1=\frac{a}{d}x+\frac{b}{d}y$$

---

정수 $a,b$ 둘 중 하나가 적어도 0이 아닐 때 집합

$$T=\{ax+by|x,y는 정수\}$$

은 정확히 정수 $d=gcd(a,b)$의 배수들로 이루어진 집합이다.

---

$a|c$, $b|c$ 그리고 $gcd(a,b)=1$이면 $ab|c$이다.

---

유클리드 보조정리.

$a|bc$이고 $gcd(a,b)=1$이면 $a|c$이다.

---

유클리드 알고리즘

유클리드 호제법이라고도 부른다.

 

유클리드 알고리즘에서 다음과 같이 식을 얻는다.

$$a=q_1 b+r_1 \ \ \ \ 0\leq r_1 <b$$

나머지가 0이면 $b|a$이므로 $gcd(a,b)=b$이다.

그렇지 않다면 아래와 같은 동작을 반복한다.

$$b=q_2 r_1 + r_2 \ \ \ \ 0\leq r_2 <r_1$$

$$\vdots$$

$$r_{n-1} = q_{n+1}r_n +0$$

에 대해 $r_n$이 $gcd(a,b)$와 같다.

---

$a=qb+r$이면 $gcd(a,b)=gcd(b,r)$이다.

---

$k>0$이면 $gcd(ka,kb) = k\cdot gcd(a,b)$

0이 아닌 정수 $k$에 대해 $gcd(ka,kb) = |k|\cdot gcd(a,b)$

---

양의 정수 $a, b$에 대해

$gcd(a,b)lcm(a,b)=ab$

 

 

$lcm(a,b)=ab$이면 $gcd(a,b)=1$이고 그 역도 성립한다.

---

디오판투스 방정식

특수해를 통해 일반해를 찾는 방법이다.

선형 디오판투스 방정식 $ax+by=c$에 대해 알아보자.

 

해를 갖는 조건은 $d=gcd(a,b)$일 때, $d|c$임과 동치이다.

$x_0 , y_0$가 특수해일 때, 다른 모든 해들은 $t$가 임의의 정수일 때 다음을 만족한다.

$$ x= x_{0} + \frac{b}{d} t$$

$$ y=y_{0} - \frac{a}{d} t$$

pf)

$x_0 , y_0$이 특수해이고 $x', y'$이 또 다른 특수해라 가정하자.

아래 두 식은 동치이다.

$$ax_0 + b y_0 = c= ax'+by'$$

$$a(x'-x_0 ) =  b(y_0 - y')$$

$a=dr$, $b=ds$인 서로소 $r, s$가 존재한다.

$$r(x'-x_0) = s(y_0-y')$$

$gcd(r,s)=1$이고 $r|s(y_0 - y')$이다. 유클리드 보조정리를 이용하면 $r|(y_0 - y')$이며 임의의 $t$에 대해 $y_0 -y' =rt$이고 $x'-x_0 = st$이다.

이를 통해 다음 식을 유도할 수 있다.

$$x'=x_0 +st=x_0 +\frac{b}{d} t$$

$$y'=y_0 - rt=y_0 -\frac{a}{d} t$$

---

'<Elementary Number Theory>, David M. Burton저'를 기반하여 개인 공부 목적으로 작성되었습니다.

오타 및 오류가 있을 수 있으며, 문제가 될 시 삭제될 수 있습니다.