(+)분류 : 가져온 문서/오메가
Euler's Criterion
르장드르 기호를 계산하는 한 방법이다.
1. 진술 ✎ ⊖
홀소수 p에 대하여 (n|p) \\equiv n^{\\frac{p-1}{2}} \\ (\\mathrm{mod}\\ p)이다.
2. 증명 ✎ ⊖
만약 (n|p)=1이라면 x^2 \\equiv n\\ (\\mathrm{mod}\\ p)인 x \\in \\Bbb{Z}가 존재하므로 n^{\\frac{p-1}{2}} \\equiv x^{p-1} \\equiv 1\\ (\\mathrm{mod}\\ p). 따라서 성립.
임의의 n \\in \\Bbb{Z}에 대하여 n^{\\frac{p-1}{2}} \\equiv \\pm 1\\ (\\mathrm{mod}\\ p)인데, 합동방정식 x^{\\frac{p-1}{2}} \\equiv 1\\ (\\mathrm{mod}\\ p)의 해는 정확히 \\frac{p-1}{2}개이므로 그 해는 (n|p)=1,\\ 1 \\leq n \\leq p-1인 \\frac{p-1}{2}개의 자연수들이다. 그러므로 나머지 (n|p)=-1,\\ 1 \\leq n \\leq p-1인 \\frac{p-1}{2}개의 자연수들은 n^{\\frac{p-1}{2}} \\equiv -1\\ (\\mathrm{mod}\\ p)을 만족한다. 따라서 증명되었다.
임의의 n \\in \\Bbb{Z}에 대하여 n^{\\frac{p-1}{2}} \\equiv \\pm 1\\ (\\mathrm{mod}\\ p)인데, 합동방정식 x^{\\frac{p-1}{2}} \\equiv 1\\ (\\mathrm{mod}\\ p)의 해는 정확히 \\frac{p-1}{2}개이므로 그 해는 (n|p)=1,\\ 1 \\leq n \\leq p-1인 \\frac{p-1}{2}개의 자연수들이다. 그러므로 나머지 (n|p)=-1,\\ 1 \\leq n \\leq p-1인 \\frac{p-1}{2}개의 자연수들은 n^{\\frac{p-1}{2}} \\equiv -1\\ (\\mathrm{mod}\\ p)을 만족한다. 따라서 증명되었다.
3. 예시 ✎ ⊖
(17|23) \\equiv 17^{\\frac{22}{2}} \\equiv 17^11 \\equiv 34271896307633 \\equiv -1\\ (\\mathrm{mod}\\ 23)
따라서 (17|23)=-1이다.
따라서 (17|23)=-1이다.
