돌아가기 삭제 이동 파일 올리기

오일러 판정법 _(편집)

(불러오기) (편집 필터 규칙)

[[분류:가져온 문서/오메가]]
Euler's Criterion

[[르장드르 기호]]를 계산하는 한 방법이다.

== 진술 ==
홀소수 [math(p)]에 대하여 [math((n|p) \equiv n^{\frac{p-1}{2}} \ (\mathrm{mod}\ p))]이다.

== 증명 ==
만약 [math((n|p)=1)]이라면 [math(x^2 \equiv n\ (\mathrm{mod}\ p))]인 [math(x \in \Bbb{Z})]가 존재하므로 [math(n^{\frac{p-1}{2}} \equiv x^{p-1} \equiv 1\ (\mathrm{mod}\ p))]. 따라서 성립.

임의의 [math(n \in \Bbb{Z})]에 대하여 [math(n^{\frac{p-1}{2}} \equiv \pm 1\ (\mathrm{mod}\ p))]인데, 합동방정식 [math(x^{\frac{p-1}{2}} \equiv 1\ (\mathrm{mod}\ p))]의 해는 정확히 [math(\frac{p-1}{2})]개이므로 그 해는 [math((n|p)=1,\ 1 \leq n \leq p-1)]인 [math(\frac{p-1}{2})]개의 자연수들이다. 그러므로 나머지 [math((n|p)=-1,\ 1 \leq n \leq p-1)]인 [math(\frac{p-1}{2})]개의 자연수들은 [math(n^{\frac{p-1}{2}} \equiv -1\ (\mathrm{mod}\ p))]을 만족한다. 따라서 증명되었다.

== 예시 ==
[math((17|23) \equiv 17^{\frac{22}{2}} \equiv 17^11 \equiv 34271896307633 \equiv -1\ (\mathrm{mod}\ 23))]

따라서 [math((17|23)=-1)]이다.

== 영상 ==
[youtube(deifygl7D5w)]

[Include(틀:가져옴2,O=오메가, C=[[https://creativecommons.org/licenses/by-nc-sa/3.0/deed.ko|CC BY-NC-SA 3.0]])]

(임시 저장) (임시 저장 불러오기)

(↪️) (💎) (🛠️) (추가)

[[분류:가져온 문서/오메가]]
Euler's Criterion

[[르장드르 기호]]를 계산하는 한 방법이다.

== 진술 ==
홀소수 [math(p)]에 대하여 [math((n|p) \equiv n^{\frac{p-1}{2}} \ (\mathrm{mod}\ p))]이다.

== 증명 ==
만약 [math((n|p)=1)]이라면 [math(x^2 \equiv n\ (\mathrm{mod}\ p))]인 [math(x \in \Bbb{Z})]가 존재하므로 [math(n^{\frac{p-1}{2}} \equiv x^{p-1} \equiv 1\ (\mathrm{mod}\ p))]. 따라서 성립.

임의의 [math(n \in \Bbb{Z})]에 대하여 [math(n^{\frac{p-1}{2}} \equiv \pm 1\ (\mathrm{mod}\ p))]인데, 합동방정식 [math(x^{\frac{p-1}{2}} \equiv 1\ (\mathrm{mod}\ p))]의 해는 정확히 [math(\frac{p-1}{2})]개이므로 그 해는 [math((n|p)=1,\ 1 \leq n \leq p-1)]인 [math(\frac{p-1}{2})]개의 자연수들이다. 그러므로 나머지 [math((n|p)=-1,\ 1 \leq n \leq p-1)]인 [math(\frac{p-1}{2})]개의 자연수들은 [math(n^{\frac{p-1}{2}} \equiv -1\ (\mathrm{mod}\ p))]을 만족한다. 따라서 증명되었다.

== 예시 ==
[math((17|23) \equiv 17^{\frac{22}{2}} \equiv 17^11 \equiv 34271896307633 \equiv -1\ (\mathrm{mod}\ 23))]

따라서 [math((17|23)=-1)]이다.

== 영상 ==
[youtube(deifygl7D5w)]

[Include(틀:가져옴2,O=오메가, C=[[https://creativecommons.org/licenses/by-nc-sa/3.0/deed.ko|CC BY-NC-SA 3.0]])]

비로그인 상태입니다. 편집한 내용을 저장하면 지금 접속한 IP가 기록됩니다.

편집을 전송하면 당신은 이 문서의 기여자로서 본인이 작성한 내용이 CC BY 4.0에 따라 배포되고, 기여한 문서의 하이퍼링크나 URL로 저작자 표시가 충분하다는 것에 동의하는 것입니다.