QuadraticResidues

자연수 세계 로 돌아가기

제곱꼴 나머지 (Quadratic Residues)

페르마 소정리는 '어떤 소수 p가 그것의 배수가 아닌 a 를 나눌 수 있는가, a 가 어떤 형태일 때 나눌 수 있는가'에 대한 일반적인 알고리듬을 보여준 중요한 첫발이다. 이로써 '나눌 수 있음'에 대한 엄청난 정보를 준 셈이다. 수학의 정리가 보통 그렇듯이 페르마 소정리도 완결적인 마침표가 아니다. 페르마 소정리가 열어둔 느낌표의 문을 따라 물음표의 탐험은 계속된다.

페르마 소정리와 비슷한 모양을 가진 수들을 몇 개 검토해보자.

$4^{11}\equiv _{23}1,\ 5^{11}\not \equiv _{23}1,\ 5^{11}\equiv _{23}-1$

이 사례들은, a를 꼭 'p-1번 곱해서 1 을 뺀 형태'일 때만 p 로 나누어진다라고는 할 수 없다는 새로운 사실을 살짝 드러내고 있다. 탐구를 더 해보자. 나눌 수 있음에 대한 더 많은 정보를 캐낼 수 있을 것이다.

제곱꼴 나머지의 정의

2 가 아닌 소수는 홀수라 2k+1 꼴이고 페르마 소정리에서 역할을 한 지수가 p-1 이었다. 따라서 페르마 소정리에서 2 가 아닌 소수 p 에 대하여 다시 생각해볼 수 있다.

소수 p 가 2 가 아니고, a 는 p 의 배수가 아니면, $a^{2k}-1\equiv _{p}0$

이다. 이렇게 되면 a 의 지수는 짝수 이므로,

$(a^{k}+1)(a^{k}-1)\equiv _{p}0$

로 바꿔쓸 수 있다. 모듈합동에서 다룬 기본 성질 7)에 따라

$a^{k}+1\equiv _{p}0$ 이거나 $a^{k}-1\equiv _{p}0$

이다. p-1 번 보다 훨씬 작은 횟수만큼 곱해서 1을 더하거나 빼도 p 로 나눌 수 있다는 기준을 거의 찾은 셈이다. a 가 어떨 때 $a^{k}+1\equiv _{p}0$ 이고, 어떨 때 $a^{k}-1\equiv _{p}0$ 일까? 라는 문제에 이른 것이다. (어떻게 될까? 멈추고 혼자 더 나아가보라.)

앞에서 페르마 소정리의 조건 부분에서 소수에 대한 조건을 더 엄격하게 했다. 유일한 짝수 소수인 2 를 빼고 생각해고 따라서 2k+1 = p 라고 가정했기 때문에, $a^{k}=a^{\frac {p-1}{2}}$ 이다. a 가 어떤 수 x 의 제곱꼴인 수와 p 로 나눈 나머지가 같으면, 다시 말해

$a\equiv _{p}x^{2}$

이라면,

$a^{\frac {p-1}{2}}\equiv _{p}x^{p-1}$ 이고 $x^{p-1}\equiv _{p}1$

앞부분의 비교 관계는 모듈합동의 성질에 따라 그리 되고, 뒷부분의 비교 관계는 x 는 여전히 p 의 배수가 아닐 것이므로, 페르마 소정리에 따른 것이다. 모듈합동이라는 비교 관계의 기본 성질은 transitive 하기 때문에 결론적으로, 다음과 같이 말할 수 있다.

a 가 어떤 수의 제곱꼴인 수와 홀수 소수 p 로 나눈 나머지가 같다면 $a^{\frac {p-1}{2}}-1$ 은 p 로 나뉠 수 있다

페르마 소정리로부터 새로운 비밀을 캐낸 것이다.

페르마 소정리를 오일러가 더 폭넓게 응용할 수 있는 형태로 일반화 하였듯이, 여기서도 기왕에 'a 가 어떤 수의 제곱꼴인 수와 홀수 소수 p 로 나눈 나머지가 같다면' 부분을 일반화 해보자.

정의 (제곱꼴 나머지)  : a 와 n 이 서로소이고, '제곱꼴인 어떤 수 x 와 a 가 주어진 수 n 에 대해 모듈합동'이면 그때의 a 를 'n 의 제곱꼴 나머지' 라고 부른다. 그렇지 않으면 제곱꼴 非나머지라 한다.

이 식을 기호로 표현할 수 있다.

$\forall a,n((a,n)=1\ \land \ \exists x(a\equiv _{n}x^{2}))$ 이면 a 는 n 의 제곱꼴 나머지고 그렇지 않으면 非나머지다.

위의 식은 주어진 a, n 에 대하여 x 를 찾는 방정식의 해를 찾는 문제로 된다. 이는 '방정식'을 주요 대상으로하는 대수학으로 연구가 이어지게 될 것이라는 것을 짐작할 수 있다. 모듈합동에서 우리에게 익숙한 같음 관계( = )가 주요 역할을 하는 보통의 산술에서 모듈 합동 관계 ($\equiv$ ) 가 중요한 역할을 하는 'Modulo Arithmetic'으로 수학의 지평이 넓혀졌다는 이야기를 했다. 여기서는 마침내 'modulo 합동 관계를 성립하는 방정식'의 개념이 중요한 역할을 하는 Modulo Algebra 라 부를 수 있는 영역으로 빛이 들고 있다는 것을 볼 수 있다. 제곱꼴에서 더 일반화하여 세제곱꼴, 네제곱꼴인 modulo 방정식의 해들은 어떤 성질을 가질지 끝없이 물음표를 던져갈 수 있다. (위의 식을 일반화 하면서, 스스로 어느 정도 이를 발전시켜보라. ('p의 제곱꼴 非나머지' 라는 용어를 우리말로 어떻게 하는게 좋을까???)

이제 특수한 성질을 갖는 수의 범주를 정의했으니 그것들은 도대체 어떻게 생겼고 살아가는지 들여다볼 차례다.

제곱꼴 나머지의 성질

p 보다 작은 p 의 제곱꼴 나머지의 개수

제곱꼴 나머지에 대해 익숙해지기 위해 예를 두 개만 들어보자.

(예) 7 의 제곱꼴 나머지 : 7 보다 작은 수들 중 7 의 제곱꼴 나머지.

$1^{2}\equiv 6^{2}\equiv 1\qquad ({\rm {mod}}\ 7)$

$2^{2}\equiv 5^{2}\equiv 4\qquad ({\rm {mod}}\ 7)$

$3^{2}\equiv 4^{2}\equiv 2\qquad ({\rm {mod}}\ 7)$

이므로, 7 보다 작은 수 중, 7 의 제곱꼴 나머지들은 1, 4, 2 이다. 그리고 2, 3, 6 은 제곱꼴 非나머지다.

(예) 11 의 제곱꼴 나머지 : 11 보다 작은 수 중에서 11 의 제곱꼴 나머지.

$1^{2}\equiv 10^{2}\equiv 1\qquad ({\rm {mod}}\ 11)$

$2^{2}\equiv 9^{2}\equiv 4\qquad ({\rm {mod}}\ 11)$

$3^{2}\equiv 8^{2}\equiv 9\qquad ({\rm {mod}}\ 11)$

$4^{2}\equiv 7^{2}\equiv 5\qquad ({\rm {mod}}\ 11)$

$5^{2}\equiv 6^{2}\equiv 3\qquad ({\rm {mod}}\ 11)$

이므로, 11보다 작은 수 중, 11의 제곱꼴 나머지들은 1, 4, 9, 5, 3 이다. 그리고 2, 6, 7, 8, 10 은 제곱꼴 非나머지다.

앞의 예에서 다음 성질을 유추해볼 수 있다. (스스로 증명해보시오.)

p 가 홀수인 소수고 a 가 p 의 배수가 아니라면, 1 부터 p-1 사이에는 정확히 ${\frac {p-1}{2}}$ 개 제곱꼴 나머지와 ${\frac {p-1}{2}}$ 개 非나머지가 있다.

a 가 p 의 제곱꼴 나머지이면 $a^{\frac {p-1}{2}}\equiv _{p}1$

a 가 p 의 제곱꼴 非나머지이면 $a^{\frac {p-1}{2}}\equiv _{p}-1$

가우스의 황금 정리

수론에서 매우 중요한 기초가 되는 법칙에 대하여 정리만 알아보자. 이 정리를 구체적으로 언급한 사람은 르장드르 였다. 그리고 젊은 가우스가 이를 시간을 많이 들여 최초로 엄격하게 증명했다. 가우스는 이를 '제곱꼴 상호관계의 법칙(The law of quadratic reciprocity)'라 이름을 붙이고 '황금 정리'(golden theorem)'이라 별명을 부르며 증명한 것에 대하여 대단한 자부심을 가졌던 것으로 알려져있다. 그 이후로도 오늘날까지 수백개의 증명이 등장하고 있다. 가우스만 하더라도 살아있을 때 8개의 다른 증명을 했다고 한다. 충분히 쉬운 것은 아직 발견되지 않았다.

가우스의 Golden Theorem  : 2가 아닌 서로 다른 두 소수 p, q에 대하여

• p, q가 둘 중 하나라도 4n+1 꼴인 경우 : q 가 p 의 제곱꼴 나머지이면 p 가 q 의 제곱꼴 나머지 이고 그 역도 참이다.
• p, q가 모두 4n+3 꼴인 경우 : q 가 p 의 제곱꼴 非나머지면 p가 q의 제곱꼴 나머지 이고 그 역도 참이다.

위의 정리를 모듈 산술과 모듈 방정식의 용어로 다시 쓰면

• p, q가 둘 중 하나라도 4n+1 꼴인 경우 : $x^{2}\equiv p\ ({\rm {mod}}\ q)$ 해가 있으면 $x^{2}\equiv q\ ({\rm {mod}}\ p)$ 도 해가 있다. 그 역도 참이다.
• p, q가 모두 4n+3 꼴인 경우 : $x^{2}\equiv p\ ({\rm {mod}}\ q)$ 해가 있으면 $x^{2}\equiv q\ ({\rm {mod}}\ p)$ 는 해가 없다. 그 역도 참이다.

또는 논리적으로 같은 내용이 되는 다른 표현은

• p, q가 둘 중 하나라도 4n+1 꼴인 경우 : q 가 p 의 제곱꼴 나머지이고 p 가 q 의 제곱꼴 나머지이거나, q 가 p 의 제곱꼴 非나머지고 p 가 q 의 제곱꼴 非나머지다.
• p, q가 모두 4n+3 꼴인 경우 : q 가 p 의 제곱꼴 非나머지고 p가 q의 제곱꼴 나머지 거나, 이고 q 가 p 의 제곱꼴 나머지고 p가 q의 제곱꼴 非나머지이다.

또는 이렇게도 표현할 수 있다.

Note

Math : Math글쓰기 | Math번역 | MathBoard | Math&Culture | MathMoim
OnLineMathCenter | MathCamp | SoftMathJournal | MathBook | CyberAcademia | Academia