제곱 잉여

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

 정의 
이 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인 소인수를 갖지 않는다.

 표 
+ 제곱잉여 x  12 3 45 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 x2149162536496481100 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

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

 같이 보기 
 르장드르 기호

 외부 링크 


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