이차상호법칙

(1)

정수론, 제22장

이차상호법칙

^{이상준 교수}⁽^{덕성여대 수학과)}

2015년 2학기

교재 : 친절한 수론 길라잡이 (4판)

조셉 실버만 지음, 김병찬,김지영,이종규,박부성 옮김

강의 슬라이드: 이상준, 오연주(15학번)

(2)

각 장의 목표

❖ 각 장의 목표: p가 홀수인 소수이고, a ≢ 0 (mod p) 라 하자.

❖ 20장: 주어진 p에 대해, 는 무엇일까?

❖ 21장: a = -1 또는 2 일 때, 는 무엇일까?

❖ 22장: 는 무엇일까?

(3)

❖ 22장 목표: 는 무엇일까?

❖ 예시:  

❖ 일반화: a=q1q2…qr (qi는 서로 다를 필요없는 소수)라면 

❖ 사실: 만약 소수 a에 대해서 를 계산할 수 있다면   모든 정수 a에 대해서 를 계산할 수 있다.

(4)

❖ 자료:  

❖ 질문: 어떤 규칙성을 발견할 수 있나?

출처: 조셉 실버만, 친절한 수론 길라잡이

(5)

관찰

❖ p=5인 행: 

❖ q=5인 열: 

❖ 똑같다!

❖ 추측: 모든 소수 p에 대해서 

(6)

❖ 이 규칙의 유용성:

❖ 를 구하는 것은 어려운 문제이다. (p가 큰 경우)

❖ 그러나 는 소수 p를 5로 나눈 나머지에만 의존하기 때문에   계산이 매우 간단하다.  

❖ 을 구하기 위해 을 이용할 수 있다!

(7)

❖ 예시: 라 가정하자. 

이고, 같은방법으로

❖ 추측: 모든 소수 p와 q에 대해

❖ 추측은 사실이 아니다!

❖ 반례:

❖ 질문: 언제 가 성립할까?

(8)

❖ 자료:  

❖ 질문: 규칙성을 찾아라.

❖ 추측: 만약 p ≡ 1 (mod 4)이거나 q ≡ 1 (mod 4)이면, 이다.

❖ 추측: 만약 p ≡ 3 (mod 4)이고 q ≡ 3 (mod 4)이면, 이다.

(9)

이차상호법칙

❖ 이차상호법칙: 서로 다른 홀수인 소수 p와 q에 대하여 다음이 성립한다.

❖ ①

❖ ②

❖ ③

❖ 증명: ①과 ②는 21장에서 증명을 하였고, ③은 23장에서 증명할 것이다.

❖ 이차상호법칙은 어떠한 수가 이차잉여인지 아닌지   판별하는 유용한 도구이다.

(10)

❖ 예제1:

(11)

❖ 예제2:

(12)

❖ 예제3: ? (힌트: 397은 소수이다, 299=13×23) 

(13)

❖ 예제4: ? (힌트: 48611은 소수이다, 37603=31×1213)

(14)

계산상 문제점

❖ 질문: 홀수인 소수 p와 a ≢ 0 (mod p) 에 대하여 을 구하기 위해 필요한 것?

❖ 답: a의 소인수 분해! (어려운 문제이다.) 

❖ 질문: “a의 소인수 분해” 를 모르고 을 계산할 방법이 없는가?

❖ 답: 야코비(Jacobi) 가 고안한 방법이 있다.

(15)

야코비 기호 (Jacobi symbol)

❖ 르장드르 기호를 일반화하여 야코비 기호를 정의한다.

❖ 정의(야코비 기호): 모든 자연수 a,b에 대하여  

b = p1p2...pr (pi는 서로 다를 필요없는 소수)이라 하자. 

❖ 중요: 이 값은 a가 b의 이차잉여인지의 여부와 상관이 없다!

(16)

일반화된 이차상호법칙

❖ 일반화된 이차상호법칙: 모든 홀수 a와 b에 대하여 다음이 성립한다. 

❖ 증명: 23장 (수업에서는 생략)

(17)

추가성질

(18)

❖ 예제:  

❖ 연습문제: 출처: 조셉 실버만, 친절한 수론 길라잡이

(19)

❖ 예제1:

(20)

❖ 예제2:

(21)

❖ 예제3:  

(22)

❖ 예제4: