정수론, 제11장
오일러 𝛷 함수와
중국인의 나머지 정리
이상준 교수
(덕성여대 수학과) 2015년 2학기
교재 : 친절한 수론 길라잡이 (4판)
조셉 실버만 지음, 김병찬,김지영,이종규,박부성 옮김
𝛷(m)을 어떻게 계산할까?
❖ 정의: 𝛷(m) = # { a : 1 ≤ a ≤ m, gcd(a,m)=1 }
❖ 성질1: 만약 p가 소수이면, 𝛷(p) = p-1이다.
❖ 증명: 1, …, p-1 모두 p와 서로소이다.
❖ 성질2: 만약 p와 q가 서로 다른 소수이면, 𝛷(pq) = (p-1)(q-1)이다.
❖ 증명: 1과 pq 사이의 pq와 서로소가 아닌 모든 정수는 p, 2p, 3p, …, qp ← q 개
q, 2q, 3q, …, pq ← p 개
그러므로, 𝛷(pq) = pq-(q+p-1) = (p-1)(q-1)
❖ 성질 1-2를 모든 자연수로 일반화하자.
공통요소
𝛷 함수 공식
❖ 정리(𝛷 함수 공식): n=p1k1
p
2k2…p
rkr(p
i: 서로다른 소수)이면 𝛷(n) = n(1-1/p
1)(1-1/p
2)…(1-1/p
r) 이다.
❖ 증명: 다음페이지!
❖ 예제:
❖
𝛷(1512) = 𝛷(2
2・3
2・7) = 1512(1-1/2)(1-1/3)(1-1/7) = 1512・1/2・2/3・6/7 = 432
❖
𝛷(2
5・3・11
2) =
𝛷 함수 공식 증명
❖ 정리(𝛷 함수 공식): n=p1k1p2k2…prkr (pi: 서로다른 소수)이면 𝛷(n) = n(1-1/p1)(1-1/p2)…(1-1/pr) 이다.
❖ 보조정리 (a) 만일 p가 소수이고 k≥1 이면 𝛷(pk) = pk(1-1/p).
(b) 만일 gcd(m,n)=1 이면 𝛷(mn) = 𝛷(m)𝛷(n).
❖ 𝛷 함수 공식 증명(보조정리 가정):
𝛷(n) = 𝛷(p1k1…prkr) = 𝛷(p1k1)…𝛷(prkr)
= p1k1(1-1/p1)p2k2(1-1/p2)…prkr(1-1/pr) = n(1-1/p1)(1-1/p2)…(1-1/pr).
보조정리 (a) (b)의 증명
❖ 보조정리(a): 만일 p가 소수이고 k≥1 이면 𝛷(pk) = pk - pk-1.
❖ 증명:
❖ {1,2,…,pk}안의 pk와 서로소가 아닌 모든 정수는 p,2p,3p,…,pk-1・p
❖ 그러므로 𝛷(pk) = pk - pk-1 = pk(1-1/p). 끝!
❖ 보조정리(b): 만일 gcd(m,n)=1 이면, 𝛷(mn) = 𝛷(m)𝛷(n) 이다.
❖ 증명:
❖ 두 집합 A와 B를 정의하자.
A := { a : 1 ≤ a ≤ mn, gcd(a,mn)=1 }
B := { (b,c) : 1 ≤ b ≤ m, gcd(b,m)=1, 1 ≤ c ≤ n, gcd(c,n)=1 }
❖ |A|=𝛷(mn), |B|=𝛷(m)𝛷(n)
❖ 𝛷(mn) = 𝛷(m)𝛷(n)를 보이기 위해
A,B 사이에 일대일대응(1-1 correspondence)을 찾으면 된다.
❖ 함수 f : A → B 를 정의하자:
❖ f가 일대일대응임을 보이기 위해 다음 3가지를 보이면 된다:
❖ ① f는 잘 정의되어있다.
❖ ② f는 일대일함수(1-1)이다.
❖ ③ f는 onto함수이다.
출처: 조셉 실버만, 친절한 수론 길라잡이
← 중국인의 나머지 정리를 이용!
← 중국인의 나머지 정리를 이용!
❖ ①의 증명:
❖ ②와 ③의 증명: (중국인의 나머지 정리 소개 후)
중국인의 나머지 정리
❖ 중국인의 나머지 정리: 두 정수 m,n이 gcd(m,n)=1을 만족한다고 하자.
임의의 정수 b,c에 대해 연립 합동방정식 x ≡ b (mod m), x ≡ c (mod n) 은 (mod mn)으로 정확히 하나의 해를 가진다.
❖ 역사기록: 중국인의 나머지 정리에 대한 최초의 기록은 3세기 후반 혹은 4세기 초반 즈음 에 기록된 중국의 수학책에 있다: <손자산경> AD 300년경, 3권, 26번 문제.
❖ “우리는 몇 개의 물건을 가지고 있는데, 정확히 몇 개인지 모른다. 만일 이들을 세 개씩 묶 어서 세면 두 개가 남고, 다섯 개씩 묶어 세면 세 개가 남고, 일곱 개씩 묶어 세면 두 개가 남는다. 과연 몇 개 있을까?”
❖ 중국인의 나머지 정리 증명: x ≡ b (mod m) ---(1) x ≡ c (mod n) ---(2)
❖ (1)로 부터 x=b+my 를 얻는다.
❖ (2)에 대입하면 b+my ≡ c (mod n) ==> my ≡ c-b (mod n)
❖ gcd(m,n)=1 이기 때문에 0≤y≤n-1인 유일한 해 y1 이 존재한다.
❖ x=b+my 을 만족하며 0≤x≤mn-1인 유일한 해 x1=b+my1 가 존재한다.
↑
0≤y1≤n-1, 0≤b≤m-1
❖ ②와 ③의 증명:
