제곱 잉여

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

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

인 정수 가 존재한다면, 를 법 에 대한 제곱 잉여()라고 한다. 법 에 대한 제곱 잉여가 아닌 정수를 법 에 대한 제곱 비잉여()라고 한다.

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

 성질 
만약 이라면, 와 가 법 에 대한 제곱 잉여인지 여부는 같다. 따라서, 주어진 법 에 대한 제곱 잉여를 다룰 때, 속 법 에 대한 제곱 잉여에 집중하여도 충분하다.

만약 이 짝수라면, 속 법 에 대한 제곱 잉여는 개 이하이다. 만약 이 홀수라면, 속 법 에 대한 제곱 잉여는 개 이하이다.

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

홀수 소수 에 대하여, 가운데 절반은 법 에 대한 제곱 잉여이며, 나머지 절반은 법 에 대한 제곱 비잉여이다. 즉, 개의 제곱 잉여와 개의 제곱 비잉여가 있다.

홀수 소수 에 대하여, 두 집합

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

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

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

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

 슈어 추측 
홀수 소수 가 주어졌고,

가 각각 법 에 대한 연속된 제곱 잉여 및 제곱 비잉여의 최대 개수라고 하자. 그렇다면, 다음이 성립한다.
 만약 를 4로 나눈 나머지가 3이라면, 
 (슈어 추측, ) 만약 이라면, 
 

 소수의 거듭제곱에 대한 제곱 잉여 
홀수 소수 및 양의 정수 에 대하여, 속 와 서로소인 정수들 가운데 절반은 법 에 대한 제곱 잉여이며, 나머지 절반은 법 에 대한 제곱 비잉여이다. 즉, 개의 제곱 잉여와 개의 제곱 비잉여가 있다.

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

양의 정수 와 홀수 에 대하여, 다음 두 조건이 서로 동치이다.
 는 법 에 대한 제곱 잉여이다.
 다음 세 조건 가운데 정확히 하나가 성립한다.
 
 이며, 
 이며, 

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

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

의 해는 다음과 같다.
 만약 와 가 서로소라면,
 만약 , 이라면, 해는 (법 2 아래) 유일하며, 다음과 같다.

 만약 이거나 이며, 가 하나의 해라면, 전체 해는 (법 아래) 2개이며, 다음과 같다. 
 만약 이며 이라면, 가 하나의 해라면, 전체 해는 (법 아래) 4개이며, 다음과 같다. 
 만약 가 의 배수이며, 의 배수가 아니라면, 는 항상 의 꼴이다 (와 은 서로소). 또한, 의 전체 해의 수는 (법 아래) 의 해의 수와 의 곱이며, 다음과 같다. 여기서 는 의 해이며, 이다.
 만약 가 의 배수라면, 의 전체 해는 (법 아래) 개이며, 다음과 같다. 

 합성수에 대한 제곱 잉여 
2 이상의 정수 의 소인수 분해가

라고 하자. 그렇다면, 임의의 정수 에 대하여, 다음 두 조건이 서로 동치이다.
 는 법 에 대한 제곱 잉여이다.
 각 에 대하여, 는 법 에 대한 제곱 잉여이다.
또한, 합동 방정식

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

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

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

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

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

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

 표 

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

 같이 보기 
 르장드르 기호

 외부 링크 
 

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