제곱 잉여

수론에서, **제곱 잉여**(-剩餘, quadratic residue) 또는 **이차 잉여**(二次剩餘)는 어떤 정수의 제곱과 (주어진 법 아래) 합동인 정수이다. **제곱 비잉여**(-非剩餘, quadratic nonresidue) 또는 **이차 비잉여**(二次非剩餘)는 어떤 정수의 제곱과 (주어진 법 아래) 합동일 수 없는 정수이다.
# 정의
n이 2 이상의 정수이며, a가 임의의 정수라고 하자. 만약 :x^2\equiv a\pmod n 인 정수 x가 존재한다면, a를 **법 n에 대한 제곱 잉여**(quadratic residue modulo n)라고 한다. 법 n에 대한 제곱 잉여가 아닌 정수를 **법 n에 대한 제곱 비잉여**(quadratic nonresidue modulo n)라고 한다. 일부 저자는 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에 대한 제곱 잉여이다. * (오일러 기준, Euler's criterion) 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) * (슈어 추측, Schur’s conjecture) 만약 p\ne13이라면, N(p)<\sqrt 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인 소인수를 갖지 않는다.
## 표
{| class="wikitable" |+ 제곱잉여 |- ! *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*2 ! |1 ! |4 ! |9 ! |16 ! |25 ! |36 ! |49 ! |64 ! |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 |}
# 역사
슈어 추측은 패트릭 험멜(Patrick Hummel)이 증명하였다.