이차잉여란? 가 의 이차잉여라는 것은, 제곱을 으로 나눈 나머지가 가 되도록 하는 정수가 존재한다는 것이다.
즉, 인 정수 가 존재하면, 가 의 이차잉여 (제곱잉여, quadratic residue) 라는 의미이다.
이차잉여라는 말이 존재한다는 것은, 곧 이차 비잉여도 존재한다는 뜻이다. 모든 자연수가 어느 제곱수와 에서 합동이 된다면, 굳이 이차 잉여라는 말이 존재하지 않았을 것이다.
예상한 것과 동일한 맥락에서 다음과 같이 이차 비잉여도 정의할 수 있다.
즉, 인 정수 가 존재하지 않으면, 는 의 이차비잉여 (제곱비잉여, quadratic nonresidue) 라는 의미이다.
앞서 이야기한 잉여계의 이론과 합치면, 자연스럽게 이차잉여계를 떠올릴 수 있다. 예상과 같이 에 대해 인 정수 가 존재하는 의 집합을 의 이차잉여계(quadratic residues modulo ) 라 한다.
가장 쉬운 modulo 2에서의 이차잉여를 구해보자. mod 2에서는 모든 정수들이 홀짝으로만 분류되기 때문에 이차잉여가 0과 1 뿐이다.
이 의 완전 잉여계이면서 이차잉여계라고 할 수 있다.
잉여계 개념은 쉽고. 정수 의 제곱 이 로 나뉘었을 때 특정 나머지값만 나온다면, 이는 동일 이차잉여계에 속함.
‘잉여’라는 단어는 ‘나머지’를 의미한다. 고로 ‘나머지’를 모은 것이 ‘잉여계’가 된다. 더 정확히 설명하자면, 1 1보다 큰 자연수 에 대해 을 모은 집합은 n의 최소 양의 잉여계(least nonnegative residues modulo ) 이다.
modulo 3을 고려하기 시작할 때 고려해야할 대상은 0,1,2 뿐.
0,1은 자명하고, 2의 경우 . 이는 가 의 이차비잉여라는 것으로 서술될 수 있음.
2는 3의 이차비잉여. 로 만드는 정수 가 존재하지 않는다.
1는 3의 이차비잉여. 로 만드는 정수 가 존재한다.
잉여계라는 것은 결국 자기보다 작은 숫자들을 나누었을 때 나머지로 등장할 수 있는 숫자들의 리스트.
이차잉여의 주체여부를 판단하고자 하는 정수 를 제곱한 후, 이걸 객체여부가 되는 숫자 으로 나누었을 때의 나머지 리스트가 이차잉여계에 속함.
여기 안속하면 이차잉여계에 안속함. 이차비잉여.
이차잉여계의 후보군은 이하의 모든 숫자. 여기서 실제로 제곱해보고 나눈 후에 이차잉여, 이차비잉여를 체크하면 됨.