a = −1인 경우

정수론, 제21장

-1은 어떤 법 p에 대해 제곱수일까?

2는?

이상준 교수

(덕성여대 수학과)

2015년 2학기

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

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

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

질문

❖ 질문: x² ≡ a (mod p) 를 만족하는 해 x가 존재할까?

❖ 20장: p를 고정하고 a를 변수로 두었다.

❖ 21장: a를 (-1 또는 2로) 고정하고 p를 변수로 둔다.

❖ 궁극적 목표: 를 계산하기 위한 기초! (22장)

a = −1인 경우

❖ 질문: -1 이 QR가 되는 소수 p는 무엇인가?

❖ 다시말해서,


① 어떤 소수 p에 대해 다음 합동식 x² ≡ -1 (mod p)의 해가 존재하는가?

❖ ② 이 성립하는 소수 p는 무엇인가?

a = −1인 경우

❖ 질문: -1 이 QR가 되는 소수 p는 무엇인가?

❖ 자료: 


❖ 결과: 이 표를 정리하면,

❖ -1이 이차잉여인 소수 p=5,13,17,29

❖ -1이 이차비잉여인 소수 p=3,7,11,19,23,31

❖ 질문: 어떤 추측을 할 수 있을까?

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

추측과 오일러 판정법

❖ 추측: 


❖ 위의 추측을 증명하기 위해, 다음을 이용한다.

❖ 오일러 판정법: p가 홀수인 소수이면,


❖ 참고: 이것을 ‘페르마 소정리의 제곱근’이라 부른다.


a^p-1 ≡ 1 (mod p)

❖ 정리(중요!): 홀수인 소수 p에 대하여 


❖ 증명: 오일러 판정법에 의하여


❖ 경우1: p ≡ 1 (mod 4), 다시 말해 p=4k+1 이라 하자.

❖ 좌변 = (-1)^(p-1)/2 = (-1)^2k = 1 이므로

❖ 경우2: p ≡ 3 (mod 4), 즉 p=4k+3 이라 하자.

❖ 좌변 = (-1)^(p-1)/2 = (-1)^2k+1 = -1 이므로

❖ 법 4에 대해 1과 합동인 소수 정리: 1 (mod 4) 꼴인 소수는 무한히 많이 존재한다.

❖ 증명: (귀류법) p1,p2,...,pr 이 1 (mod 4)꼴인 모든 소수의 목록이라 가정하자.

❖ A = (2p1p2…pr)² + 1 이라 하자. --- (1)

❖ A=q1q2…qs ---(2) 로 소인수분해되었다고 하자.

❖ 주장: q1가 1 (mod 4) 꼴이다.

❖ 주장의 증명: (2p1p2…pr)² + 1 ≡ A ≡ 0 (mod q1)

❖ (2p1p2…pr)² ≡ -1 (mod q1)

❖ -1 이 이차잉여이므로 q1 ≡ 1 (mod 4) 를 만족한다.

❖ 그러므로, 1≤j≤r 인 어떤 j에 대해 q1 = pj.

❖ (1)에 의해, pj∤A, 그러나 (2)에 의해 q1|A. 모순!

a = 2인 경우

❖ 질문: 2가 QR이 되는 소수 p는 무엇인가?


다시말해, 합동식 x² ≡ 2 (mod p)를 만족하는 소수 p는 무엇인가?

❖ 자료:

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

❖ 결과: 2가 이차잉여인지 이차비잉여인지에 따라 소수를 분류하면 다음과 같다:

❖ 2가 이차잉여가 되는 법 p = 7,17,23,31,41,47,71,73,79,89,97,03,113,127

❖ 2가 이차비잉여가 되는 법 p = 3,5,11,13,19,29,37,43,53,59,61,67,83,101,107,109

❖ ① mod 4: 7,17,23,31,41,47,71,73,79,89,97 ≡ 3,1,3,3,1,3,3,1,3,1,1,3,1,3 (mod 4)
 3,5,11,13,19,29,37,43,53,59,61,67,83 ≡ 3,1,3,1,3,1,1,3,1,3,1,3,3,1,3,1 (mod 4)

❖ ② mod 3: 7,17,23,31,41,47,71,73,79,89,97 ≡ 1,2,2,1,2,2,2,1,1,2,1,1,2,1 (mod 3)


3,5,11,13,19,29,37,43,53,59,61,67,83 ≡ 0,2,2,1,1,2,1,1,2,2,1,1,2,2,2,1 (mod 3)

❖ ③ mod 8: 7,17,23,31,41,47,71,73,79,89,97 
 ≡ 7,1,7,7,1,7,7,1,7,1,1 (mod 8)

❖ 3,5,11,13,19,29,37,43,53,59,61,67,83 
 ≡ 3,5,3,5,3,5,5,3,5,3,5,3 (mod 8)

추측

❖ 추측: 


❖ 질문: 오일러 판정법을 쓸 수 있을까?

❖ ① 2^(p-1)/2 (mod p) 계산이 쉽지 않다.

❖ ② 가우스(Gauss)가 고안한 아이디어를 이용하면 가능하다!

❖ 예제(가우스의 방법): 2가 법 13에 대해 이차잉여인지 확인해보자.

❖ 답: 오일러 판정법에 의해

❖ ① 2・4・6・8・10・12 = (2・1)(2・2)(2・3)(2・4)(2・5)(2・6) = 2⁶・1・2・3・4・5・6 = 2⁶・6! —(1)

❖ ② 2・4・6・8・10・12 ≡ 2・4・6・(-5)・(-3)・(-1) ≡ (-1)³・2・4・6・5・3・1 ≡ -6! (mod 13) —(2)

❖ (1)(2)로부터 2⁶・6! ≡ -6! (mod 13) 이다.

❖ 그러므로 2⁶ ≡ -1 (mod 13)이다.

❖ 오일러 판정법에 의해 2는 13에 대해 이차비잉여다.

❖ 보조정리(일반화): 2^(p-1)/2 ≡ (-1)^{(음수 기호 개수)} (mod p).

❖ 여기서 음수 기호의 개수는 이다.

❖ 증명: q=(p-1)/2 라 하자.

❖ ① 2・4・6・・・(p-1) = 2^(p-1)/2・1・2・3・・・{(p-1)/2} = 2^q・q! —— (3)

❖ ② 2・4・6・8・10・12・・・{(p-1)/2} | {(p+3)/2}・・・(p-5)・(p-3)・(p-1)


≤ (p-1)/2 인 수는 > (p-1)/2 인 수는
 그대로둔다. p를 빼 준다.

❖ = 2・4・6・・・{(p-1)/2}・{-(p-3)/2}・・・・・(-5)・(-3)・(-1)

❖ = (-1)^{(음수 기호 개수)}・q! (mod p) —— (4)

❖ (3)과 (4)에 의해, 2^q ≡ (-1)^{(음수 기호 개수)} (mod p) 를 알 수 있다.

❖ 정리(중요!): 홀수인 소수 p에 대하여


❖ 증명: 1, 3, 5, 7 (mod 8)인 4가지 경우가 있다.

❖ ① p ≡ 3 (mod 8) 이라 하자. 즉, p=8k+3 이라 하자.

❖ p-1 = 8k+2 이고 (p-1)/2 = 4k+1 이다.

❖ 짝수가 (p-1)/2 = 4k+1 보다 큰지 작은지에 대한 내용은 
 2・4・6・・・4k | (4k+2)・(4k+4)・・・(8k+2).

❖ 2^(p-1)/2 ≡ (-1)^2k+1 ≡ -1 (mod p).

❖ 오일러 판정법에 의해 ≡ 2^(p-1)/2 ≡ -1 (mod p).

❖ ② p ≡ 1 (mod 8) ③ p ≡ 5 (mod 8) ④ p ≡ 7 (mod 8) → 유사!

❖ 연습: 다른 p에 대하여.

요약

❖ 정리1: 홀수인 소수 p에 대하여 


❖ 정리2: 홀수인 소수 p에 대하여