정수론은 정수를 단순히 계산하는 데서 끝나지 않고, 어떤 정수가 다른 정수를 나누는지, 공약수는 어떤 구조를 가지는지, 정수해를 갖는 방정식은 언제 풀리는지를 연구한다. 이 글에서는 이후의 합동식과 소수 이론을 이해하는 데 필요한 가장 기본적인 도구를 정리한다.

Divisibility

정수 , 에 대하여 일 때, 어떤 정수 가 존재하여

가 되면 가 를 나눈다고 하고 로 쓴다. 이때 는 의 divisor 또는 factor이고, 는 의 multiple이다.

예를 들어 이지만 이다. 정의에서 바로 다음 성질을 얻는다.

  • , ,
  • 이고 이면
  • 이고 이면 임의의 에 대해
  • , 이면

마지막에서 특히 중요한 것은 공약수가 두 수의 모든 정수 선형결합을 나눈다는 사실이다. 이 성질이 Bézout’s Identity와 Euclidean Algorithm의 기반이 된다.

Division Algorithm

Division Algorithm은 정수를 양의 정수로 나누었을 때 몫과 나머지가 정확히 하나씩 존재한다는 정리이다.

, 이면 유일한 정수 가 존재하여

를 만족한다.

존재성 증명

다음 집합을 생각한다.

는 공집합이 아니다. 를 충분히 작은 음의 정수로 잡으면 가 양수가 되기 때문이다. Well-Ordering Principle에 의해 에는 최소 원소 이 존재한다. 어떤 에 대해

이므로 이다. 이제 임을 보여야 한다. 만약 라면

이므로 이다. 그런데 이므로 이 최소라는 사실에 모순이다. 따라서 이다.

유일성 증명

두 표현

이 있다고 하자. 두 식을 빼면

이다. 그런데 이고 오른쪽은 의 배수이다. 절댓값이 보다 작은 의 배수는 0뿐이므로 이고, 이어서 이다.

Greatest Common Divisor

두 정수 가 동시에 0은 아니라고 하자. 양의 정수 가 다음을 만족하면 의 최대공약수라고 한다.

  1. 이고 이다.
  2. , 인 모든 정수 에 대해 이다.

이를 로 쓴다. 두 번째 조건은 단순히 수치적으로 가장 큰 공약수라는 뜻보다 강하다. 모든 공약수가 를 나누므로 공약수들의 구조를 완전히 대표한다.

Bézout’s Identity

정수론에서 가장 중요한 기본 정리 중 하나는 최대공약수를 두 정수의 선형결합으로 표현할 수 있다는 것이다.

를 만족하는 정수 가 존재한다.

증명

양의 정수인 선형결합을 모은 집합

을 생각한다. 이 집합은 공집합이 아니며 Well-Ordering Principle에 의해 최소 원소 를 갖는다. 어떤 정수 에 대해

이다.

Division Algorithm으로 , 라 하자. 그러면

이므로 도 의 정수 선형결합이다. 이면 이면서 이므로 최소성에 모순이다. 따라서 , 즉 이다. 같은 방식으로 이다.

반대로 가 의 공약수이면 는 모든 정수 선형결합을 나누므로 이다. 따라서 이다.

이 증명에서 다음 사실도 함께 얻는다.

즉 두 정수의 모든 선형결합은 최대공약수의 배수이며, 최대공약수의 모든 배수도 선형결합으로 표현된다.

Relatively Prime과 Euclid’s Lemma

이면 가 서로소라고 한다. Bézout’s Identity에 의해

한다.

이로부터 Euclid’s Lemma의 기본 형태가 나온다.

이고 이면 이다.

실제로 에 를 곱하면

이다. 왼쪽의 두 항은 모두 로 나누어지므로 이다.

Euclidean Algorithm

Division Algorithm을 반복하면 최대공약수를 빠르게 계산할 수 있다. 핵심은 다음 등식이다.

이면 이다.

증명

가 의 공약수이면 도 나누므로 는 의 공약수이다. 반대로 가 의 공약수이면 도 나누므로 의 공약수이다. 두 쌍의 공약수가 완전히 같으므로 최대공약수도 같다.

따라서

이라면 마지막으로 0이 아닌 나머지 가 이다.

Extended Euclidean Algorithm 예제

를 계산하면

따라서 최대공약수는 6이다. 식을 거꾸로 대입하면

즉 최대공약수뿐 아니라 Bézout 계수까지 계산할 수 있다.

Least Common Multiple

양의 공배수 중 가장 작은 수를 라 한다. 일 때

이다.

, , 라 하면 이다. 는 의 공배수이다. 한편 임의의 양의 공배수 에 대해 라 하면 , 이고 가 서로소이므로 이다. 따라서 가 최소공배수이다.

부호까지 고려하면 일반적으로

로 쓴다.

Linear Diophantine Equation

정수 계수를 갖고 정수해를 구하는 방정식을 Diophantine Equation이라고 한다. 가장 기본적인 형태는

이다.

이 방정식은 일 때, 그리고 그때에만 정수해를 갖는다.

증명

해 가 존재하면 는 를 나누므로 도 나눈다.

반대로 라 하자. Bézout’s Identity로 이고 인 정수 가 존재한다. 따라서

이므로 , 가 한 해이다.

한 특수해 를 알면 모든 해는

로 주어진다. 이 식을 원래 방정식에 대입하면 추가된 두 항이 상쇄되어 해가 유지된다. 반대로 두 해의 차를 비교하고 와 가 서로소임을 사용하면 모든 해가 이 형태임을 보일 수 있다.

정리

Division Algorithm은 정수의 몫과 나머지를 보장한다. Bézout’s Identity는 최대공약수를 선형결합으로 표현하며, Euclidean Algorithm은 이를 실제로 계산한다. 이 결과들은 일차 디오판토스 방정식이 정수해를 가질 조건과 모든 해의 형태를 완전히 결정한다.

연습 문제

  1. Division Algorithm을 이용해 을 6으로 나눈 몫과 나머지를 구한다.
  2. Extended Euclidean Algorithm으로 을 구하고 이를 꼴로 표현한다.
  3. 방정식 의 모든 정수해를 구한다.

풀이

1번

나머지는 이어야 한다. 다음과 같이 쓸 수 있다.

따라서 몫은 , 나머지는 1이다.

2번

따라서 이다. 역대입하면

즉 , 이다.

3번

이고 이므로 해가 존재한다. 식을 6으로 나누면

이다. , 이 한 해이다. 따라서 모든 해는

이다.