‘정수론’. 보통 중학교/고등학교 과정에서는 많이 배우지 않는 내용이다. 고등학교 과정에서 등장하는 정수론 내용은, ‘임의의 두 수 A, B에 대해 A를 B로 나누었을 때 몫 Q와 나머지 R(R은 0 이상 B 미만)이 존재해 A=BQ+R로 쓸 수 있다.’는 내용이 거의 전부이다. 하지만, 이 내용은 ‘정수론’이라는 과목의 일부분일 뿐이다. 이 글에서는, 정수론에서 자주 사용되는 기초 정리들과, 그 활용에 대해 간단히 설명해 보겠다.
먼저, ‘유클리드 호제법’이 있다. ‘유클리드 호제법’은 어떤 두 수의 최대 공약수를 구할 때 사용하는 방법인데, 어떤 두 수 A, B에 대해 A=BQ+R로 썼을 때, 식 gcd(A,B)=gcd(B,R)이 성립한다는 정리를 바탕으로 하고 있다.(이 때, gcd(x,y)는 두정수 x,y의 최대공약수를 의미한다.) 예를 들어, 84와 35의 최대공약수를 유클리드 호제법을 이용해 구해보자. 84=35*2+14, 35=14*2+7이므로, gcd(84,35)=gcd(35,14)=gcd(14,7)=7이다. 84와 35는 매우 작은 수라서, 소인수분해 등 다른 방법을 이용해 최대공약수를 구하는 것이 더 쉬울 수도 있지만, 수가 매우 커진다면, 유클리드 호제법을 이용해 최대공약수를 구하는 것이 최대공약수를 구하는 매우 효과적인 방법이 될 것이다.
다음으로, ‘페르마의 소정리’가 있다. ‘페르마의 소정리’를 좀 더 일반적으로 서술한 정리가 ‘오일러의 정리’인데, 이 두 정리는 ‘어떤 수를 어떤 수로 나눈 나머지를 쉽게 구하기 위해’ 사용되는 정리이다. ‘페르마의 소정리’는 임의의 소수 p와, p의 배수가 아닌 정수 a에 대해, a의 (p-1)제곱을 p로 나눈 나머지가 1이라는 정리이다. 예를 들어, 9의 99제곱을 13으로 나눈 나머지를 구하는 문제를 풀 때, ‘페르마의 소정리’를 이용하지 않으면, 비교적 복잡한 계산을 해야 답을 구할 수 있다. 페르마의 소정리에 의해, 9의 12제곱을 13으로 나눈 나머지가 1이고, 99=12*8+3이므로, 9의 99제곱을 13으로 나눈 나머지는, 9의 3제곱을 13으로 나눈 나머지와 같고, 이 값은 1이다.
다음으로, ‘윌슨 정리’가 있다. 윌슨 정리는, 임의의 소수 p에 대해 (p-1)!을 p로 나눈 나머지가 (p-1)이라는 정리이다.(이 때, n!은 1부터 n까지의 모든 자연수를 곱한 값이다.) 예를 들어, 12!을 13으로 나눈 나머지는 12이다. 간단한 응용으로, 11!을 13으로 나눈 나머지를 구해보자. 12!=12*11!이므로, 윌슨 정리에 의해 12*11!을 13으로 나눈 나머지는 12이다. 따라서, 11!을 13으로 나눈 나머지는 1이다.(이것을 합동식을 이용해 표기하면, ax==b(mod m) 꼴의 합동식이 되는데, 이 합동식의 해를 구하는 방법에는 x에 0,1, ---, m-1을 대입해보는 방법, ax-my=b꼴의 부정방정식으로 바꾸어 해를 구하는 방법 등 여러 가지 방법이 있지만, 이에 대한 자세한 설명은 이 글에서 생략하겠다.)
마지막으로, 가우스 함수와 관련된 몇 가지 정리들이 있다. 먼저, [x]는 x보다 작거나 같은 최대의 정수를 의미한다. 이 때, 서로소인 두 양의 정수 a,b에 대해 식 ‘([a/b]+[2a/b]+ --- +[(b-1)a/b])=(a-1)(b-1)/2’이 성립한다. 이 식의 증명은, 대수적 방법으로 할 수도 있지만, 기하학적 의미를 생각해 보면 쉽게 증명할 수 있다. 이 식의 좌변은, 직선 y=(a/b)x, y=0, x=b로 둘러싸인 영역 내부의 격자점(x,y 좌표가 모두 정수인 점)의 개수인데, 대칭성을 고려했을 때, 이 값은 (a-1)(b-1)/2가 된다. 따라서, 증명이 완료되었다. 대수적 방법으로 증명하기 위해서는, 0<=x<1일 때, 식 ([x]+[a-x])의 값을 조사해 보아야 한다. x가 0이 아닐 때, 이 값은 (a-1)이다. 따라서, 가우스가 ‘1부터 100까지의 합은 5050이다.’라는 것을 증명할 때 사용했던 논리와 동일한 논리를 사용하면, 식 ‘([a/b]+[2a/b]+ --- +[(b-1)a/b])=(a-1)(b-1)/2’이 성립한다는 것이 증명된다. 이 두 가지 증명은 잘 알고 있어야 한다. 이 식이 문제 해결에 사용되는 경우보다는, 이 식을 증명하는 데 필요한 아이디어들이 문제 해결에 사용되는 경우가 많기 때문이다.
지금까지 정수론에서 자주 사용되는 정리들에 대해 논의해 보았다. 이런 정리들의 증명을 충분히 익히고, 이런 정리들을 문제 해결에 활용하는 것을 충분히 연습한다면, 정수론 문제들을 좀 더 효과적으로 해결할 수 있을 것이다.
HOME > 
