제곱 잉여 문서 원본 보기

{{위키데이터 속성 추적}}
[[수론]]에서, 정수 <math>n</math>에 대해, <math>a</math>가 <math>n</math>의 '''제곱잉여(이차잉여)'''(二次剩餘, {{llang|en|quadratic residue}}) 라는 것은 <math>x^2=a</math> mod <math>n</math>를 만족하는 정수 <math>x</math>가 존재한다는 것이다.

만약 이 방정식을 만족하는 정수 <math>x</math>가 존재하지 않으면, <math>a</math>는 <math>n</math>의 '''제곱 비잉여(이차 비잉여)'''(非二次剩餘,{{llang|en|quadratic nonresidue}}) 라고 한다.

예를 들어,
:<math>1^2 \equiv 1,\ 3^2 \equiv 2,\ 2^2 \equiv 4 \pmod{7}</math>
이므로, 1, 2, 4는 7에 대한 제곱잉여이다. 한편, 3, 5, 6은 7에 대한 제곱잉여가 아니다. 일반적으로 홀수인 [[소수 (수론)|소수]] <math>p\,</math>에 대하여 <math>1, 2, \cdots, p-1</math> 가운데 제곱잉여인 수와 제곱잉여가 아닌 수는 각각 <math>\frac{p-1}{2}</math> 개씩 존재한다.

두 홀수 [[소수 (수론)|소수]] <math>p, q</math>가 서로에 대해 제곱잉여인지 여부에 대하여, [[이차 상호 법칙]]이라 부르는 대칭적인 관계가 성립한다.

== 제곱잉여표 ==
{| class="wikitable" style="text-align:center;"
|+ 제곱잉여
|-
! ''x'' || 1||2|| 3|| 4||5|| 6|| 7|| 8 ||9 ||10|| 11|| 12|| 13|| 14 ||15|| 16|| 17|| 18 ||19|| 20|| 21|| 22|| 23|| 24 ||25
|-
! ''x''<sup>2</sup>
! style="width:25px;"|1
! style="width:25px;"|4
! style="width:25px;"|9
! style="width:25px;"|16
! style="width:25px;"|25
! style="width:25px;"|36
! style="width:25px;"|49
! style="width:25px;"|64
! style="width:25px;"|81
!100|| 121|| 144|| 169|| 196 ||225|| 256|| 289|| 324 ||361 || 400|| 441|| 484|| 529|| 576 ||625
|-
! mod 2
| 1 || 0
| 1 || 0
| 1 || 0
| 1 || 0
| 1 || 0
| 1 || 0
| 1 || 0
| 1 || 0
| 1 || 0
| 1 || 0
| 1 || 0
| 1 || 0
| 1
|-
! mod 3
| 1 || 1 || 0
| 1 || 1 || 0
| 1 || 1 || 0
| 1 || 1 || 0
| 1 || 1 || 0
| 1 || 1 || 0
| 1 || 1 || 0
| 1 || 1 || 0
| 1
|-
! mod 4
| 1 || 0
| 1 || 0
| 1 || 0
| 1 || 0
| 1 || 0
| 1 || 0
| 1 || 0
| 1 || 0
| 1 || 0
| 1 || 0
| 1 || 0
| 1 || 0
| 1
|-
! mod 5
| 1 || 4 || 4 || 1 || 0
| 1 || 4 || 4 || 1 || 0
| 1 || 4 || 4 || 1 || 0
| 1 || 4 || 4 || 1 || 0
| 1 || 4 || 4 || 1 || 0
|-

! mod 6
| 1 || 4 || 3 || 4 || 1 || 0
| 1 || 4 || 3 || 4 || 1 || 0
| 1 || 4 || 3 || 4 || 1 || 0
| 1 || 4 || 3 || 4 || 1 || 0
| 1
|-
! mod 7
| 1 || 4 || 2 || 2 || 4 || 1 || 0
| 1 || 4 || 2 || 2 || 4 || 1 || 0
| 1 || 4 || 2 || 2 || 4 || 1 || 0
| 1 || 4 || 2 || 2
|-

! mod 8
| 1 || 4 || 1 || 0
| 1 || 4 || 1 || 0
| 1 || 4 || 1 || 0
| 1 || 4 || 1 || 0
| 1 || 4 || 1 || 0
| 1 || 4 || 1 || 0
| 1
|-

! mod 9
| 1 || 4 || 0 || 7 || 7 || 0 || 4 || 1 || 0
| 1 || 4 || 0 || 7 || 7 || 0 || 4 || 1 || 0
| 1 || 4 || 0 || 7 || 7 || 0 || 4
|-

! mod 10
| 1 || 4 || 9 || 6 || 5 || 6 || 9 || 4 || 1 || 0
| 1 || 4 || 9 || 6 || 5 || 6 || 9 || 4 || 1 || 0
| 1 || 4 || 9 || 6 || 5
|-

! mod 11
| 1 || 4 || 9 || 5 || 3 || 3 || 5 || 9 || 4 || 1 || 0
| 1 || 4 || 9 || 5 || 3 || 3 || 5 || 9 || 4 || 1 || 0
| 1 || 4 || 9
|-

! mod 12
| 1 || 4 || 9 || 4 || 1 || 0
| 1 || 4 || 9 || 4 || 1 || 0
| 1 || 4 || 9 || 4 || 1 || 0
| 1 || 4 || 9 || 4 || 1 || 0
| 1
|-

! mod 13
| 1 || 4 || 9 || 3 || 12 || 10 || 10 || 12 || 3 || 9 || 4 || 1 || 0
| 1 || 4 || 9 || 3 || 12 || 10 || 10 || 12 || 3 || 9 || 4 || 1
|-

! mod 14
| 1 || 4 || 9 || 2 || 11 || 8 || 7 || 8 || 11 || 2 || 9 || 4 || 1 || 0
| 1 || 4 || 9 || 2 || 11 || 8 || 7 || 8 || 11 || 2 || 9
|-

! mod 15
| 1 || 4 || 9 || 1 || 10 || 6 || 4 || 4 || 6 || 10 || 1 || 9 || 4 || 1 || 0
| 1 || 4 || 9 || 1 || 10 || 6 || 4 || 4 || 6 || 10
|-

! mod 16
| 1 || 4 || 9 || 0 || 9 || 4 || 1 || 0
| 1 || 4 || 9 || 0 || 9 || 4 || 1 || 0
| 1 || 4 || 9 || 0 || 9 || 4 || 1 || 0
| 1
|-

! mod 17
| 1 || 4 || 9 || 16 || 8 || 2 || 15 || 13 || 13 || 15 || 2 || 8 || 16 || 9 || 4 || 1 || 0
| 1 || 4 || 9 || 16 || 8 || 2 || 15 || 13
|-

! mod 18
| 1 || 4 || 9 || 16 || 7 || 0 || 13 || 10 || 9 || 10 || 13 || 0 || 7 || 16 || 9 || 4 || 1 || 0
| 1 || 4 || 9 || 16 || 7 || 0 || 13
|-

! mod 19
| 1 || 4 || 9 || 16 || 6 || 17 || 11 || 7 || 5 || 5 || 7 || 11 || 17 || 6 || 16 || 9 || 4 || 1 || 0
| 1 || 4 || 9 || 16 || 6 || 17
|-

! mod 20
| 1 || 4 || 9 || 16 || 5 || 16 || 9 || 4 || 1 || 0
| 1 || 4 || 9 || 16 || 5 || 16 || 9 || 4 || 1 || 0
| 1 || 4 || 9 || 16 || 5
|-

! mod 21
| 1 || 4 || 9 || 16 || 4 || 15 || 7 || 1 || 18 || 16 || 16 || 18 || 1 || 7 || 15 || 4 || 16 || 9 || 4 || 1 || 0
| 1 || 4 || 9 || 16
|-

! mod 22
| 1 || 4 || 9 || 16 || 3 || 14 || 5 || 20 || 15 || 12 || 11 || 12 || 15 ||  20 || 5 || 14 || 3 || 16 ||  9 || 4 || 1 || 0
| 1 || 4 || 9
|-

! mod 23
| 1 || 4 || 9 || 16 || 2 || 13 || 3 || 18 || 12 || 8 || 6 || 6 || 8 || 12 ||18 || 3 || 13 || 2 || 16 || 9 || 4 || 1 || 0
| 1 || 4
|-

! mod 24
| 1 || 4 || 9 || 16 || 1 || 12 || 1 || 16 || 9 || 4 || 1 || 0
| 1 || 4 || 9 || 16 || 1 || 12 || 1 || 16 || 9 || 4 || 1 || 0
| 1
|-

! mod 25
| 1 || 4 || 9 || 16 || 0 || 11 || 24 || 14 || 6 || 0 || 21 || 19  || 19 || 21 || 0 || 6 || 14 || 24 || 11 || 0 || 16 || 9 || 4 || 1 || 0
|}

== 같이 보기 ==
* [[르장드르 기호]]

== 외부 링크 ==
* {{매스월드|id=QuadraticResidue|title=Quadratic residue}}

{{전거 통제}}

[[분류:NP-완전 문제]]
[[분류:모듈러 산술]]