제곱 잉여

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

정의

$n$이 2 이상의 정수이며, $a$가 임의의 정수라고 하자. 만약

$x^2\equiv a(\mathrm{mod}n)$

인 정수 $x$가 존재한다면, $a$를 법 $n$에 대한 제곱 잉여(영어: quadratic residue modulo $n$)라고 한다. 법 $n$에 대한 제곱 잉여가 아닌 정수를 법 $n$에 대한 제곱 비잉여(영어: quadratic nonresidue modulo $n$)라고 한다.

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

성질

만약 $a\equiv b(\mathrm{mod}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}\equiv 1(\mathrm{mod}p)$
• 법 $p$에 대한 원시근 $g$가 주어졌을 때, $a$의 지표 ${\log }_{g}a$는 짝수이다.

반대로, 다음 세 조건이 서로 동치이다.

• $a$는 법 $p$에 대한 제곱 잉여가 아니다.
• (오일러 기준) $a^{(p-1)/2}\equiv -1(\mathrm{mod}p)$
• 법 $p$에 대한 원시근 $g$가 주어졌을 때, $a$의 지표 ${\log }_{g}a$는 홀수이다.

오일러 기준은 제곱 잉여에 대한 판별을 단순 계산으로 귀결시키지만, 큰 수의 경우 많은 계산량을 요구하므로 실용적이지 않다.

이차 상호 법칙

소수 $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\equiv 1(\mathrm{mod}4)$이거나 $q\equiv 1(\mathrm{mod}4)$라면, $p$와 $q$가 서로에 대한 제곱 잉여인지 여부는 같다. 즉, 만약 $p$가 법 $q$에 대한 제곱 잉여라면 $q$도 법 $p$에 대한 제곱 잉여이며, 반대로 만약 $p$가 법 $q$에 대한 제곱 잉여가 아니라면 $q$도 법 $p$에 대한 제곱 잉여가 아니다.
• 만약 $p\equiv q\equiv 3(\mathrm{mod}4)$라면, $p$와 $q$가 서로에 대한 제곱 잉여인지 여부는 다르다. 즉, 만약 $p$가 법 $q$에 대한 제곱 잉여라면 $q$는 법 $p$에 대한 제곱 잉여가 아니며, 반대로 만약 $p$가 법 $q$에 대한 제곱 잉여가 아니라면 $q$는 법 $p$에 대한 제곱 잉여이다.

슈어 추측

홀수 소수 $p$가 주어졌고,

$R(p)=\max \{n\in {\mathbb{Z}}^{+}|\mathrm{\exists }m\in \mathbb{Z}:\left(\frac{m}{p}\right)=\left(\frac{m+1}{p}\right)=\cdots =\left(\frac{m+n-1}{p}\right)=1\}$

$N(p)=\max \{n\in {\mathbb{Z}}^{+}|\mathrm{\exists }m\in \mathbb{Z}:\left(\frac{m}{p}\right)=\left(\frac{m+1}{p}\right)=\cdots =\left(\frac{m+n-1}{p}\right)=-1\}$

가 각각 법 $p$에 대한 연속된 제곱 잉여 및 제곱 비잉여의 최대 개수라고 하자. 그렇다면, 다음이 성립한다.

• 만약 $p$를 4로 나눈 나머지가 3이라면, $R(p)=N(p)$
• (슈어 추측, 영어: Schur’s conjecture) 만약 $p\ne 13$이라면, $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\equiv 1(\mathrm{mod}4)$
  • $k\ge 3$이며, $a\equiv 1(\mathrm{mod}8)$

소수 $p$ 및 양의 정수 $k$ 및 0이 아닌 정수 $a$가 주어졌다고 하자. 또한, $a=p^j{a}^{\prime }$이며, $a^{\prime }$와 $p$가 서로소라고 하자. 그렇다면, $a$가 법 $p^k$에 대한 제곱 잉여인지 여부는 다음과 같이 가릴 수 있다.

• 만약 $j\ge k$라면, $a$는 ($p^k$의 배수이므로) 법 $p^k$에 대한 제곱 잉여이다.
• 만약 $j<k$이며, $j$가 홀수라면, $a$는 법 $p^k$에 대한 제곱 비잉여이다.
• 만약 $j<k$이며, $j$가 짝수이며, $a^{\prime }$이 법 $p$에 대한 제곱 잉여라면, $a$는 법 $p^k$에 대한 제곱 잉여이다.
• 만약 $j<k$이며, $j$가 짝수이며, $a^{\prime }$이 법 $p$에 대한 제곱 비잉여라면, $a$는 법 $p^k$에 대한 제곱 비잉여이다.

소수 $p$와 양의 정수 $k$ 및 법 $p^k$에 대한 제곱 잉여 $a$에 대하여, 합동 방정식

$x^2\equiv a(\mathrm{mod}{p}^k)$

의 해는 다음과 같다.

• 만약 $p$와 $a$가 서로소라면,
  • 만약 $p=2$, $k=1$이라면, 해는 (법 2 아래) 유일하며, 다음과 같다.

    $x\equiv 1(\mathrm{mod}2)$

  • 만약 $p\ne 2$이거나 $p=k=2$이며, $\sqrt{a}(\mathrm{mod}{p}^k)$가 하나의 해라면, 전체 해는 (법 $p^k$ 아래) 2개이며, 다음과 같다. $$x\equiv \sqrt{a},p^k-\sqrt{a}(\mathrm{mod}{p}^k)$$
  • 만약 $p=2$이며 $k\ge 3$이라면, $\sqrt{a}(\mathrm{mod}{p}^k)$가 하나의 해라면, 전체 해는 (법 $p^k$ 아래) 4개이며, 다음과 같다. $$x\equiv \sqrt{a},p^k-\sqrt{a},p^{k-1}+\sqrt{a},p^{k-1}-\sqrt{a}(\mathrm{mod}{p}^k)$$
• 만약 $a$가 $p$의 배수이며, $p^k$의 배수가 아니라면, $a$는 항상 $a=p^{2l}{a}^{\prime }$의 꼴이다 ($p$와 $a^{\prime }$은 서로소). 또한, $x^2\equiv a(\mathrm{mod}{p}^k)$의 전체 해의 수는 (법 $p^k$ 아래) $x^2\equiv a^{\prime }(\mathrm{mod}{p}^{k-2l})$의 해의 수와 $p^l$의 곱이며, 다음과 같다. $$x\equiv p^l\sqrt{a^{\prime }}+t{p}^{k-l}(\mathrm{mod}{p}^k)$$ 여기서 $\sqrt{a^{\prime }}(\mathrm{mod}{p}^{k-2l})$는 $x^2\equiv a^{\prime }(\mathrm{mod}{p}^{k-2l})$의 해이며, $t=0,1,2,\dots ,p^l-1$이다.
• 만약 $a$가 $p^k$의 배수라면, $x^2\equiv a(\mathrm{mod}{p}^k)$의 전체 해는 (법 $p^k$ 아래) $p^{k-\lfloor (k+1)/2\rfloor }$개이며, 다음과 같다. $$x\equiv 0,p^{\lfloor (k+1)/2\rfloor },2p^{\lfloor (k+1)/2\rfloor },\dots ,(-1)p^{\lfloor (k+1)/2\rfloor }(\mathrm{mod}{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(\mathrm{mod}n)$

의 해의 (법 $n$에 대한 합동을 감안한) 수는 합동 방정식

$x^2\equiv a(\mathrm{mod}{p}_i^{r_i})(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\equiv 1(\mathrm{mod}4)$

보다 일반적으로, 2 이상의 정수 $n$에 대하여, 다음 두 조건이 서로 동치이다.

• −1은 법 $n$에 대한 제곱 잉여이다.
• $n$은 4의 배수가 아니며, $n$은 4로 나눈 나머지가 3인 소인수를 갖지 않는다.

제곱 잉여 2

소수 $p$에 대하여, 다음 두 조건이 서로 동치이다.

• 2는 법 $p$에 대한 제곱 잉여이다.
• $p=2$이거나, $p\equiv 1(\mathrm{mod}8)$이거나, $p\equiv 7(\mathrm{mod}8)$

보다 일반적으로, 2 이상의 정수 $n$에 대하여, 다음 두 조건이 서로 동치이다.

• 2는 법 $n$에 대한 제곱 잉여이다.
• $n$은 4의 배수가 아니며, $n$은 8로 나눈 나머지가 3이나 5인 소인수를 갖지 않는다.

제곱 잉여 3

소수 $p$에 대하여, 다음 두 조건이 서로 동치이다.

• 3은 법 $p$에 대한 제곱 잉여이다.
• $p=2$이거나, $p\equiv 1(\mathrm{mod}12)$이거나, $p\equiv 11(\mathrm{mod}12)$

보다 일반적으로, 2 이상의 정수 $n$에 대하여, 다음 두 조건이 서로 동치이다.

• 3은 법 $n$에 대한 제곱 잉여이다.
• $n$은 4의 배수가 아니며, 9의 배수가 아니며, $n$은 12로 나눈 나머지가 5나 7인 소인수를 갖지 않는다.

표

제곱잉여

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
x2	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)이 증명하였다.

같이 보기

• 르장드르 기호

외부 링크

• Weisstein, Eric Wolfgang. “Quadratic residue” (영어). 《Wolfram MathWorld》. Wolfram Research.