정수론, 제7장
인수분해와 산술의 기본정리
이상준 교수(덕성여대 수학과)2015년 2학기
교재 : 친절한 수론 길라잡이 (4판)
조셉 실버만 지음, 김병찬,김지영,이종규,박부성 옮김
강의 슬라이드: 이상준, 오연주(15학번)
소수와 합성수
❖ 정의:
소수(prime number): (양의) 약수가 1과 p 뿐인 2 이상인 정수 p 합성수(composite number): 소수가 아닌 2 이상인 정수 m
❖ 예: 소수 2,3,5,7,11,13,17,19,23,29,31,...
합성수 4,6,8,9,10,12,14,15,16,18,20,...
❖ 질문: 우리는 왜 소수를 연구할까?
보조정리
❖ 보조정리: 소수 p가 정수들의 곱 ab를 나눈다고 가정하자.
그러면 p는 a를 나누거나 b를 나눈다. (또는 a와 b를 모두 나눈다.)
❖ 증명: 만일 p|a 라면, 증명이 끝난다. 그러므로 p
∤
a 라고 가정하자.❖ 그러면 gcd(p,a) = 1 이므로 px+ay=1 의 정수해 x와 y를 찾을 수 있다.……… (1)
❖ 다른 한편으로는 p|ab 이므로, pk=ab를 만족하는 정수 k가 있다. ……… (2)
❖ (1)의 양변에 b를 곱하면 bpx+bay = b 이다.
❖ (2)를 대입하면 p(bx+ky) = b 이다. 그러므로 p∣b 이다.
일반화: 소수의 가약성
❖ 소수의 가약성 정리: 소수 p가 정수들의 곱 a1a2…ar 를 나눈다고 하자.
그러면 p는 인수 a1, a2, …, ar 중 최소한 하나를 나눈다.
❖ 증명: 만일 p∣a1 이면, 증명이 끝난다.
만일 p∤a1 이면, 앞 보조정리에 의해 p∣a2a3…ar 이다.
❖ 만일 p∣a2 이면, 증명이 끝난다.
만일 p∤a2 이면, 앞 보조정리에 의해 p∣a3a4…ar 이다.
⋮
❖ p∣arar-1이다. 만일 p∣ar-1 이면, 증명이 끝난다.
만일 p∤ar-1 이면, 앞 보조정리에 의해 p∣ar 이다. 증명 끝!
산술의 기본정리
❖ 산술의 기본 정리 (Fundamental theorem of arithmetic):
2보다 크거나 같은 모든 정수 n은 소수들의 곱 n = p1p2…pr로 표현되며, 그 표현은 유일하다.
❖ 주의:
❖ ① 각각의 pi 들이 서로 다른 소수일 필요는 없다.
예: 300 = 2・2・3・5・5
❖ ② 유일성 측면에서 소수들을 곱하는 순서는 무시한다.
예: 12 = 2・2・3 = 2・3・2 = 3・2・2
❖ 증명: 다음 두가지를 증명하면 된다.
주장1: 정수 n(≥2)은 소수들의 곱으로 표현될 수 있다.
주장2: 소수들을 곱하는 순서를 무시하면 그 방법은 유일하다.
❖ 주장1: 정수 n(≥2)은 소수들의 곱으로 표현될 수 있다.
❖ 증명: (수학적 귀납법)
❖ (1) n=2이면, n은 소수이다.
❖ (2) 주장1이 2≤n≤k에서 성립한다고 가정하자. n=k+1이라 하자.
❖ k+1이 소수이면, 주장1은 성립한다.
그렇지않으면, k+1=n1・n2 (2≤n1,n2≤k)이다.
❖ 가정에 의하여, n1과 n2는 소수의 곱으로 쓰여질 수 있다.
즉 n1 = p1p2…pr, n2 = q1q2…qs (pi, qj는 다를 필요가 없는 소수)이다.
❖ n = n1n2 = p1p2…prq1q2…qs 이므로 주장1은 성립한다.
❖ 주장2: 소수들을 곱하는 순서를 무시하면 그 방법은 유일하다.
❖ 증명: (귀류법)
❖ n = p1p2…pr = q1q2…qs (pi와 qi는 다를 필요가 없는 소수)이고
p1p2…pr 은 q1q2…qs 를 순서만 바꾼 것이 아니라고 가정하자.
❖ p1p2…pr = q1q2…qs로 부터 공통 소인수들을 모두 소거하여 p1’p2’…pu’= q1’q2’…qv’ 를 얻었다고 하자.
(순서만 바꾼 것이 아니므로 좌우변은 1이 아니다.)
❖ p1’|q1’q2’…qv’이므로 소수의 가약성에 의해 p1’|qi’ 인 i가 존재한다.
❖ p1’=qi’ 이므로 이미 소거가 되었어야 하므로 모순!
❖ 질문: 주어진 정수 n을 소수의 곱으로 어떻게 쓸까?
❖ 경우1 (n이 작을 때): 직접 소인수분해할 수 있다.
❖ 예:
❖ 경우2 (n이 클 때): 약수를 찾을 때까지 n 을 소수 2,3,4,5,11,... 로 나누어 본다.
❖ 예: n = 9105293 = 37・246089 246089 = 43・5723
5723 = 59・97 (97이 소수이므로 끝!) 그러므로, 9105293 = 37・43・59・97.
작은 소인수가 있다.
❖ 정리: 만일 n 이 소수가 아니라면, p ≤ √n 인 n의 소인수 p가 있다.
❖ 증명: p가 n을 나누는 가장 작은 소수라 가정하면, n = pm ≥ p*p = p2 이다.
그러므로 p ≤ √n 이다.
❖ 주의: 작은 소인수를 찾는 것은 오랜시간이 걸릴 수도 있다.
예를 들어 n = 10128 라 하자. √n = (10128)1/2 = 1064. 만일 우리가 초당 109=1,000,000,000번의
나눗셈을 할 수 있을지라도 약 3・1048년의 시간이 걸린다.
추가 질문
❖ 질문1: 주어진 정수가 소수인지 합성수인지 어떻게 판별할 수 있을까?
❖ 답: 어떤 정수가 소수인지를 높은 확률로 판별해주는 알고리즘이 있다.
알고리즘의 결과: 합성수 or 99.99999%로 소수.
❖ 질문2: 만일 n이 합성수라면, 어떻게 소인수분해를 할 수 있을까?
❖ 답: 어려운 문제이다. 그래서 이것은 암호(RSA)에 이용된다.
