제곱 잉여

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

정의

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

${\displaystyle x^{2}\equiv a{\pmod {n}}}$

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

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

성질

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

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

소수에 대한 제곱 잉여

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

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

홀수 소수 ${\displaystyle p}$에 대하여, 두 집합

${\displaystyle \{1,2,\dots ,(p-1)/2\}}$

${\displaystyle \{(p-1)/2+1,\dots ,p-1\}}$

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

오일러 기준

홀수 소수 ${\displaystyle p}$ 및 이와 서로소인 정수 ${\displaystyle a}$에 대하여, 다음 세 조건이 서로 동치이다.

• ${\displaystyle a}$는 법 ${\displaystyle p}$에 대한 제곱 잉여이다.
• (오일러 기준, 영어: Euler's criterion) ${\displaystyle a^{(p-1)/2}\equiv 1{\pmod {p}}}$
• 법 ${\displaystyle p}$에 대한 원시근 ${\displaystyle g}$가 주어졌을 때, ${\displaystyle a}$의 지표 ${\displaystyle \log _{g}a}$는 짝수이다.

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

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

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

이차 상호 법칙

소수 ${\displaystyle p}$와 두 정수 ${\displaystyle a}$, ${\displaystyle b}$에 대하여, 다음이 성립한다.

• 만약 ${\displaystyle a}$와 ${\displaystyle b}$가 법 ${\displaystyle p}$에 대한 제곱 잉여라면, ${\displaystyle ab}$ 역시 법 ${\displaystyle p}$에 대한 제곱 잉여이다.
• 만약 ${\displaystyle a}$와 ${\displaystyle p}$가 서로소이며, ${\displaystyle a}$가 법 ${\displaystyle p}$에 대한 제곱 잉여, ${\displaystyle b}$가 법 ${\displaystyle p}$에 대한 제곱 비잉여라면, ${\displaystyle ab}$는 법 ${\displaystyle p}$에 대한 제곱 비잉여이다.
• 만약 ${\displaystyle a}$와 ${\displaystyle b}$가 법 ${\displaystyle p}$에 대한 제곱 비잉여라면, ${\displaystyle ab}$는 법 ${\displaystyle p}$에 대한 제곱 잉여이다.
• 만약 ${\displaystyle a}$와 ${\displaystyle p}$가 서로소이며, ${\displaystyle a}$가 법 ${\displaystyle p}$에 대한 제곱 잉여라면, ${\displaystyle a}$의 법 ${\displaystyle p}$에 대한 곱셈 역원 역시 법 ${\displaystyle p}$에 대한 제곱 잉여이다.
• 만약 ${\displaystyle a}$와 ${\displaystyle p}$가 서로소이며, ${\displaystyle a}$가 법 ${\displaystyle p}$에 대한 제곱 비잉여라면, ${\displaystyle a}$의 법 ${\displaystyle p}$에 대한 곱셈 역원 역시 법 ${\displaystyle p}$에 대한 제곱 비잉여이다.

이는 정수가 소수에 대한 제곱 잉여인지 여부를 소수가 소수에 대한 제곱 잉여인지 여부로 귀결시킨다.

서로 다른 두 홀수 소수 ${\displaystyle p\neq q}$가 서로에 대한 제곱 잉여인지 여부에 대하여, 이차 상호 법칙이라고 부르는 대칭적인 관계가 성립한다.

• 만약 ${\displaystyle p\equiv 1{\pmod {4}}}$이거나 ${\displaystyle q\equiv 1{\pmod {4}}}$라면, ${\displaystyle p}$와 ${\displaystyle q}$가 서로에 대한 제곱 잉여인지 여부는 같다. 즉, 만약 ${\displaystyle p}$가 법 ${\displaystyle q}$에 대한 제곱 잉여라면 ${\displaystyle q}$도 법 ${\displaystyle p}$에 대한 제곱 잉여이며, 반대로 만약 ${\displaystyle p}$가 법 ${\displaystyle q}$에 대한 제곱 잉여가 아니라면 ${\displaystyle q}$도 법 ${\displaystyle p}$에 대한 제곱 잉여가 아니다.
• 만약 ${\displaystyle p\equiv q\equiv 3{\pmod {4}}}$라면, ${\displaystyle p}$와 ${\displaystyle q}$가 서로에 대한 제곱 잉여인지 여부는 다르다. 즉, 만약 ${\displaystyle p}$가 법 ${\displaystyle q}$에 대한 제곱 잉여라면 ${\displaystyle q}$는 법 ${\displaystyle p}$에 대한 제곱 잉여가 아니며, 반대로 만약 ${\displaystyle p}$가 법 ${\displaystyle q}$에 대한 제곱 잉여가 아니라면 ${\displaystyle q}$는 법 ${\displaystyle p}$에 대한 제곱 잉여이다.

슈어 추측

홀수 소수 ${\displaystyle p}$가 주어졌고,

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

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

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

• 만약 ${\displaystyle p}$를 4로 나눈 나머지가 3이라면, ${\displaystyle R(p)=N(p)}$
• (슈어 추측, 영어: Schur’s conjecture) 만약 ${\displaystyle p\neq 13}$이라면, ${\displaystyle N(p)<{\sqrt {p}}}$
• ${\displaystyle N(p)=O(p^{1/4})}$

소수의 거듭제곱에 대한 제곱 잉여

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

임의의 홀수 소수 ${\displaystyle p}$ 및 양의 정수 ${\displaystyle k}$ 및 ${\displaystyle p}$와 서로소인 정수 ${\displaystyle a}$에 대하여, 다음 두 조건이 서로 동치이다.

• ${\displaystyle a}$는 법 ${\displaystyle p^{k}}$에 대한 제곱 잉여이다.
• ${\displaystyle a}$는 법 ${\displaystyle p}$에 대한 제곱 잉여이다.

이는 헨젤 보조정리의 특수한 경우이다.

양의 정수 ${\displaystyle k}$와 홀수 ${\displaystyle a}$에 대하여, 다음 두 조건이 서로 동치이다.

• ${\displaystyle a}$는 법 ${\displaystyle 2^{k}}$에 대한 제곱 잉여이다.
• 다음 세 조건 가운데 정확히 하나가 성립한다.
  • ${\displaystyle k=1}$
  • ${\displaystyle k=2}$이며, ${\displaystyle a\equiv 1{\pmod {4}}}$
  • ${\displaystyle k\geq 3}$이며, ${\displaystyle a\equiv 1{\pmod {8}}}$

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

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

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

${\displaystyle x^{2}\equiv a{\pmod {p^{k}}}}$

의 해는 다음과 같다.

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

    ${\displaystyle x\equiv 1{\pmod {2}}}$

  • 만약 ${\displaystyle p\neq 2}$이거나 ${\displaystyle p=k=2}$이며, ${\displaystyle {\sqrt {a}}{\pmod {p^{k}}}}$가 하나의 해라면, 전체 해는 (법 ${\displaystyle p^{k}}$ 아래) 2개이며, 다음과 같다. $${\displaystyle x\equiv {\sqrt {a}},p^{k}-{\sqrt {a}}{\pmod {p^{k}}}}$$
  • 만약 ${\displaystyle p=2}$이며 ${\displaystyle k\geq 3}$이라면, ${\displaystyle {\sqrt {a}}{\pmod {p^{k}}}}$가 하나의 해라면, 전체 해는 (법 ${\displaystyle p^{k}}$ 아래) 4개이며, 다음과 같다. $${\displaystyle x\equiv {\sqrt {a}},p^{k}-{\sqrt {a}},p^{k-1}+{\sqrt {a}},p^{k-1}-{\sqrt {a}}{\pmod {p^{k}}}}$$
• 만약 ${\displaystyle a}$가 ${\displaystyle p}$의 배수이며, ${\displaystyle p^{k}}$의 배수가 아니라면, ${\displaystyle a}$는 항상 ${\displaystyle a=p^{2l}a'}$의 꼴이다 (${\displaystyle p}$와 ${\displaystyle a'}$은 서로소). 또한, ${\displaystyle x^{2}\equiv a{\pmod {p^{k}}}}$의 전체 해의 수는 (법 ${\displaystyle p^{k}}$ 아래) ${\displaystyle x^{2}\equiv a'{\pmod {p^{k-2l}}}}$의 해의 수와 ${\displaystyle p^{l}}$의 곱이며, 다음과 같다. $${\displaystyle x\equiv p^{l}{\sqrt {a'}}+tp^{k-l}{\pmod {p^{k}}}}$$ 여기서 ${\displaystyle {\sqrt {a'}}{\pmod {p^{k-2l}}}}$는 ${\displaystyle x^{2}\equiv a'{\pmod {p^{k-2l}}}}$의 해이며, ${\displaystyle t=0,1,2,\dots ,p^{l}-1}$이다.
• 만약 ${\displaystyle a}$가 ${\displaystyle p^{k}}$의 배수라면, ${\displaystyle x^{2}\equiv a{\pmod {p^{k}}}}$의 전체 해는 (법 ${\displaystyle p^{k}}$ 아래) ${\displaystyle p^{k-\lfloor (k+1)/2\rfloor }}$개이며, 다음과 같다. $${\displaystyle x\equiv 0,p^{\lfloor (k+1)/2\rfloor },2p^{\lfloor (k+1)/2\rfloor },\dots ,(-1)p^{\lfloor (k+1)/2\rfloor }{\pmod {p^{k}}}}$$

합성수에 대한 제곱 잉여

2 이상의 정수 ${\displaystyle n}$의 소인수 분해가

${\displaystyle n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}}$

라고 하자. 그렇다면, 임의의 정수 ${\displaystyle a}$에 대하여, 다음 두 조건이 서로 동치이다.

• ${\displaystyle a}$는 법 ${\displaystyle n}$에 대한 제곱 잉여이다.
• 각 ${\displaystyle i=1,\dots ,r}$에 대하여, ${\displaystyle a}$는 법 ${\displaystyle p_{i}^{r_{i}}}$에 대한 제곱 잉여이다.

또한, 합동 방정식

${\displaystyle x^{2}\equiv a{\pmod {n}}}$

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

${\displaystyle x^{2}\equiv a{\pmod {p_{i}^{r_{i}}}}\qquad (i=1,\dots ,r)}$

의 해의 (법 ${\displaystyle p_{i}^{r_{i}}}$에 대한 합동을 감안한) 수의 곱과 같다. 이는 중국인의 나머지 정리를 사용하여 보일 수 있다.

예

정수 ${\displaystyle a}$에 대하여, 다음 두 조건이 서로 동치이다.

• 임의의 2 이상의 정수 ${\displaystyle n}$에 대하여, ${\displaystyle a}$는 법 ${\displaystyle n}$에 대한 제곱 잉여이다.
• ${\displaystyle a}$는 어떤 정수의 제곱이다.

특히, 0과 1은 모든 법에 대한 제곱 잉여이며, 따라서 ${\displaystyle n}$의 배수 및 ${\displaystyle n}$으로 나눠 1이 남는 정수는 법 ${\displaystyle n}$에 대한 제곱 잉여이다.

제곱 잉여 −1

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

• −1은 법 ${\displaystyle p}$에 대한 제곱 잉여이다.
• ${\displaystyle p=2}$이거나, ${\displaystyle p\equiv 1{\pmod {4}}}$

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

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

제곱 잉여 2

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

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

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

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

제곱 잉여 3

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

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

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

• 3은 법 ${\displaystyle n}$에 대한 제곱 잉여이다.
• ${\displaystyle n}$은 4의 배수가 아니며, 9의 배수가 아니며, ${\displaystyle 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.