[정수론 입문 시리즈 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. 합동식

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

실험: 손으로 계산하기

나눗셈 알고리즘은 식을 외우기 전에 몫과 나머지를 직접 찾는 감각이 중요합니다.

나눗셈	표준 형태	몫 $q$	나머지 $r$
29를 5로 나누기	$29 = 5 \times 5 + 4$	5	4
42를 8로 나누기	$42 = 8 \times 5 + 2$	5	2
35를 7로 나누기	$35 = 7 \times 5 + 0$	5	0
-14를 5로 나누기	$-14 = 5 \times (-3) + 1$	-3	1

특히 마지막 줄을 직접 확인해 보세요.

$5 \times (-3) + 1 = -15 + 1 = -14$

나머지는 음수가 아니라 $0 \le r < |b|$를 만족하도록 잡았습니다.

패턴 발견

표에서 공통으로 보이는 패턴은 다음과 같습니다.

• 모든 예시는 $a = bq + r$ 꼴입니다.
• 나머지 $r$는 항상 0 이상이고 $|b|$보다 작습니다.
• 나머지가 0인 경우가 바로 나누어떨어지는 경우입니다.
• 음수 $a$에서도 나머지 범위는 그대로 유지됩니다.

즉, 나눗셈 알고리즘은 "나눗셈을 했다"는 말을 정수론에서 비교 가능한 표준 형태로 바꾸는 장치입니다.

이론 정리

나눗셈 알고리즘

정수 $a$와 0이 아닌 정수 $b$에 대해, $a = bq + r$, $0 \le r < |b|$를 만족하는 정수 $q,r$가 유일하게 존재합니다.

여기서 $q$는 몫, $r$는 나머지입니다. 특히 $r=0$이면 $b \mid a$입니다.

Python으로 확인하기

Python의 divmod는 몫과 나머지를 한 번에 돌려줍니다.

examples = [(29, 5), (42, 8), (35, 7), (-14, 5)]

for a, b in examples:
    q, r = divmod(a, b)
    print(f"{a} = {b} * {q} + {r}")
    assert a == b * q + r
    assert 0 <= r < abs(b)

assert가 실패하지 않는다면, 손으로 구한 표준 형태가 나눗셈 알고리즘의 조건을 만족한다는 뜻입니다.

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이라는 특별한 경우라는 점도 확인했습니다.

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