Euler's Criterion
르장드르 기호를 계산하는 한 방법이다.
홀소수 p에 대하여 (n|p) \\equiv n^{\\frac{p-1}{2}} \\ (\\mathrm{mod}\\ p)이다.
만약 (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)을 만족한다. 따라서 증명되었다.
(17|23) \\equiv 17^{\\frac{22}{2}} \\equiv 17^11 \\equiv 34271896307633 \\equiv -1\\ (\\mathrm{mod}\\ 23)
따라서 (17|23)=-1이다.
