오일러 판정법

최근 수정 시각 : 2023-05-23 23:37:47 | 조회수 : 22

Euler's Criterion

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

목차

1. 진술
2. 증명
3. 예시
4. 영상

1. 진술

홀소수 pp에 대하여 (np)np12 (mod p)(n|p) \equiv n^{\frac{p-1}{2}} \ (\mathrm{mod}\ p)이다.

2. 증명

만약 (np)=1(n|p)=1이라면 x2n (mod p)x^2 \equiv n\ (\mathrm{mod}\ p)xZx \in \Bbb{Z}가 존재하므로 np12xp11 (mod p)n^{\frac{p-1}{2}} \equiv x^{p-1} \equiv 1\ (\mathrm{mod}\ p). 따라서 성립.

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

3. 예시

(1723)172221711342718963076331 (mod 23)(17|23) \equiv 17^{\frac{22}{2}} \equiv 17^11 \equiv 34271896307633 \equiv -1\ (\mathrm{mod}\ 23)

따라서 (1723)=1(17|23)=-1이다.

4. 영상



이 문서의 내용 중 전체 또는 일부는 오메가에서 가져왔으며 CC BY-NC-SA 3.0에 따라 이용할 수 있습니다.