이상준 ( 법 덕성여대 p 년 2 에 교수 학기 수학과 대해 )2015 제곱인 수

(1)

정수론, 제20장

법 p에 대해 제곱인 수

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

2015년 2학기

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

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

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

(2)

복습과 질문

❖ 복습: 8장에서 선형 합동식 ax ≡ c (mod m)을 푸는 방법에 대해 배웠다.

❖ 목표: 이차방정식 x² ≡ c (mod m)을 생각해보자.

❖ 질문:

❖ ① x² ≡ 3 (mod 7) 은 해가 존재하는가?

❖ ② x² ≡ -1 (mod 13) 은 해가 존재하는가?

❖ ③ x² ≡ 2 (mod p) 의 해가 존재하는 소수 p는 무엇인가?

(3)

❖ ①과 ②의 답:

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

(4)

❖ 질문: 흥미로운 패턴은 무엇일까?

❖ 몇가지 답:

❖ ① 제곱수로 나타난 0 이외의 수는 정확히 두 번 나타난다.

❖ 즉, c가 0이 아니면 x² ≡ c² (mod p) 은 두 개의 해를 가진다.

❖ 증명: x² ≡ c² (mod p) ⇒ x² - c² ≡ 0 (mod p) 

(x+c)(x-c) ≡ 0 (mod p) ⇒ x+c ≡ 0 (mod p) or x-c ≡ 0 (mod p)  ⇒ x ≡ ±c (mod p)

❖ ② b² ≡ (p-b)² (mod p)

❖ 증명: (p-b)² ≡ (-b)² ≡ b² (mod p)

(5)

❖ 정리하면, ①②로부터, 우리는 다음을 알 수 있다: 

❖ 주목: 법 p에 대해 (0이 아닌) 제곱수의 목록을 만들고자 한다면,   우리는 오직 절반의 수에 대해서만 계산하면 된다. 

(6)

❖ 목표: 법 p에 대해 제곱수와 제곱수가 아닌 수를 구분하는 패턴을 찾는 것

❖ 정의: p를 소수이고, c ≢ 0 (mod p) 라 하자.

❖ ① 만일 어떤 a 에 대하여 a² ≡ c (mod p)이면, 

c를 법 p에 대한 이차잉여(quadratic residue modulo p)라 부른다.

❖ ② 만일 모든 a에 대하여 a² ≢ c (mod p)이면, 

c를 법 p에 대한 이차비잉여(quadratic non-residue modulo p)라 부른다.

❖ 표기법:

❖ QR = 이차잉여

❖ NR = 이차비잉여

(7)

❖ 예시:

❖ ① 3과 12는 법 13에 대한 QR이다.

❖ ② 2와 5는 법 13에 대한 NR이다.

❖ ③ 법 7에 대한 QR인 수:

❖ ④ 법 7에 대한 NR인 수:

❖ ⑤ 법 13에 대한 QR인 수:

❖ ⑥ 법 13에 대한 NR인 수:

(8)

❖ 정리: p를 홀수인 소수라 가정하자.  

법 p에 대한 이차잉여의 개수는 (p-1)/2이고, 이차비잉여의 개수도 (p-1)/2이다.

❖ 증명: “이차잉여의 개수가 (p-1)/2”임을 보이기만 하면 된다.

(9)

곱의 법칙

❖ 성질: QR × QR = QR

❖ 증명: b12·b22 ≡ (b1b2)² (mod p)

❖ 관찰: 

❖ 추측: QR × NR = NR, NR × NR = QR

(10)

이차잉여 곱셈 법칙 (버전1)

❖ 정리 (이차잉여 곱셈법칙): p를 홀수인 소수라 하면 다음이 성립한다.

❖ ⅰ) 두 개의 이차잉여의 곱은 이차잉여이다.

❖ ⅱ) 이차잉여와 이차비잉여의 곱은 이차비잉여이다.

❖ ⅲ) 이차비잉여의 곱은 이차잉여이다.

❖ 기호: 이 세 가지 법칙을 기호로 표현하면 다음과 같다. 

QR × QR = QR, QR × NR = NR, NR × NR = QR

(11)

❖ 증명: (수업시간)

(12)

르장드르 기호(Legendre symbol)

❖ 관찰: QR × QR = QR, QR × NR = NR, NR × NR = QR 

⟷ 1 × 1 = 1 ⟷ 1 × (-1) = (-1) ⟷ (-1) × (-1) = 1

❖ 주목: QR ⟷ 1 NR ⟷ -1

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

a의 법 p에 대한 르장드르 기호(Legendre symbol)는 

❖ 예시:  

(13)

이차잉여 곱셈 법칙(버전2)

❖ 르장드르 기호를 사용하면, 

이차잉여 곱셈 법칙은 다음과 같은 간단한 공식으로 표현된다.

❖ 정리(이차잉여 곱셈법칙): p가 홀수인 소수이고 a,b ≢ 0 (mod p) 라 하면, 

가 성립한다.

❖ 예제: = ?

❖ 답:  

❖ 10² ≡ 3 (mod 97) 이기 때문에, 이다.