정수 용어 정리

1. 약수와 배수

▶ 나눗셈 알고리즘(The Division Algorithm) : 두 정수 $a, b(\neq 0)$에 대해서 $a = bq+r$을 만족하는 정수 $q, r$이 유일하게 존재한다. (단, $0\leq r < b $ 이다.)

▶ 약수와 배수 : $a=bq+r$ (단, $abq \neq 0 , 0 \leq r < b$)에서 $r=0$이면 $a=bq$이다. 이때 $a$를 $b$의 배수, $b$를 $a$의 약수라고 한다. 기호로 $b | a$라 한다.

▶ $a,b,c$가 $0$이 아닌 임의의 세 정수 일 때

   1) $a|b$이고 $a|c$이면 $a|(b+c)$

   2) $a|b$ 또는 $a|c$이면 $a|bc$

   3) $a|b$ 이고 $b|c$이면 $a|c$

 

2. 최대공약수

두 정수 $ a,b$에 대해서 $d|a$, $d|b$인 정수 $d$를 $a$와 $b$의 공약수(common divisor)라 한다. 또한 두 정수 $a,b$에 대해서 다음 세 조건을 만족시키는 정수 $d$를 $a$와 $b$의 최대공약수(greatest common divisor : GCD) 이다.

1) $d \geq 0$

2) $d|a, d|b$

3) $e|a, e|b$이면 $e|d$

 

3. 최소공배수

두 정수 $a,b$에 대해서 $a|m$, $b|m$ 인 정수 $m$을 $a$와 $b$의 공배수(common multiple)이라 한다. 또한 두 정수 $a,b$에 대해서 다음 세 조건을 만족시키는 정수 $m$을 $a$와 $b$의 최소공배수(least common multiple)라 한다.

1) $m \geq 0$

2) $a|m$, $b|m$

3) $a|c$, $b|c$이면 $m|c$

 

4. 소수와 합성수

▶ 소수 : 1보다 큰 자연수 중 1과 자기 자신 이외에 양의 약수를 가지지 않는 수이다. 약수가 2개인 자연수이다.

▶ 합성수 : 1보다 큰 자연수 중 소수가 아닌 수이다. 약수의 개수가 3개 이상인 자연수이다.

▶ 소인수분해 : 합성수는 반드시 소수의 곱으로 나타낼 수 있다. 결과는 오직 하나밖에 없으며 합성수를 소수의 곱으로 나타내는 것을 소인수분해라 한다.

▶ 소인수 분해를 이용해 약수를 구하는 방법

1) 어떤 자연수 $A$가 $A=a^m \times b^n $ ($a,b$는 서로 다른 소수, $m,n$은 자연수)로 소인수 분해될 때, $A$의 약수는 $a^m$의 약수 ($1, a, a^2 , \codts , a^m$)과 ($1, b, b^2 , \cdots , b^n$)를 각각 곱한 것과 같다.

2) $A=a^m \times b^n $은 $(m+1) \times (n+1)$개의 약수를 갖는다.