[정수론 입문 시리즈 3편] 나눗셈 알고리즘은 왜 정수론의 출발점인가?

지난 글에서는 약수와 배수를 나누어떨어짐의 관점에서 읽었습니다. 이제 한 걸음 더 나아가면, 어떤 정수든 나눗셈을 할 때 결국 몫과 나머지로 정리된다는 사실을 보게 됩니다. 이 구조를 정리한 것이 바로 나눗셈 알고리즘입니다.

이름 때문에 복잡한 계산 절차처럼 들릴 수 있지만, 핵심은 단순합니다. 정수를 다른 정수로 나누면, 몫과 나머지가 있는 표준 형태로 항상 쓸 수 있다는 것입니다. 여기서 중요한 점은 이 표준 형태가 사실상 하나로 정해진다는 데 있습니다.

What this post covers

• 나눗셈 알고리즘의 정확한 형태를 정리합니다.
• 왜 $a = bq + r$에서 나머지 범위가 중요한지 설명합니다.
• 구체적인 예시로 몫과 나머지를 읽는 법을 익힙니다.
• 이 구조가 왜 최대공약수와 유클리드 호제법으로 이어지는지 봅니다.

이번 글에서 새로 나오는 용어

• 나눗셈 알고리즘 (Division Algorithm): 정수 $a$를 0이 아닌 정수 $b$로 나눌 때 $a = bq + r$ 꼴로 나타낼 수 있다는 정리입니다.
• 몫 (Quotient): 나눗셈에서 몇 번 들어가는지를 나타내는 값입니다.
• 나머지 (Remainder): 나누고 남는 부분입니다.
• 나누어떨어짐 (Divisibility): 나머지가 0인지 아닌지로 약수 관계를 판별하는 기준입니다.

나눗셈 알고리즘의 핵심 문장

정수 $a$와 0이 아닌 정수 $b$에 대해, 다음을 만족하는 정수 $q$, $r$가 존재합니다.

$$a = bq + r \qquad (0 \le r < |b|)$$

여기서

• $q$는 몫
• $r$는 나머지

입니다.

이 식은 단순한 계산 결과가 아니라, 정수를 다루는 표준 분해 방식입니다. 이 범위를 지키면 몫과 나머지가 뒤섞이지 않고, 같은 정수를 같은 기준으로 읽을 수 있습니다.

왜 나머지 조건이 꼭 필요할까?

처음 보면 $a = bq + r$ 꼴은 너무 많아 보입니다. 예를 들어

$$23 = 4 \times 5 + 3$$

도 맞고,

$$23 = 4 \times 4 + 7$$

도 맞습니다.

하지만 두 번째 식에서는 나머지 7이 4보다 크므로, 우리가 원하는 표준 형태가 아닙니다. 정수론에서는 한 나눗셈 결과를 유일한 형태로 읽고 싶기 때문에 나머지는 항상

$$0 \le r < |b|$$

를 만족해야 합니다.

이 조건이 있어야 나눗셈 결과가 뒤죽박죽이 되지 않고, 몫과 나머지가 사실상 하나로 정해집니다. 즉, 나머지 범위 조건은 보기 좋게 만들기 위한 약속이 아니라, 나눗셈 결과를 안정적으로 비교하기 위한 조건입니다.

예시로 보는 나눗셈 알고리즘

예시 1. 23을 4로 나누기

23을 4로 나누면

$$23 = 4 \times 5 + 3$$

입니다.

• 몫: 5
• 나머지: 3

여기서 나머지 3은 0 이상 4 미만이므로 조건을 만족합니다.

예시 2. 24를 6으로 나누기

$$24 = 6 \times 4 + 0$$

입니다.

나머지가 0이면 나누어떨어집니다. 따라서 6은 24의 약수입니다.

즉, 나눗셈 알고리즘은 약수 여부도 바로 설명해 줍니다.

예시 3. 음수가 들어갈 때

정수론에서는 음수도 다룹니다. 예를 들어 -17을 5로 나누면 다음처럼 쓸 수 있습니다.

$$-17 = 5 \times (-4) + 3$$

여기서 몫은 -4, 나머지는 3입니다. 계산을 직접 확인하면

$$5 \times (-4) + 3 = -20 + 3 = -17$$

가 됩니다. 나머지는 음수가 아니라

$$0 \le r < 5$$

를 만족하도록 잡는다는 점이 중요합니다. 음수가 포함되어도 나머지의 범위 규칙은 그대로 유지됩니다.

나눗셈 알고리즘이 약수 개념을 어떻게 정리할까?

지난 글에서 "나누어떨어진다"는 말을 배웠습니다. 이제는 이 말이 더 정확하게 보입니다.

정수 $a$를 정수 $b$로 나눈 결과가

$$a = bq + r$$

일 때,

• $r = 0$이면 $b$는 $a$의 약수
• $r \ne 0$이면 약수가 아님

입니다.

즉, 나누어떨어짐은 나눗셈 알고리즘에서 나머지가 0인 특별한 경우라고 볼 수 있습니다.

왜 정수론의 출발점이라고 할까?

나눗셈 알고리즘은 이후 여러 핵심 개념의 기반이 됩니다.

1. 최대공약수

두 수를 나눌 때 나오는 나머지를 계속 추적하면 최대공약수를 빠르게 구할 수 있습니다. 실제로 이후에는

$$\gcd(a,b) = \gcd(b,r)$$

처럼 공약수 문제가 더 작은 나머지 문제로 바뀌는 모습을 보게 됩니다.

2. 유클리드 호제법

유클리드 호제법은 한마디로 말해 "나머지를 반복해서 새 문제로 바꾸는 방법"입니다. 나눗셈 알고리즘이 없으면 이 반복의 기준도 세울 수 없습니다.

3. 합동식

나중에 배우는 합동도 결국 "나머지가 같다"는 관점입니다. 따라서 나눗셈 알고리즘은 합동식의 배경이 되기도 합니다.

Common mistakes

1. 나머지를 제수보다 크게 쓰는 실수

$23 = 4 \times 4 + 7$은 등식으로는 맞지만, 나눗셈 알고리즘의 표준 형태는 아닙니다. 나머지는 항상 $|b|$보다 작아야 합니다.

2. 나머지가 음수여도 된다고 생각하는 실수

정수론의 기본 표기에서는 보통

$$0 \le r < |b|$$

를 사용합니다. 이 범위를 지켜야 비교와 분류가 쉬워집니다.

3. 나눠떨어짐과 몫/나머지를 따로 생각하는 실수

"나누어떨어진다"는 것은 결국 나머지가 0이라는 뜻입니다. 따로 외우기보다 한 구조 안에서 보는 편이 좋습니다.

Wrap-up

이번 글에서는 나눗셈 알고리즘의 핵심 형태

$$a = bq + r \qquad (0 \le r < |b|)$$

를 정리하고, 왜 이 식이 정수론의 표준 언어가 되는지 살펴봤습니다. 또 나누어떨어짐이 나머지 0이라는 특별한 경우라는 점도 확인했습니다.

다음 글에서는 두 수의 공통 구조를 요약하는 값인 최대공약수와 최소공배수를 다루며, 정수 사이의 공통성을 어떻게 읽는지 정리해 보겠습니다.