최근 편집
최근 토론
게시판 메인
도구
투표
무작위 문서
스킨 설정
파일 올리기
기타 도구
216.73.216.149
IP
사용자 도구
사용자 설정
로그인
회원 가입
최근 편집
최근 토론
돌아가기
삭제
이동
파일 올리기
오일러 판정법
(편집)
(불러오기)
(편집 필터 규칙)
[[분류:가져온 문서/오메가]] 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]])]
(임시 저장)
(임시 저장 불러오기)
기본값
모나코 에디터
normal
namumark
namumark_beta
macromark
markdown
custom
raw
(↪️)
(💎)
(🛠️)
(추가)
[[분류:가져온 문서/오메가]] 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로 저작자 표시가 충분하다는 것에 동의하는 것입니다.
전송
미리보기