[정수론] 정수나눗셈(division algorithm), divisibility (나누어 떨어짐), 약수와 배수, 소수(prime number), 서로소(relative prime)
Math/Numbers/Combinatorics2008. 4. 15. 15:08 |
이 글은, 앞으로 정수론 관련 글을 쓰기 위한 용어 및 기호의 도입 페이지이다.
정수론의 불문율 : 정수론에서 등장하는 문자들은 특별한 언급이 없을땐 일단 정수라고 가정한다.
1. 정수의 나눗셈
임의의 두 정수 a , b (≠0 ) 에 대하여 , a = b q + r ( 0 ≤ r < |b| ) 으로 표현할수 있는 유일한 q 와 r 이 존재한다.
이때, b 를 제수 ( 읽기는 젯수라고 읽음, divider ) , a 를 피제수 ( 피젯수라고 읽음, dividend ) ,
q 를 몫 ( quotient ) , r 을 나머지 ( remainder ) 라고 한다.
주의할 것은, 우리의 수학에서는 0 으로 나누는 것을 엄격히 금지하기 때문에, 나누는수, 즉 제수는 항상 0 이 아니어야 한다.
( 즉, 위식에서 b ≠ 0 ) 앞으로는 언급이 없더라도, 0 으로 나누는 것은 자동 배제시키기로 한다.
예) 17 을 -3 로 나누면, 17 = (-3) * (-5) + 2 이므로, 몫은 -5 이고, 나머지는 2 가 된다.
2. 나누어떨어짐 ( divisibility )
정수의 나눗셈에서, 나머지(remainder) 가 0 인 경우, "나누어 떨어진다" 고 말한다.
나누어떨어짐 (디비저빌러리 -_- ) 에 대해, 다음의 기호를 도입하자.
a | b " a divides b " " a 는 b 를 나눈다. " ⇔(def ) b = a k for some integer k
다시한번 0 으로 나누는 것에 대한 주의를 환기시키자면, 이 경우 a 가 b 를 나누었으므로,
별 말이 없더라도, a 는 0 이 아니라는 말을 포함한다.
디비저빌러리는 다음의 성질이 있다.
" a | b ∧ b | c ⇒ a | c " 증명: b = a k , c = b t = a ( kt )
이런걸, transitive 하다고 한다. 즉, " 디비저빌러리 릴레이션은 트랜지티브 하다. "
3. 약수(divisor) 와 배수(multiple)
a | b 일때, a 를 b 의 약수, b 를 a 의 배수 라고 한다.
예) 3 | 0 이므로 3 은 0 의 약수, 0 은 3 의 배수 ( 왜냐면, 0 = 3 * 0 , 몫은 0 , 나머지는 0 )
0 | 3 은 생각할 수 없다 -_-
4. 공약수 ( common divisor ) 와 공배수 ( common multiple )
d | a1 ∧ d | a2 ∧ ... ∧ d | an 일 때, d 를 a1 , a2 , ... , an 의 공약수라고 부른다.
a1
| m ∧ a2 | m ∧ ... ∧ an | m 일 때, m 을 a1 , a2 , ... , an 의 공배수라고 부른다. 양의 공약수와 음의 공약수가 있는데, 음의 공약수가 단지 양의 공약수에 - 만 붙인거라서, 별 관심을 불러일으키지 않는 관계로,
보통 공약수라고 하면, ( 혼동의 여지가 없는 경우 ) 양의 공약수를 의미한다.
공배수도 마찬가지다.
divisibility 가 transitive 하므로, 공약수, 공배수의 정의로 부터, 공약수는 공배수를 나눈다.
즉, d | a , ... 이고, a | m .... 이므로, d | a | m 이 되어, d | m 이 당연하게 성립한다.
5. 최대공약수 ( the greatest common divisor ) 와 최소공배수 (the least common multiple )
공약수 중에서 가장 큰 것을 최대공약수라고 하고, (양의) 공배수 중에 가장 작은 것을 최소공배수라고 한다.
약칭으로, gcd 와 lcm 이라는 표현을 많이 쓴다. 간혹, 답안쓰다가 실수로 lcd 라고 쓰는 사람들이 있다 ㅋㅋㅋ 나도 ㅋㅋㅋ
표기법으로 다음의 것이 자주 사용된다.
gcd (
a1 , a2 , ... , an
) :
a1 , a2 , ... , an
의 최대공약수
lcm (
a1 , a2 , ... , an
) :
a1 , a2 , ... , an
의 최소공배수
혼동의 여지가 없는 한, 우리는 더 간단히 , 종 종 g 와 ℓ 혹은 ( ) 와 [ ] 따위로 표현하기도 한다.
예. ( 6 , 8 , 12 ) = 6 , 8 , 12 의 최대공약수
[ 6, 8, 12 ] = 6, 8 , 12 의 최소공배수
어찌되었건 최대공약수도 공약수이고, 최소공배수도 공배수이므로, 공약수는 공배수를 나누니까, 따라서, 최대공약수도 최소공배수를 나눈다.
6. 소수 (prime number)
양의 약수가 2개 인 자연수를 소수 라고 부른다.
( 소수라고 쓰고, 솟수 라고 읽는다. )
7. 서로소 (relative prime)
a1 , a2 , ... , an
에 대해, 임의의 서로다른 두 수 ai , aj 를 골라도, GCD(ai, aj) = 1 일 때,
a1 , a2 , ... , an
를 서로 소 라고 한다.
( 즉, 1 말고는 공약수가 없는 경우이다. )