약수와 배수

Def. (나눗셈 알고리즘)

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

$$a=bq+r,~0\leq r<b$$

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

 

Def. (약수와 배수)

정수 $a,~b$에 대하여

(1) $a\neq 0$

(2) $b=ac$인 정수 $c$가 존재한다.

을 만족할 때, $b$는 $a$로 나누어진다고 표현하고 $a~|~b$로 쓴다.

**이때 $a$는 $b$의 약수 $b$는 $a$의 배수가 된다. 

**$a$와 $b$는 음수가 될 수도 있다 (정수)

 

Def. (최대공약수)

$a,~b$를 적어도 둘 중 하나는 0이 아닌 정수라 하자. $a,~b$의 최대공약수(greatest common divisor)는 $gcd(a,~b)$로 쓰고 다음을 만족하는 양의 정수 $d$이다.

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

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

 

Def. (서로소)

정수 $a,~b$에 대해 $gcd(a,~b)=1$인 경우 서로소(relatively prime)라 한다.

 

Thm1.

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

 

Thm2.

적어도 하나는 0이 아닌 주어진 정수 $a,~b$에 대해

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

를 만족하는 $x,~y$가 존재한다.

 

** 디오판투스 방정식 $ax+by=c$

선형 디오판투스 방정식 $ax+by=c$가 해를 가지는 것은 $d=gcd(a,~b)$일 때 $d~|~c$임과 동치이다.

특수해 $x_{0},~y_{0}$에 대하여 일반해는 다음과 같다.

$$x=x_{0}+\left ( \frac{b}{d} \right )t,~y=y_{0}-\left ( \frac{a}{d} \right )t~~(t\in \mathbb{Z})$$