정수론의 꽃 이차상호법칙에 대해 아라보자.

오랜만에 궤령부에 수학글을 하나 올려보고 싶은데, 뭐가 좋을까 고민하다가 이차상호법칙이 떠올랐어.

아마 익숙하지 않은 이름이겠지만, 페러데이의 법칙, 상대성 이론만큼이나 정수론의 역사에서는 중요한 발견이지. 오늘은 한번 그 법칙을 소개해볼까 해.

1. 합동연산

우리가 시간을 더하거나 뺄 때, 예컨대 9시에서 5시간 뒤라고 하면, 14시라고도 하지만 2시라고도 해. 왜냐하면 12시는 곧 0시나 마찬가지거든. 이렇게 12를 0으로 취급하는 방식의 연산을 합동연산이라고 해.

그런데 꼭 12를 0으로 칠 필요는 없어. 원한다면 3을 0으로, 4를 0으로 칠 수도 있지. 

예를 들어, 5를 0으로 치는 연산에서 4 x 3를 계산한다고 해볼까?

일반적으로 4 x 3 은 12야. 하지만 5를 0과 같은 것으로 쳐주기로 했으니, 12는 7과 같은 것이고, 7은 2와 같은 것이 돼. 즉 4 x 3은 2인 셈이지. 이를 수학자들은 4 x 3 ≡ 2 (mod 5)라고 표기해. 4 x 3은 12지만, 5를 0으로 취급하는 합동연산에서 이는 2와 같다 라는 뜻이지.

5를 0과 같다고 취급하는 것은 -1을 4와 같다고 취급하는 것과 같아. 0에서 1을 빼면 -1, 5에서 1을 빼면 4니까. 마찬가지로 3도 -2와 같은 것이 돼. 그래서 4 x 3은 (-1) x (-2)와 같고, 실제로 이를 계산해보면 역시 2가 나오지.

또 다른 예를 한번 들어볼까? 7을 0과 같다고 여기고 3 x 4 + 2를 계산해보자고 하자.

먼저 3 x 4는 12이고, 여기에 2를 더하면 14가 돼. 7을 0과 같다고 여겼으니, 14는 7과 같고, 그 7은 0과 같아. 그래서 3 x 4 + 2 ≡ 0 (mod 7)인 것이지.

2. 제곱잉여

이제부터는 mod n에 n이 소수인 경우만 생각해볼거야. 예컨대 n을 3이라고 둬볼까? mod 3에서는 제곱으로 나올 수 있는 수들로는 무엇이 있을까?

먼저 0의 제곱은 0이야. 1의 제곱도 1이고. 2의 제곱은 4야. 하지만 우리는 mod 3, 즉 3을 0과 같은 것으로 취급하기로 했으니까 4는 1과 같아. 즉, 2의 제곱은 mod 3에서는 1인 거야. 요약하자면,
0^2 ≡ 0 (mod 3)
1^2 ≡ 1 (mod 3)
2^2 ≡ 1 (mod 3)
이라고 표기할 수 있어. 보다시피 mod 3에서 제곱해서 나올 수 있는 수로는 0을 제외하곤 1밖에 없어.

왜 0, 1, 2만 계산하냐고? 물론 3, 4, 5, ... 의 제곱들도 계산할 수 있어. 하지만 3은 곧 0과 같은 것이니 3의 제곱을 계산하는 것은 0의 제곱을 계산하는 것과 같아. 그리고 이는 우리가 이미 구했지. 마찬가지로 4의 제곱을 계산하는 것도 1의 제곱을 계산하는 것과 같아. 5의 제곱은 2의 제곱과 같지. 그래서 0, 1, 2만 계산해도 충분한 거야.

소수에서만 해보기로 했으니 이번엔 mod 5에서 계산해볼까? 직접 연필을 쥐고 계산해보면 다음의 결과들을 구할 수 있어.
0^2 ≡ 0 (mod 5)
1^2 ≡ 1 (mod 5)
2^2 ≡ 4 (mod 5)
3^2 ≡ 4 (mod 5)
4^2 ≡ 1 (mod 5)
mod 5에서 제곱해서 나올 수 있는 수로는 0을 제외하곤 1과 4밖에 없지.

이처럼 p를 소수라 할 때 (mod p)에서 0이 아닌 제곱해서 나올 수 있는 수를 제곱잉여라고 해. (mod 5)에서의 제곱잉여는 1과 4, (mod 3)에서의 제곱잉여는 1밖에 없지.

mod 7, mod 11, mod 13 등 작은 소수에 대해서 제곱 잉여를 구하다보면 다음의 성질들을 깨닫게 돼.
 

1. mod p의 제곱 잉여의 개수는 항상 (p-1)/2이다. (mod 3의 제곱잉여는 (3-1)/2=1개, mod 5의 제곱잉여는 (5-1)/2 = 2개)
2. 1은 항상 제곱 잉여이다. (당연하지! 1의 제곱은 1이니까)
그런데 이런 눈에 보이는 당연한 성질 말고 정말 놀라운 성질이 하나 더 있어. 그게 바로 이차상호법칙이야.

3. 이차상호법칙

p와 q를 홀수인 소수라고 하자. p는 (mod q)의 제곱잉여일까? 반대로 q는 (mod p)의 제곱잉여일까?

사실 이 두 질문에 대해 곰곰히 생각해보면 서로 관련이 전혀 없어 보이는 것이 정상이야.

mod q는 q를 0으로 취급하는 연산이고, mod p는 p를 0으로 취급하는 연산이잖아. 애초에 다른 계산 방식을 갖고 있는 별개의 세상인데 이 둘 사이에 연관성이 있으리라 기대하긴 어렵지.

하지만 이차상호법칙은 놀랍게도 둘 사이에 연관성이 있다는 사실을 밝혀냈어.
 

제 1법칙: p ≡ 1 (mod 4)거나 q ≡ 1 (mod 4)라면, p가 (mod q)에서 제곱잉여면, q는 (mod p)에서 제곱잉여고, p가 (mod q)에서 제곱잉여가 아니라면, q는 (mod p)에서 제곱잉여가 아니다.
 

제 2법칙: p ≡ 3 (mod 4)이고 q ≡ 3 (mod 4)라면, p가 (mod q)에서 제곱잉여면, q는 (mod p)에서 제곱잉여가 아니고, p가 (mod q)에서 제곱잉여가 아니라면, q는 (mod p)에서 제곱잉여이다.

복잡하니까 예를 들어서 하나하나 살펴보자.

Case 1: p = 3, q = 5.
3는 mod 4, 즉 4를 0으로 여기는 세상에서 3과 같아. 당연하지. 3은 이미 4보다 작으니까 수를 더 빼줄 필요가 없어. 하지만 5는 mod 4에서 1과 같아. 5에서 4를 빼면 1이 되니까.

즉, p = 3과 q = 5라면, 이차상호법칙의 제 1법칙의 조건에 부합해. p 와 q 중 적어도 하나가 (mod 4)에서 1이니까.

이번엔 둘의 제곱잉여 여부를 구해보자. 앞서 계산했듯, mod 5에서 제곱잉여는 1과 4야. 즉 3은 mod 5에서 제곱잉여가 아니지. mod 3에서는 제곱잉여가 1이었어. 5는 mod 3에서 2와 같은데, 2는 mod 3에서 제곱잉여가 아니었어. 즉, 3은 (mod 5)에서, 5는 (mod 3)에서 제곱잉여가 아닌 셈이지.

보다시피 3은 mod 5에서 제곱잉여가 아니고, 마찬가지로 5도 mod 3에서 제곱잉여가 아니지. 둘의 결과가 같은 이유는 3과 5 중 적어도 하나가 mod 4에서 1이기 때문이야.

Case 2: p = 5, q = 11

여기선 5 ≡ 1 (mod 4)이므로, p와 q 중 적어도 하나가 (mod 4)에서 1이야. 즉 제 1법칙을 사용해줘야하지.

먼저 11이 mod 5에서 제곱잉여인지 확인해볼까? 11은 mod 5에서 1과 같고, 1은 항상 제곱잉여라 했어. 즉 11은 mod 5에서 제곱잉여지.

그렇다면 이차상호법칙에 의해 5도 mod 11에서 제곱잉여라는 사실을 유추할 수 있어. 실제로 계산해보면 

4^2 = 16 ≡ 5 (mod 11), 즉 5는 (mod 11)에서 제곱잉여야. 

11이 (mod 5)에서 제곱잉여이면서 동시에 5가 (mod 11)에서 제곱잉여였어. 둘의 결과가 같은 이유는 5와 11 중 적어도 하나가 mod 4에서 1이기 때문이야.

Case 3: p = 3, q = 7

이번엔 p와 q 둘 다 둘 다 (mod 4)에서 3이야. 제 2법칙의 조건에 부합하지.

7은 (mod 3)에서 제곱잉여일까? 7은 (mod 3)에서 1과 같고, 1은 항상 제곱잉여라했지? 즉 7은 (mod 3)에서 제곱잉여야. 

그리고 이차상호법칙에 따르면 3은 (mod 7)에서 제곱잉여가 '아니어야' 하지. 실제로 계산해보면...

1^2 ≡ 1 (mod 7)
2^2 ≡ 4 (mod 7)
3^2 ≡ 2 (mod 7)
4^2 ≡ 2 (mod 7)
5^2 ≡ 4 (mod 7)
6^2 ≡ 1 (mod 7)
보다시피 어떤 수도 제곱해서 3이 되질 않아. 

요약하자면 7이 (mod 3)에서 제곱잉여이고, 반대로 3은 (mod 7)에서 제곱잉여가 아니야. 둘의 결과가 다른 이유는 3과 7 둘 다 mod 4에서 3과 같기 때문이야.

이차상호법칙은 p와 q가 아주 클 때 진가를 발휘해. 예를 들어 p = 47이고 q = 283이라고 해보자. 그리고 누군가가 물었어. 47은 mod 283에서 제곱잉여인가요?

이차상호법칙이 없다면 우리는 일일이 계산해야 돼. mod 283에서 1의 제곱, 2의 제곱, 3의 제곱, ..., 282의 제곱을 일일이 다 계산하고, 이들 중 47이 있는지 확인해야 하지.

하지만 이차상호법칙은 47이 (mod 283)에서 제곱잉여인지 계산하는 대신 283이 (mod 47)에서 제곱잉여인지 계산하면 된다는 사실을 알려줘.

그리고 283은 mod 47에서 283 - 47 = 236과 같고, 그것은 236에서 47을 뺀 189와 같고, 이는 189에서 47을 뺀 142와 같고, 142에서 47을 뺀 95와 같고, 95에서 47을 뺀 48과 같고, 48에서 47을 뺀 1과 같지. 즉 283 ≡ 1 (mod 47)이야.

앞서 언급했듯, 1은 항상 제곱잉여지. 즉 283은 (mod 47)에서 제곱잉여고, 이차상호법칙에 따라 47은 (mod 283)에서 제곱잉여가 될 수 없다는 결론에 도달해. 굳이 1부터 282까지 일일이 제곱해보지 않더라도, 훨씬 더 계산을 쉽게 만들어낼 수 있지.

4. 이차상호법칙이 유용한 이유

이차상호법칙은 합동연산을 쉽게 만들어주는 강력한 도구야. 그리고 정수론에서는 합동연산을 정말 밥먹듯 쓰지. 예를 들어
x^2 - 9y^2 = 53을 만족하는 정수해 x,y가 존재할까? 라는 질문을 살펴보자.

합동연산을 모른다면, x와 y에 온갖 정수들을 일일이 대입해줘야 해. 

하지만 합동연산을 안다면... 음 이 식을 mod 3에서 풀어볼까? 하고 떠올려볼 수 있어.

x^2이야 냅두고, 9는 mod 3에서 0과 같으므로, 9y^2은 mod 3에서 y^2에 0을 곱한 꼴이 돼. 즉 0이지. 그리고 53은 mod 3에서 2야.

즉 x^2 - 9y^2 = 53이라는 식을 (mod 3)에서 계산하면 x^2 ≡ 2 (mod 3)이 돼. 하지만 앞서 봤듯, 2는 (mod 3)에서 제곱잉여가 될 수 없어. 다시말해,  (mod 3)에서 제곱해서 2가 되는 정수는 존재하지 않아.

만약 x^2-9y^2 = 53을 만족하는 정수 x와 y가 존재한다면, x의 (mod 3)과 y의 (mod 3)값이 x^2 ≡ 2 (mod 3)을 만족해야 해. 하지만 이 식은 해가 없어. 그러므로 원래의 식도 해가 존재할 수 없다는 사실을 알 수 있어. 한평생 계산해봐야 알 수 있는 문제가 너무나 깔끔하고 쉽게 해결됐지?

만약 mod 3에서 아무런 모순이 발생하지 않는다면? 그렇다면 다른 mod p를 취해도 돼. mod 5에서, mod 7에서 이런식으로 작은 소수들에서 식의 해결여부를 확인해볼 수 있지. 이들 중 하나라도 ‘해가 존재할 수 없음’이 나온다면, 원래의 방정식은 해가 존재할 수 없게 돼.

약간 역사 얘기를 해보면 이차상호법칙은 수학의 왕자 가우스가 처음 발견했어. 가우스는 수학에 있어서는 엄밀함을 넘어 아름다움을 추구했고, 스스로가 그 증명을 완전히 이해하고 아름답다고 느끼지 않으면 절대로 출간하지 않았대. 덕분에 가우스는 엄청나게 많은 수학적 발견을 했지만, 그가 살아있는 동안엔 가우스의 서재에 갇혀있었고, 가우스 사후에 널리 퍼지게 되었지.

하지만 그렇게 수학적 아름다움과 엄밀함을 중요시한 가우스가 이를 증명해내고도 도저히 믿을 수 없었다는 거야. 그는 이차상호법칙에 대한 증명을 6개나 만들어낸 후에야 이것이 사실임을 인정하고 발표했고 사후에 그의 증명 2개가 추가로 발견됐대.

물론 가우스 사후에도 수학은 많이 발전을 거듭해. 이차상호법칙은 이제 아틴의 상호법칙이라는 이름으로 훨씬 더 많이 발전됐고 일반화됐지. 물론 수학자들은 만족하지 않고 계속해서 더 일반화된, 더 정교한, 더욱 복잡한 상호법칙을 찾고 있어. 

자 오늘은 정수론의 꽃 이차상호법칙을 살펴봤어. 개인적으로 이차상호법칙의 발견이 정수론의 레벨을 한단계 끌어올린 사건이라고 생각해. 초등적 정수론이 대수적 정수론으로 탈바꿈한 계기를 이차상호법칙이라고 생각하지. 아무쪼록 수학에 관심이 많은 궤령부 친구들에게 재밌고 즐거운 뇌운동 시간이었기를 바라며, 정수론민수는 이만 물러갈게. QED