제곱 잉여

수론에서, **제곱 잉여**(-剩餘, ) 또는 **이차 잉여**(二次剩餘)는 어떤 정수의 제곱과 (주어진 법 아래) 합동인 정수이다. **제곱 비잉여**(-非剩餘, ) 또는 **이차 비잉여**(二次非剩餘)는 어떤 정수의 제곱과 (주어진 법 아래) 합동일 수 없는 정수이다.

## 정의
n이 2 이상의 정수이며, a가 임의의 정수라고 하자. 만약
:x^2\equiv a\pmod n
인 정수 x가 존재한다면, a를 **법 <math>n</math>에 대한 제곱 잉여**()라고 한다. 법 n에 대한 제곱 잉여가 아닌 정수를 **법 <math>n</math>에 대한 제곱 비잉여**()라고 한다.

일부 저자는 n이 홀수 소수이며, a와 n이 서로소일 것을 요구한다.

## 성질
만약 a\equiv b\pmod n이라면, a와 b가 법 n에 대한 제곱 잉여인지 여부는 같다. 따라서, 주어진 법 n에 대한 제곱 잉여를 다룰 때, \{0,1,\dots,n-1\} 속 법 n에 대한 제곱 잉여에 집중하여도 충분하다.

만약 n이 짝수라면, \{0,1,\dots,n-1\} 속 법 n에 대한 제곱 잉여는 n/2+1개 이하이다. 만약 n이 홀수라면, \{0,1,\dots,n-1\} 속 법 n에 대한 제곱 잉여는 (n+1)/2개 이하이다.

### 소수에 대한 제곱 잉여
모든 정수는 법 2에 대한 제곱 잉여이다.

홀수 소수 p에 대하여, \{1,2,\dots,p-1\} 가운데 절반은 법 p에 대한 제곱 잉여이며, 나머지 절반은 법 p에 대한 제곱 비잉여이다. 즉, (p-1)/2개의 제곱 잉여와 (p-1)/2개의 제곱 비잉여가 있다.

홀수 소수 p에 대하여, 두 집합
:\{1,2,\dots,(p-1)/2\}
:\{(p-1)/2+1,\dots,p-1\}
속 법 p에 대한 제곱 잉여의 수를 생각하자. 만약 p를 4로 나눈 나머지가 1이라면, 두 집합 속 법 p에 대한 제곱 잉여의 수는 같다. 이는 이 경우 −1이 제곱 잉여이므로, a와 p-a가 제곱 잉여인지 여부가 같기 때문이다. 만약 p를 4로 나눈 나머지가 3이라면, 첫째 집합 속 법 p에 대한 제곱 잉여의 수는 둘째 집합 속 법 p에 대한 제곱 잉여의 수보다 많다. 이는 유수 공식을 사용하여 증명할 수 있으며, 초등적인 증명은 알려져 있지 않다.

#### 오일러 기준
홀수 소수 p 및 이와 서로소인 정수 a에 대하여, 다음 세 조건이 서로 동치이다.
* a는 법 p에 대한 제곱 잉여이다.
* (오일러 기준, ) a^{(p-1)/2}\equiv1\pmod p
* 법 p에 대한 원시근 g가 주어졌을 때, a의 지표 \log_ga는 짝수이다.
반대로, 다음 세 조건이 서로 동치이다.
* a는 법 p에 대한 제곱 잉여가 아니다.
* (오일러 기준) a^{(p-1)/2}\equiv-1\pmod p
* 법 p에 대한 원시근 g가 주어졌을 때, a의 지표 \log_ga는 홀수이다.
오일러 기준은 제곱 잉여에 대한 판별을 단순 계산으로 귀결시키지만, 큰 수의 경우 많은 계산량을 요구하므로 실용적이지 않다.

#### 이차 상호 법칙
소수 p와 두 정수 a, b에 대하여, 다음이 성립한다.
* 만약 a와 b가 법 p에 대한 제곱 잉여라면, ab 역시 법 p에 대한 제곱 잉여이다.
* 만약 a와 p가 서로소이며, a가 법 p에 대한 제곱 잉여, b가 법 p에 대한 제곱 비잉여라면, ab는 법 p에 대한 제곱 비잉여이다.
* 만약 a와 b가 법 p에 대한 제곱 비잉여라면, ab는 법 p에 대한 제곱 잉여이다.
* 만약 a와 p가 서로소이며, a가 법 p에 대한 제곱 잉여라면, a의 법 p에 대한 곱셈 역원 역시 법 p에 대한 제곱 잉여이다.
* 만약 a와 p가 서로소이며, a가 법 p에 대한 제곱 비잉여라면, a의 법 p에 대한 곱셈 역원 역시 법 p에 대한 제곱 비잉여이다.
이는 정수가 소수에 대한 제곱 잉여인지 여부를 소수가 소수에 대한 제곱 잉여인지 여부로 귀결시킨다.

서로 다른 두 홀수 소수 p\ne q가 서로에 대한 제곱 잉여인지 여부에 대하여, 이차 상호 법칙이라고 부르는 대칭적인 관계가 성립한다.
* 만약 p\equiv1\pmod4이거나 q\equiv1\pmod4라면, p와 q가 서로에 대한 제곱 잉여인지 여부는 같다. 즉, 만약 p가 법 q에 대한 제곱 잉여라면 q도 법 p에 대한 제곱 잉여이며, 반대로 만약 p가 법 q에 대한 제곱 잉여가 아니라면 q도 법 p에 대한 제곱 잉여가 아니다.
* 만약 p\equiv q\equiv3\pmod4라면, p와 q가 서로에 대한 제곱 잉여인지 여부는 다르다. 즉, 만약 p가 법 q에 대한 제곱 잉여라면 q는 법 p에 대한 제곱 잉여가 아니며, 반대로 만약 p가 법 q에 대한 제곱 잉여가 아니라면 q는 법 p에 대한 제곱 잉여이다.

#### 슈어 추측
홀수 소수 p가 주어졌고,
:R(p)=\max\left\{n\in\mathbb Z^+|\exists m\in\mathbb Z\colon\left(\frac mp\right)=\left(\frac{m+1}p\right)=\cdots=\left(\frac{m+n-1}p\right)=1\right\}
:N(p)=\max\left\{n\in\mathbb Z^+|\exists m\in\mathbb Z\colon\left(\frac mp\right)=\left(\frac{m+1}p\right)=\cdots=\left(\frac{m+n-1}p\right)=-1\right\}
가 각각 법 p에 대한 연속된 제곱 잉여 및 제곱 비잉여의 최대 개수라고 하자. 그렇다면, 다음이 성립한다.
* 만약 p를 4로 나눈 나머지가 3이라면, R(p)=N(p)
* (슈어 추측, ) 만약 p\ne13이라면, N(p)
* N(p)=O(p^{1/4})

### 소수의 거듭제곱에 대한 제곱 잉여
홀수 소수 p 및 양의 정수 k에 대하여, \{0,1,2,\dots,p^k-1\} 속 p와 서로소인 정수들 가운데 절반은 법 p^k에 대한 제곱 잉여이며, 나머지 절반은 법 p^k에 대한 제곱 비잉여이다. 즉, p^{k-1}(p-1)/2개의 제곱 잉여와 p^{k-1}(p-1)/2개의 제곱 비잉여가 있다.

임의의 홀수 소수 p 및 양의 정수 k 및 p와 서로소인 정수 a에 대하여, 다음 두 조건이 서로 동치이다.
* a는 법 p^k에 대한 제곱 잉여이다.
* a는 법 p에 대한 제곱 잉여이다.
이는 헨젤 보조정리의 특수한 경우이다.

양의 정수 k와 홀수 a에 대하여, 다음 두 조건이 서로 동치이다.
* a는 법 2^k에 대한 제곱 잉여이다.
* 다음 세 조건 가운데 정확히 하나가 성립한다.
** k=1
** k=2이며, a\equiv1\pmod4
** k\ge3이며, a\equiv1\pmod8

소수 p 및 양의 정수 k 및 0이 아닌 정수 a가 주어졌다고 하자. 또한, a=p^ja'이며, a'와 p가 서로소라고 하자. 그렇다면, a가 법 p^k에 대한 제곱 잉여인지 여부는 다음과 같이 가릴 수 있다.
* 만약 j\ge k라면, a는 (p^k의 배수이므로) 법 p^k에 대한 제곱 잉여이다.
* 만약 j이며, j가 홀수라면, a는 법 p^k에 대한 제곱 비잉여이다.
* 만약 j이며, j가 짝수이며, a'이 법 p에 대한 제곱 잉여라면, a는 법 p^k에 대한 제곱 잉여이다.
* 만약 j이며, j가 짝수이며, a'이 법 p에 대한 제곱 비잉여라면, a는 법 p^k에 대한 제곱 비잉여이다.

소수 p와 양의 정수 k 및 법 p^k에 대한 제곱 잉여 a에 대하여, 합동 방정식
:x^2\equiv a\pmod{p^k}
의 해는 다음과 같다.
* 만약 p와 a가 서로소라면,
** 만약 p=2, k=1이라면, 해는 (법 2 아래) 유일하며, 다음과 같다.
**:x\equiv1\pmod2
** 만약 p\ne2이거나 p=k=2이며, \sqrt a\pmod{p^k}가 하나의 해라면, 전체 해는 (법 p^k 아래) 2개이며, 다음과 같다. x\equiv\sqrt a,p^k-\sqrt a\pmod{p^k}
** 만약 p=2이며 k\ge3이라면, \sqrt a\pmod{p^k}가 하나의 해라면, 전체 해는 (법 p^k 아래) 4개이며, 다음과 같다. x\equiv\sqrt a,p^k-\sqrt a,p^{k-1}+\sqrt a,p^{k-1}-\sqrt a\pmod{p^k}
* 만약 a가 p의 배수이며, p^k의 배수가 아니라면, a는 항상 a=p^{2l}a'의 꼴이다 (p와 a'은 서로소). 또한, x^2\equiv a\pmod{p^k}의 전체 해의 수는 (법 p^k 아래) x^2\equiv a'\pmod{p^{k-2l}}의 해의 수와 p^l의 곱이며, 다음과 같다. x\equiv p^l\sqrt{a'}+tp^{k-l}\pmod{p^k} 여기서 \sqrt{a'}\pmod{p^{k-2l}}는 x^2\equiv a'\pmod{p^{k-2l}}의 해이며, t=0,1,2,\dots,p^l-1이다.
* 만약 a가 p^k의 배수라면, x^2\equiv a\pmod{p^k}의 전체 해는 (법 p^k 아래) p^{k-\lfloor(k+1)/2\rfloor}개이며, 다음과 같다. x\equiv0,p^{\lfloor(k+1)/2\rfloor},2p^{\lfloor(k+1)/2\rfloor},\dots,(-1)p^{\lfloor(k+1)/2\rfloor}\pmod{p^k}

### 합성수에 대한 제곱 잉여
2 이상의 정수 n의 소인수 분해가
:n=p_1^{k_1}\cdots p_r^{k_r}
라고 하자. 그렇다면, 임의의 정수 a에 대하여, 다음 두 조건이 서로 동치이다.
* a는 법 n에 대한 제곱 잉여이다.
* 각 i=1,\dots,r에 대하여, a는 법 p_i^{r_i}에 대한 제곱 잉여이다.
또한, 합동 방정식
:x^2\equiv a\pmod n
의 해의 (법 n에 대한 합동을 감안한) 수는 합동 방정식
:x^2\equiv a\pmod{p_i^{r_i}}\qquad(i=1,\dots,r)
의 해의 (법 p_i^{r_i}에 대한 합동을 감안한) 수의 곱과 같다. 이는 중국인의 나머지 정리를 사용하여 보일 수 있다.

## 예
정수 a에 대하여, 다음 두 조건이 서로 동치이다.
* 임의의 2 이상의 정수 n에 대하여, a는 법 n에 대한 제곱 잉여이다.
* a는 어떤 정수의 제곱이다.
특히, 0과 1은 모든 법에 대한 제곱 잉여이며, 따라서 n의 배수 및 n으로 나눠 1이 남는 정수는 법 n에 대한 제곱 잉여이다.

### 제곱 잉여 −1
소수 p에 대하여, 다음 두 조건이 서로 동치이다.
* −1은 법 p에 대한 제곱 잉여이다.
* p=2이거나, p\equiv1\pmod4
보다 일반적으로, 2 이상의 정수 n에 대하여, 다음 두 조건이 서로 동치이다.
* −1은 법 n에 대한 제곱 잉여이다.
* n은 4의 배수가 아니며, n은 4로 나눈 나머지가 3인 소인수를 갖지 않는다.

### 제곱 잉여 2
소수 p에 대하여, 다음 두 조건이 서로 동치이다.
* 2는 법 p에 대한 제곱 잉여이다.
* p=2이거나, p\equiv1\pmod8이거나, p\equiv7\pmod8
보다 일반적으로, 2 이상의 정수 n에 대하여, 다음 두 조건이 서로 동치이다.
* 2는 법 n에 대한 제곱 잉여이다.
* n은 4의 배수가 아니며, n은 8로 나눈 나머지가 3이나 5인 소인수를 갖지 않는다.

### 제곱 잉여 3
소수 p에 대하여, 다음 두 조건이 서로 동치이다.
* 3은 법 p에 대한 제곱 잉여이다.
* p=2이거나, p\equiv 1\pmod{12}이거나, p\equiv11\pmod{12}
보다 일반적으로, 2 이상의 정수 n에 대하여, 다음 두 조건이 서로 동치이다.
* 3은 법 n에 대한 제곱 잉여이다.
* n은 4의 배수가 아니며, 9의 배수가 아니며, n은 12로 나눈 나머지가 5나 7인 소인수를 갖지 않는다.

### 표

## 역사
슈어 추측은 패트릭 험멜()이 증명하였다.

## 같이 보기
* 르장드르 기호

## 외부 링크
* 

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