돌아이 너는... 에휴 .걍 꺼져라.

증명 병시나

s_i의 정의가

$s_i= \begin{cases} 4 & \text{if }i=0; \\ s_{i-1}^2-2 & \text{otherwise.} \end{cases}$ 이거였지.

그리고 지금 할게 $s_{p-2}\equiv0\pmod{M_p}.$ 이면 Mp (2^p-1)이 소수라는 걸 증명해야됨.

일단, 증명을 위해서 모든 i에 대해 $s_i = \omega^{2^i} + \bar{\omega}^{2^i}$ ( $\omega = 2 + \sqrt{3}$ , $\bar{\omega} = 2 - \sqrt{3}$ )

임을 증명해야한다. 물론 수학적 귀납법 쓰는겅미.

$s_0 = \omega^{2^0} + \bar{\omega}^{2^0} = (2 + \sqrt{3}) + (2 - \sqrt{3}) = 4.$ $\begin{array}{lcl}s_n & = & s_{n-1}^2 - 2 \\ & = & \left(\omega^{2^{n-1}} + \bar{\omega}^{2^{n-1}}\right)^2 - 2 \\ & = & \omega^{2^n} + \bar{\omega}^{2^n} + 2(\omega\bar{\omega})^{2^{n-1}} - 2 \\ & = & \omega^{2^n} + \bar{\omega}^{2^n}, \\ \end{array}$ 이건 중3 수학 아는 애면 다 알아먹는다. 난 과외알바하는 학생 아니니까 그렇게 알고 ㅇㅇ (이번 여름에는 인턴할겨)
$\omega\bar{\omega} = (2 + \sqrt{3})(2 - \sqrt{3}) = 1$ 인거 써먹음. 중3이면 이런거 다 배우지?

이제 $s_i = \omega^{2^i} + \bar{\omega}^{2^i}$ 인거다?

[edit]충분조건

일단, $s_{p-2}\equiv0\pmod{M_p}$ 이면 $M_p$ 가 소수임을 증명할거임. (이게 충분조건이지)

$s_{p-2} \equiv 0 \pmod{M_p}$ 이면, 어떤 정수 k에 대해 $\omega^{2^{p-2}} + \bar{\omega}^{2^{p-2}} = kM_p$ 가 성립하지(합동식이니까 ㅇㅇ)

그 다음 이 세줄은 식정리.

$\begin{align} \omega^{2^{p-2}} & = kM_p - \bar{\omega}^{2^{p-2}} \\ \left(\omega^{2^{p-2}}\right)^2 & = kM_p\omega^{2^{p-2}} - (\omega\bar{\omega})^{2^{p-2}} \\ \omega^{2^{p-1}} & = kM_p\omega^{2^{p-2}} - 1.\quad\quad\quad\quad\quad(1) \end{align}$ ( $\omega\bar{\omega} = (2 + \sqrt{3})(2 - \sqrt{3}) = 1$ 인것을 이용하기 위해 ω^(2^(p-2))를 양변에 곱해줌.) 일단 귀류법을 써서 증명할거기 때문에, Mp가 소수가 아니고 Mp의 가장 작은 소인수가 q라고 가정한다.(여기서 메르센소수는 홀수니까 q>2어야겠지?)그러면 $X = \{a + b\sqrt{3} | a, b \in \mathbb{Z}_q\}$ ,( $\mathbb{Z}_q$ 는 0부터 q-1까지의 정수. 사실 mod q에 대한 finite field) 인 집합을 고려하자(원소는 q^2개. 그리고 여기서 q > 2니까 $~ \omega$ , $\bar{\omega}$ 는 $X$ 의 원소임을 알 수 있지.)

그리고 $X$ 의 원소간의 곱셈을 아래와 같이 정의한다.

$(a + b\sqrt{3})(c + d\sqrt{3}) = [(ac + 3bd) \hbox{ mod } q] + [(bc + ad) \hbox{ mod } q]\sqrt{3}.$ mod q가 붙는거는 X를 q로 나눈 "나머지"를 구하기 위해서 그런거(정수부 따로, sqrt(3) 붙은 부분 따로 고려해서 나머지를 구한다.)이때, $X$ 에 속한 두 숫자를 위와 같은 방법으로 곱한 값도 $X$ 에 속한다.(a,b,c,d전부 정수니까) 하지만, 이런 곱셈에서는 모든 원소에 역원이 전부 있는게 아니기 때문에(0이라던가) 이 집합과 곱셈은 군을 이루지 못함.(더보시오:http://ko.wikipedia.org/wiki/%EA%B5%B0_(%EC%88%98%ED%95%99))그래서 군을 만들어주기 위해 역원이 존재하는 X의 원소만 모은 부분집합 X*를 쓰게 됨.(당연히 원소 개수는 $q^2-1$ 개를 넘을 수 없다! 물론 0때문임.)

이제 본격적인 증명 시작.(지금까지는 포석을 깔아둔거)

일단 위에서 Mp의 약수로 q가 있다고 했으니까 $M_p \equiv 0 \pmod q$ , 또 q>2니까 $\omega \in X$ .그리고 X라는 집합에서의 곱셈의 정의에 의해 $kM_p\omega^{2^{p-2}} = 0$ .

또 (1)에 의해 $\omega^{2^{p-1}} = -1$ .왼쪽의 식 양변 제곱하면 $\omega^{2^p} = 1$ 이니까 $\omega$ 의 "곱셈"에 대한 역원은 $\omega^{2^{p}-1}$ 이 되고, 따라서 $\omega$ 는 X*의 원소임.

그리고, $\omega^{2^p} = 1$ 이니까, X*의 order(군 안에 속한 원소 a에 대해,am 이 항등원이 되는 가장 작은 m을 구하고, 각 원소에 대해 m값을 구해서 그 중 가장 큰 값이 order가 됨)은 $2^p$ 의 약수가 된다그런데, $\omega^{2^{p-1}} \neq 1$ 이니까, X*의 order는 정확히 $2^p$ 가 된다.(뭐, $2^p$ 의 소인수는 2밖에 없으니까 $\omega^{2^{p-1}} \neq 1$ 이되면 X*order가 정확히 $2^p$ 인거)

그리고 order는 다음을 성립. $2^p \leq q^2 - 1 < q^2$ (order<=group의 크기 때문)

그런데, q는 $M_p$ 의 가장 작은 소수니까 $q^2 \leq M_p = 2^p-1$ 가 되고,

$2^p < 2^p-1$ 이 됨. 여기서 모순이 일어났으니까 $M_p$ 가 합성수라는 가정이 틀린거.

따라서 $M_p$ 는 소수

[edit]필요조건

$M_p$ 가 소수면 $s_{p-2} \equiv0\pmod{M_p}$ 을 보이면 증명 끝.

p > 1인 홀수 p에 대해 2 p − 1 는 mod 12에 대해 7 이 나오고 이 때문에 Legendre symbol $(3|M_p)$ 값이 -1을 갖게 된다.(관심있으면 Legendre symbol 보던가. 난 니 선생이 아니란다.

나를 선생으로 쓸려면 돈을 내던가. 근데, 내가 거절할건데 어쩌지?)

그리고 Legendre symbol의 정의에 의해 3이 mod Mp에 대해 quadratic non-residue(q에 대해 $x^2\equiv q \pmod{n}.$ 인 x가 없는 경우를 의미함.)임을 알수 있음.

따라서 Euler's criterion에 의해 다음이 성립한다.(Euler's criterion 증명은 위키에 있으니까 알아서 읽던지, 난 정수론 책을 쓸 생각은 전혀 없어. 정수론 좋아하는 돌아이 너나 그짓해라.) $3^{(M_p-1)/2} \equiv -1 \pmod{M_p}.\,$

그리고 $2^p \equiv 1 \pmod{M_p}$ 니까 2 는 mod $M_p$ 에 대해 quadratic residue가 되고, $2 \equiv 2^{p+1} = \left(2^{(p+1)/2}\right)^2 \pmod{M_p}$ 가 성립.

따라서 Euler's criterion에 의해 다음이 성립:

$2^{(M_p-1)/2} \equiv 1 \pmod{M_p}.\,$

$\sigma = 2\sqrt{3}$ 을 정의하고, 충분조건 쓸때 나왔던 군처럼 X* = $\{a + b\sqrt{3} | a, b \in \mathbb{Z}_{M_p}\}$ .를 정의.

그리고 $M_p$ 소수니까 페르마의 소정리, $a^{M_p} \equiv a \pmod{M_p}$ 가 성립

(Fermat's little theorem<-링크)

그리고 이항정리쓰면

$(x+y)^{M_p} \equiv x^{M_p} + y^{M_p} \pmod{M_p}$ 이런 식이 나옴,(Mp가 곱해지는 관계로xy어쩌고 하는 항들은 전부 사라짐.)

그러면 group X* 에 대해서 다음이 성립:

$\begin{align} (6+\sigma)^{M_p} & = 6^{M_p} + (2^{M_p})(\sqrt{3}^{M_p}) \\ & = 6 + 2(3^{(M_p-1)/2})\sqrt{3} \\ & = 6 + 2(-1)\sqrt{3} \\ & = 6 - \sigma. \end{align}$

그리고, 계산을 해보면 $\omega = (6+\sigma)^2/24$ 가 됨(ω는 맨 위에서 정의한 그거)

.따라서 group X*에 속하는 $\omega^{(M_p+1)/2}$ 를 다음과 같이 계산 가능.

$\begin{align} \omega^{(M_p+1)/2} & = (6 + \sigma)^{M_p+1}/24^{(M_p+1)/2} \\ & = (6 + \sigma)^{M_p}(6 + \sigma)/(24 \times 24^{(M_p-1)/2}) \\ & = (6 - \sigma)(6 + \sigma)/(-24) \\ & = -1. \end{align}$ ( $24^{(M_p-1)/2} = (2^{(M_p-1)/2})^3(3^{(M_p-1)/2}) = (1)^3(-1) = -1.$ 을 사용한다.)

그리고 $M_p \equiv 3 \pmod 4$ ,(p>2니까.mod4에 의해 2^p-1하고 -1이 합동되니까 당연한거)

이므로,

양변에 $\bar{\omega}^{(M_p+1)/4}$ 곱해주면,( $\omega\bar{\omega}=1$ 은 또 씁니다.):

$\begin{align} \omega^{(M_p+1)/2}\bar{\omega}^{(M_p+1)/4} & = -\bar{\omega}^{(M_p+1)/4} \\ \omega^{(M_p+1)/4} + \bar{\omega}^{(M_p+1)/4} & = 0 \\ \omega^{(2^p-1+1)/4} + \bar{\omega}^{(2^p-1+1)/4} & = 0 \\ \omega^{2^{p-2}} + \bar{\omega}^{2^{p-2}} & = 0 \\ s_{p-2} & = 0. \end{align}$ sp−2 가 정수고, X*에서의 0에 해당되므로, mod Mp.에 대해서도 0
앞으로는 알아서 좀 해라 ㅉㅉ

전체목록

돌아이 너는... 에휴 .걍 꺼져라.

믿음과신앙베스트

명예의 전당

추천 많은 톡

댓글 많은 톡

새로운 베플

공감많은 뉴스 시사

공유하기

뉴스 플러스