Archive for June, 2012

-163과 오일러의 소수 생성 다항식 x^2+x+41

Tuesday, June 12th, 2012

-163과 오일러의 소수 생성 다항식 euler_1.gif

트위터의 타임라인(2011-7-29)을 보다보니 다항식 euler_2.gif1460x1539 일 때, 소수가 된다는 트윗이 보인다. 왜 그런지 한번 생각해 보자.
euler_3.gif는 이차다항식이므로 판별식을 한번 계산해 보자.

euler_4.gif

euler_5.gif

-163 이라는 숫자가 나왔다. 정수론에 관심이 있는 사람이라면 여기서 뭔가를 느낄 수 있다. 왜냐하면 이는 바로 오일러의 소수 생성 다항식 euler_6.gif 의 판별식이기 때문이다.

euler_7.gif

euler_8.gif

아마도 위의 다항식은 오일러의 소수 생성 다항식을 약간 숨겨 놓은 것에 불과할 것이라고 추측된다. euler_9.gif에 있는 x의 자리에 x+1500 을 넣고 정리를 해보자.

euler_10.gif

euler_11.gif

결국 맨 위에 있는 말은 “오일러의 소수 생성 다항식 euler_12.gif-40≤x≤39 인 정수 x에 대하여 소수가 된다” 는 사실을 살짝 꼬아놓은 것에 불과하다.

소수판정

-40≤x≤39일 때, euler_13.gif의 값을 한번 살펴 보자.

euler_14.gif

euler_15.gif

이 테이블을 보면, f(-40)=f(39), f(-39)=f(38),···,f(-1)=f(0) 임을 관찰할 수 있다. f(-x-1)=f(x) 이 성립하기 때문이다.

euler_16.gif

euler_17.gif

-40≤x≤39일 때를 생각하는 대신 , 0x39 일 때, euler_18.gif의 값이 소수가 됨을 보여도 충분함을 알게 되었다. 그럼 테이블을 만들어 보자.

euler_19.gif

euler_20.gif
0 41
1 43
2 47
3 53
4 61
5 71
6 83
7 97
8 113
9 131
10 151
11 173
12 197
13 223
14 251
15 281
16 313
17 347
18 383
19 421
20 461
21 503
22 547
23 593
24 641
25 691
26 743
27 797
28 853
29 911
30 971
31 1033
32 1097
33 1163
34 1231
35 1301
36 1373
37 1447
38 1523
39 1601

이제 이 테이블을 가지고 이들이 정말 모두 소수가 되는지 생각해 보자.
자연수 n이 주어져 있을 때, n 이 소수인지 아닌지를 알려면 euler_21.gif 보다 작은 모든 소수로 나눠보아 나누어지지 않음을 확인하면 된다.
작은 소수에 대해서부터 따져보자. 2로 나눈 나머지를 보자.

euler_22.gif

euler_23.gif mod 2
0 41 1
1 43 1
2 47 1
3 53 1
4 61 1
5 71 1
6 83 1
7 97 1
8 113 1
9 131 1
10 151 1
11 173 1
12 197 1
13 223 1
14 251 1
15 281 1
16 313 1
17 347 1
18 383 1
19 421 1
20 461 1
21 503 1
22 547 1
23 593 1
24 641 1
25 691 1
26 743 1
27 797 1
28 853 1
29 911 1
30 971 1
31 1033 1
32 1097 1
33 1163 1
34 1231 1
35 1301 1
36 1373 1
37 1447 1
38 1523 1
39 1601 1

모두 1이 된다. 이는 위의 테이블에 있는 40개의 숫자들이 모두 홀수가 됨을 보여준다. 따라서 2로는 나누어지지 않음을 확인할 수 있다.
이제 그 다음 소수인 3으로 나눈 나머지도 따져보자.

euler_24.gif

euler_25.gif mod 3
0 41 2
1 43 1
2 47 2
3 53 2
4 61 1
5 71 2
6 83 2
7 97 1
8 113 2
9 131 2
10 151 1
11 173 2
12 197 2
13 223 1
14 251 2
15 281 2
16 313 1
17 347 2
18 383 2
19 421 1
20 461 2
21 503 2
22 547 1
23 593 2
24 641 2
25 691 1
26 743 2
27 797 2
28 853 1
29 911 2
30 971 2
31 1033 1
32 1097 2
33 1163 2
34 1231 1
35 1301 2
36 1373 2
37 1447 1
38 1523 2
39 1601 2

3으로 나누어지지 않음을 확인했다. 5에 대해서도 한번 해보자.

euler_26.gif

euler_27.gif mod 5
0 41 1
1 43 3
2 47 2
3 53 3
4 61 1
5 71 1
6 83 3
7 97 2
8 113 3
9 131 1
10 151 1
11 173 3
12 197 2
13 223 3
14 251 1
15 281 1
16 313 3
17 347 2
18 383 3
19 421 1
20 461 1
21 503 3
22 547 2
23 593 3
24 641 1
25 691 1
26 743 3
27 797 2
28 853 3
29 911 1
30 971 1
31 1033 3
32 1097 2
33 1163 3
34 1231 1
35 1301 1
36 1373 3
37 1447 2
38 1523 3
39 1601 1

이들은 모두 5로도 나누어지지 않는다.

이렇게 하나하나의 소수에 대하여 테스트를 한다고 할때, 어느 소수까지 테스트를 해 보면 충분할까? n 이 소수인지 아닌지를 알려면 euler_28.gif 보다 작은 모든 소수로 나눠보아 나누어지지 않음을 확인하면 되므로 euler_29.gif보다 작은 소수들에 대해 따져보면 충분하다.

euler_30.gif

euler_31.gif

15개 정도의 소수의 목록을 뽑아보면,

euler_32.gif

euler_33.gif

한편 위에서 5로 나눈 나머지의 표를 가만 보면 1,3,2,3,1 가 계속해서 반복된다는 것을 관찰할 수 있다. 이 주기성은 합동식의 성질을 생각하면 쉽게 알 수 있는 것이다. 따라서 40개의 숫자의 나머지를 모두 체크하는 것은 불필요한 일이다. 5에 대한 나머지를 따지는 것으로 것이라면, 0x4 일 때의 euler_34.gif값의 나머지만 따져보면 되는 것이다.

정리하자면, 2부터 37 사이에 있는 12개의 소수 p에 대해서 0≤x≤p-1 일 때 euler_35.gifp로 나눈 나머지가 0이 되지 않는다는 것을 보이면 원하는 것이 증명된다. 여기서 이차잉여의 개념이 등장하게 된다.

이차잉여의 등장

소수 p 를 하나 고정시키자. 0≤x≤p-1일 때, euler_36.gifp로 나눈 나머지가 0이 되지 않는다는 것을 증명하기 위해 다항식 euler_37.gif를 mod p로 따져보자.
p=2인 경우는

euler_38.gif

euler_39.gif

euler_40.gif이므로 어떤 정수 x에 대해서도 euler_41.gif를 2로 나눈 나머지가 0이 되지 않음을 증명할 수 있다.

p=3인 경우는

euler_42.gif

euler_43.gif

mod 3 으로 생각할 때, euler_44.gif 이 성립한다.

euler_45.gif

euler_46.gif

그러나 euler_47.gif 은 절대로 0이 될 수 없는데, 이는 -1≡2이 3의 비이차잉여, 즉 합동식 euler_48.gif 를 만족시키는 y는 존재하지 않기 때문이다.

mod 5 로 생각한다면,

euler_49.gif

euler_50.gif

이를 위에서처럼 완전제곱꼴로 표현해보자. euler_51.gif 이 성립한다.

euler_52.gif

euler_53.gif

euler_54.gif 는 절대로 0이 될 수 없는데, 이는 -2≡3이 5의 비이차잉여, 즉 합동식 euler_55.gif 를 만족시키는 y는 존재하지 않기 때문이다. 이제 일반적인 증명이 가능하다.

정리 : 소수 2p37 에 대하여, euler_56.gifp로 나눈 나머지는 0이 될 수 없다.

p=2 인 경우는 위에서 증명하였다.
소수 2<p37 를 하나 고정시키자. {1,2,…,p-1}는 기약잉여계이므로, 2b≡1 (mod p) 를 만족시키는 b는 반드시 존재한다.
euler_57.gif 이므로, euler_58.gif이 소수 p에 대한 비이차잉여임을 보이면 충분하다. 르장드르 부호를 계산해보자.
euler_59.gif

-163 !!!
마침내 -163이 등장했다. 소수 2<p37 가 모두 euler_60.gif 를 만족시키는 보이는 것으로 충분함을 알 수 있다.

euler_61.gif

p euler_62.gif
3 -1
5 -1
7 -1
11 -1
13 -1
17 -1
19 -1
23 -1
29 -1
31 -1
37 -1

이렇게 하여 “오일러의 소수 생성 다항식 euler_63.gif-40≤x≤39 인 정수 x에 대하여 소수가 된다”는 것을 알 수 있다.

관련된 수학노트 항목