정수론, 제28장
법 p에 대한 거듭제곱과 원시근
이상준 교수(덕성여대 수학과)2015년 2학기
교재 : 친절한 수론 길라잡이 (4판)
조셉 실버만 지음, 김병찬,김지영,이종규,박부성 옮김
강의 슬라이드: 이상준, 오연주(15학번)
법 p에 대한 a의 위수
❖ 복습(페르마의 소정리): 소수 p와 gcd(a,p)=1인 정수 a에 대해서 ap-1 ≡ 1 (mod p).
❖ 정의: 법 p에 대한 a의 위수 (order of a modulo p)를
ep(a) = (am ≡ 1 (mod p)를 만족하는 가장 작은 자연수 m)로 정의한다.
❖ 주의: p와 서로소인 a에 대해서만 위수를 정의한다.
(그렇지 않으면 am ≡ 1 (mod p)인 m이 없을 수 있으므로)
❖ 자료: a의 거듭제곱 중에서 법 p에 대해 1과 합동이 되는 가장 작은 거듭제곱을 소수p = 5, 7, 11 에 대해, 그리고 1과 p-1 사이의 a에 대해서 나열해 보았다.
출처: 조셉 실버만, 친절한 수론 길라잡이
관찰
❖ (1) 모든 지수는 p-1 의 약수이다.
❖ (2) 모든 소수 p에 대하여 지수가 p-1 인 a가 항상 존재한다.
위수의 나눔 성질
❖ 정리 (위수의 나눔 성질(Order Divisibility Property)):
❖ 정수 a가 소수 p와 서로소이고, an ≡ 1 (mod p) 이라고 하자.
❖ 그러면 ep(a) | n 이다.
❖ 증명: (나눗셈 정리를 이용) n = ep(a)q + r ( 0 ≤ r < ep(a) ) 라 하자.
❖ 1 ≡ an ≡ aep(a)q+r ≡ (aep(a))q・ar ≡ 1q・ar ≡ ar (mod p)
❖ r < ep(a)이고, ep(a)는 ae ≡ 1 (mod p)가 되는 지수 중에서 가장 작은 지수이므로 ep(a)의 최소성에 의해 r = 0 이다.
❖ 따름정리: 정수 a가 소수 p와 서로소라 하면 ep(a) | p-1 이다.
❖ 증명: 페르마의 소정리에 의하여 ap-1 ≡ 1 (mod p) 이므로 위 정리에 의하여 성립.
❖ 질문: ep(a) = p-1 을 가지는 수 a가 있는가? 그런 수는 무엇인가?
❖ 사실: 만약 a가 그러한 수라면 a, a2, a3, ..., ap-3, ap-2, ap-1 (mod p)는 모두 다르다.
❖ 왜 그럴까?
❖ { a, a2, a3, …, ap-3, ap-2, ap-1 } = { 1, 2, …, p-2, p-1} (mod p)
❖ 정의: ep(a) = p-1 인 수 a를
법 p에대한 원시근(primitive root modulo p)이라고 한다.
❖ 예제: 2와 3은 법 5에 대한 원시근
❖ 3과 5는 법 7에 대한 원시근
❖ 2,6,7,8이 법 11에 대한 원시근
원시근에 대한 질문들
❖ 상황1: 법 p를 고정하자.
❖ 원시근 a는 몇개인가?
❖ 모든 원시근을 어떻게 찾을 수 있는가?
❖ 상황2: 자연수 a를 고정하자.
❖ a를 원시근으로 갖는 법 p는 얼마나 많은가?
❖ 그런 법 p는 무엇인가?
상황1: 법 p를 고정하자.
원시근 정리
❖ 상황1: 법을 고정하자.
❖ 예시: 법 11에 대해서 𝛷(10)=4 개의 원시근 2,6,7,8이 존재한다.
❖ 법 37에 대해서는 𝛷(36)=12 개의 원시근이 존재한다.
❖ 법 9907에 대해서는 𝛷(9906)=3024 개의 원시근이 존재한다.
❖ 원시근 정리: 모든 소수 p는 원시근을 가진다.
정확하게는 법 p에 대한 원시근은 𝛷(p-1) 개 존재한다.
❖ 장점: 원시근을 조사하지 않고서도 원시근의 갯수를 알 수 있다.
❖ 단점: 원시근을 실제로 찾는 방법은 알려주지 않는다.
원시근 찾기
❖ 주목: 법 p에 대한 원시근을 하나 찾을 수 있다면, 다른 모든 원시근을 찾는 것은 그리 어렵지 않다.
❖ 방법: a가 법 p에 대한 원시근이라 하자.
❖ 복습: { a, a2, a3, …, ap-3, ap-2, ap-1 } = { 1, 2, …, p-2, p-1} (mod p)
❖ m이 p-1과 서로소이면 m에 p-1배를 해야 처음으로 p-1의 배수가 된다.
❖ 즉, am은 p-1 승을 해야 처음으로 1이 된다.
❖ 그러므로 am 도 원시근!
❖ 질문: gcd(m, p-1)=1인 m이 몇개인가?
❖ 𝛷(p-1) 개.
❖ 원시근 정리에서 원시근의 갯수는 𝛷(p-1)라고 했으므로
원시근 정리의 증명
❖ 각각의 a에 대해서 ep(a) | p-1 이다.
❖ 따라서 p-1 의 약수 d에 대해서만 위수 ep(a)=d인 a가 존재한다.
❖ f(d) = (1≤a<p 이고 ep(a)=d 를 만족하는 수 a의 개수)
❖ 관찰: f(p-1)은 법 p에 대한 원시근의 개수이다.
❖ 목표: f(p-1) = 𝛷(p-1) 임을 보이면 된다.
❖ 정리: n | p-1 이면 f(n) = 𝛷(n) 이다.
❖ 정리의 증명: 다음페이지!
❖ 보조정리: n | p-1 이고 d1, d2, ..., dr 가 n의 모든 약수라면
f(d1) + f(d2) + … + f(dr) = n 이다.
❖ 관찰: 27장에서 증명한 오일러 𝛷 함수에 대한 공식과 똑같은 것이다.
❖ 보조정리의 증명:
❖ ① 주장: xn - 1 ≡ 0 (mod p) 는 0 ≤ x < p 범위에서 정확히 n개의 해를 가진다.
❖ 주장의 증명: 나중에.
❖ ② 이제 xn - 1 ≡ 0 (mod p) 의 해의 개수를 다른 방법으로 세어보자.
❖ d1, d2, ..., dr 가 n의 모든 약수라면 xn - 1 ≡ 0 (mod p) 의 해의 개수는
f(d1) + f(d2) + … + f(dr) 이다. (이유는?)
❖ ①+②: f(d1) + f(d2) + … + f(dr) = n
❖ 정리: n | p-1 이면 f(n) = 𝛷(n) 이다.
❖ 보조정리로 부터 정리의 증명: (수학적 귀납법 이용)
❖ 우선 n = 1 일 때 f(1) = 1, 𝛷(1) = 1.
❖ 수학적 귀납법의 가정으로부터 d < n 이고 d | p-1 인 모든 d에 대하여 f(d) = 𝛷(d) 가 성립한다고 가정하자.
❖ 보조정리로부터 (d1 = n)
f(n) + f(d2) + f(d3)+ … + f(dr) = n = 𝛷(n) + 𝛷(d2) + 𝛷(d3) + … + 𝛷(dr)
❖ f(di) = 𝛷(di) 가 모든 i=2,3,...,r 에 대해서 성립하므로
❖ f(n) = 𝛷(n) 이다.
❖ 남은 것:
❖ 주장: n | p-1 이면 xn - 1 ≡ 0 (mod p) 는 0 ≤ x < p 범위에서 정확히 n개의 해를 가진다.
❖ 증명:
❖ 이유: 페르마의 소정리, 법 p에 대한 다항식의 근의 정리
출처: 조셉 실버만, 친절한 수론 길라잡이
상황2: a 를 고정하자.
❖ 질문: 고정된 수 a가 어떤 소수 p에 대해서 원시근이 되는가?
❖ 자료: ep(2) 대신 ep 로 표기
e3 = 2 e5 = 4 e7 = 3 e11 = 10 e13 = 12 e17 = 8 e19 = 18 e23 = 11 e29 = 28 e31 = 5 e37 = 36 e41 = 20 e43 = 14 e47 = 23 e53 = 52 e59 = 58 e61 = 60 e67 = 66 e71 = 35 e73 = 9 e79 = 39 e83 = 82 e89 = 11 e97 = 48
❖ 2가 법 p=3,5,11,13,19,29,37,53,59,61,67,83 에 대해서 원시근
추측
❖ 아틴의 추측: 2가 법 p에 대해서 원시근이 되는 무한히 많은 소수 p가 존재한다.
❖ 일반화된 아틴의 추측: a는 -1 도 아니고 완전제곱수도 아닌 정수라고 하자.
그러면 법 p에 대해서 a가 원시근이 되는 소수 p가 무한히 많이 존재한다.
❖ 위의 추측들은 아직 증명되지 않았다!
