Euler's Criterion
르장드르 기호 를 계산하는 한 방법이다.
홀소수
p p p 에 대하여
( n ∣ p ) ≡ n p − 1 2 ( m o d p ) (n|p) \equiv n^{\frac{p-1}{2}} \ (\mathrm{mod}\ p) ( n ∣ p ) ≡ n 2 p − 1 ( mod p ) 이다.
만약
( n ∣ p ) = 1 (n|p)=1 ( n ∣ p ) = 1 이라면
x 2 ≡ n ( m o d p ) x^2 \equiv n\ (\mathrm{mod}\ p) x 2 ≡ n ( mod p ) 인
x ∈ Z x \in \Bbb{Z} x ∈ Z 가 존재하므로
n p − 1 2 ≡ x p − 1 ≡ 1 ( m o d p ) n^{\frac{p-1}{2}} \equiv x^{p-1} \equiv 1\ (\mathrm{mod}\ p) n 2 p − 1 ≡ x p − 1 ≡ 1 ( mod p ) . 따라서 성립.
임의의
n ∈ Z n \in \Bbb{Z} n ∈ Z 에 대하여
n p − 1 2 ≡ ± 1 ( m o d p ) n^{\frac{p-1}{2}} \equiv \pm 1\ (\mathrm{mod}\ p) n 2 p − 1 ≡ ± 1 ( mod p ) 인데, 합동방정식
x p − 1 2 ≡ 1 ( m o d p ) x^{\frac{p-1}{2}} \equiv 1\ (\mathrm{mod}\ p) x 2 p − 1 ≡ 1 ( mod p ) 의 해는 정확히
p − 1 2 \frac{p-1}{2} 2 p − 1 개이므로 그 해는
( n ∣ p ) = 1 , 1 ≤ n ≤ p − 1 (n|p)=1,\ 1 \leq n \leq p-1 ( n ∣ p ) = 1 , 1 ≤ n ≤ p − 1 인
p − 1 2 \frac{p-1}{2} 2 p − 1 개의 자연수들이다. 그러므로 나머지
( n ∣ p ) = − 1 , 1 ≤ n ≤ p − 1 (n|p)=-1,\ 1 \leq n \leq p-1 ( n ∣ p ) = − 1 , 1 ≤ n ≤ p − 1 인
p − 1 2 \frac{p-1}{2} 2 p − 1 개의 자연수들은
n p − 1 2 ≡ − 1 ( m o d p ) n^{\frac{p-1}{2}} \equiv -1\ (\mathrm{mod}\ p) n 2 p − 1 ≡ − 1 ( mod p ) 을 만족한다. 따라서 증명되었다.
( 17 ∣ 23 ) ≡ 1 7 22 2 ≡ 1 7 1 1 ≡ 34271896307633 ≡ − 1 ( m o d 23 ) (17|23) \equiv 17^{\frac{22}{2}} \equiv 17^11 \equiv 34271896307633 \equiv -1\ (\mathrm{mod}\ 23) ( 17∣23 ) ≡ 1 7 2 22 ≡ 1 7 1 1 ≡ 34271896307633 ≡ − 1 ( mod 23 ) 따라서
( 17 ∣ 23 ) = − 1 (17|23)=-1 ( 17∣23 ) = − 1 이다.