정수론, 제22장
이차상호법칙
이상준 교수(덕성여대 수학과)2015년 2학기
교재 : 친절한 수론 길라잡이 (4판)
조셉 실버만 지음, 김병찬,김지영,이종규,박부성 옮김
강의 슬라이드: 이상준, 오연주(15학번)
각 장의 목표
❖ 각 장의 목표: p가 홀수인 소수이고, a ≢ 0 (mod p) 라 하자.
❖ 20장: 주어진 p에 대해, 는 무엇일까?
❖ 21장: a = -1 또는 2 일 때, 는 무엇일까?
❖ 22장: 는 무엇일까?
❖ 22장 목표: 는 무엇일까?
❖ 예시:
❖ 일반화: a=q1q2…qr (qi는 서로 다를 필요없는 소수)라면
❖ 사실: 만약 소수 a에 대해서 를 계산할 수 있다면 모든 정수 a에 대해서 를 계산할 수 있다.
❖ 자료:
❖ 질문: 어떤 규칙성을 발견할 수 있나?
출처: 조셉 실버만, 친절한 수론 길라잡이
관찰
❖ p=5인 행:
❖ q=5인 열:
❖ 똑같다!
❖ 추측: 모든 소수 p에 대해서
출처: 조셉 실버만, 친절한 수론 길라잡이
❖ 이 규칙의 유용성:
❖ 를 구하는 것은 어려운 문제이다. (p가 큰 경우)
❖ 그러나 는 소수 p를 5로 나눈 나머지에만 의존하기 때문에 계산이 매우 간단하다.
❖ 을 구하기 위해 을 이용할 수 있다!
❖ 예시: 라 가정하자.
이고, 같은방법으로
❖ 추측: 모든 소수 p와 q에 대해
❖ 추측은 사실이 아니다!
❖ 반례:
❖ 질문: 언제 가 성립할까?
❖ 자료:
❖ 질문: 규칙성을 찾아라.
❖ 추측: 만약 p ≡ 1 (mod 4)이거나 q ≡ 1 (mod 4)이면, 이다.
❖ 추측: 만약 p ≡ 3 (mod 4)이고 q ≡ 3 (mod 4)이면, 이다.
출처: 조셉 실버만, 친절한 수론 길라잡이
이차상호법칙
❖ 이차상호법칙: 서로 다른 홀수인 소수 p와 q에 대하여 다음이 성립한다.
❖ ①
❖ ②
❖ ③
❖ 증명: ①과 ②는 21장에서 증명을 하였고, ③은 23장에서 증명할 것이다.
❖ 이차상호법칙은 어떠한 수가 이차잉여인지 아닌지 판별하는 유용한 도구이다.
❖ 예제1:
출처: 조셉 실버만, 친절한 수론 길라잡이
❖ 예제2:
출처: 조셉 실버만, 친절한 수론 길라잡이
❖ 예제3: ? (힌트: 397은 소수이다, 299=13×23)
❖ 예제4: ? (힌트: 48611은 소수이다, 37603=31×1213)
계산상 문제점
❖ 질문: 홀수인 소수 p와 a ≢ 0 (mod p) 에 대하여 을 구하기 위해 필요한 것?
❖ 답: a의 소인수 분해! (어려운 문제이다.)
❖ 질문: “a의 소인수 분해” 를 모르고 을 계산할 방법이 없는가?
❖ 답: 야코비(Jacobi) 가 고안한 방법이 있다.
야코비 기호 (Jacobi symbol)
❖ 르장드르 기호를 일반화하여 야코비 기호를 정의한다.
❖ 정의(야코비 기호): 모든 자연수 a,b에 대하여
b = p1p2...pr (pi는 서로 다를 필요없는 소수)이라 하자.
❖ 중요: 이 값은 a가 b의 이차잉여인지의 여부와 상관이 없다!
일반화된 이차상호법칙
❖ 일반화된 이차상호법칙: 모든 홀수 a와 b에 대하여 다음이 성립한다.
❖ 증명: 23장 (수업에서는 생략)
출처: 조셉 실버만, 친절한 수론 길라잡이
추가성질
❖ 예제:
❖ 연습문제: 출처: 조셉 실버만, 친절한 수론 길라잡이
❖ 예제1:
❖ 예제2:
❖ 예제3:
❖ 예제4: