정수론 — 소수, 나눗셈의 성질과 모듈러 산술

정수론은 정수를 연구하는 분야입니다. 소수, 나눗셈의 성질, 모듈러 산술을 이해하고 싶다면, 이미 정수론의 핵심을 보고 있는 것입니다.

소수는 $1$보다 큰 정수 중에서 양의 약수가 정확히 두 개, 즉 $1$과 자기 자신뿐인 수입니다. 나눗셈의 성질은 한 정수가 다른 정수로 나누어떨어지는지를 묻습니다. 모듈러 산술은 나머지를 추적하는 방식이어서 흔히 시계 산술이라고도 불립니다.

정수론에서 다루는 내용

이 세 가지 아이디어는 서로 연결됩니다:

• 소수는 양의 정수를 이루는 기본 구성 요소입니다.
• 나눗셈의 성질은 한 정수가 다른 정수에 정확히 들어맞는지를 알려 줍니다.
• 모듈러 산술은 나눗셈 문제를 나머지 문제로 바꾸어 표현합니다.

예를 들어, "$a$가 $n$으로 나누어떨어진다"는 말은 다음과 같습니다.

$$a \equiv 0 \pmod n$$

즉, 나눗셈 문제는 종종 나머지 문제로 다시 쓸 수 있습니다.

소수: 기본 구성 요소

소수는 다음과 같이 시작합니다.

$$2, 3, 5, 7, 11, 13, \dots$$

수 $2$는 유일한 짝수 소수입니다. 다른 모든 짝수는 $2$로 나누어떨어지므로 소수가 될 수 없습니다.

$1$보다 큰 양의 정수가 소수가 아니면 합성수라고 합니다. 예를 들어 $21$은

$$21 = 3 \cdot 7$$

이므로 합성수입니다.

소수가 중요한 이유는 $1$보다 큰 모든 정수를 인수의 순서를 제외하면 소수들의 곱으로 나타낼 수 있기 때문입니다. 이것이 소인수분해의 핵심 아이디어입니다.

나눗셈의 성질: 한 수가 다른 수에 정확히 들어맞을 때

$a$와 $b$가 정수이고 $b \ne 0$일 때, "$b$가 $a$를 나눈다"는 것은 어떤 정수 $k$가 존재하여

$$a = bk$$

가 된다는 뜻입니다.

이것은 다음과 같이 씁니다.

$$b \mid a$$

예를 들어 $20 = 4 \cdot 5$이므로 $4 \mid 20$입니다. 하지만 $22$를 $4$로 나누면 나머지가 남으므로 $4 \nmid 22$입니다.

나눗셈의 성질은 약수, 배수, 최대공약수, 최소공배수의 바탕이 되는 언어입니다. 또 익숙한 판정법도 설명해 줍니다.

• 어떤 수의 일의 자리가 짝수이면 그 수는 $2$로 나누어떨어집니다.
• 어떤 수의 일의 자리가 $0$ 또는 $5$이면 그 수는 $5$로 나누어떨어집니다.
• 어떤 수의 각 자리 숫자의 합이 $3$으로 나누어떨어지면 그 수는 $3$으로 나누어떨어집니다.

마지막 규칙은 단순한 요령이 아닙니다. 이것은 모듈러 산술에서 나옵니다.

모듈러 산술: 나머지로 계산하기

두 정수를 $n$으로 나누었을 때 나머지가 같으면, 이 둘은 법 $n$에서 합동이라고 합니다. 다음과 같이 씁니다.

$$a \equiv b \pmod n$$

이 말은 $n$이 $a-b$를 나눈다는 뜻입니다.

예를 들어,

$$17 \equiv 5 \pmod{12}$$

입니다. $17$과 $5$를 $12$로 나누면 둘 다 나머지가 $5$이고, 동시에 $17 - 5 = 12$는 $12$로 나누어떨어지기 때문입니다.

이 개념이 유용한 이유는 어떤 수를 더 간단한 합동인 수로 바꿔 계산할 수 있기 때문입니다. $12$시간 시계에서는 $15$시간을 더하는 것이 $3$시간을 더하는 것과 같은 효과를 냅니다. 왜냐하면

$$15 \equiv 3 \pmod{12}$$

이기 때문입니다.

풀이 예시: 왜 $231$은 $3$으로 나누어떨어질까?

수 $231$을 봅시다.

먼저 자릿값 형태로 쓰면

$$231 = 2 \cdot 100 + 3 \cdot 10 + 1$$

입니다.

이제 법 $3$에서 계산합니다. 다음이 성립하므로

$$10 \equiv 1 \pmod 3$$

따라서

$$100 = 10^2 \equiv 1^2 \equiv 1 \pmod 3$$

입니다.

그러므로

$$231 \equiv 2 \cdot 1 + 3 \cdot 1 + 1 \equiv 2 + 3 + 1 = 6 \equiv 0 \pmod 3$$

가 됩니다.

$231 \equiv 0 \pmod 3$이므로, 이 수는 $3$으로 나누어떨어집니다.

이것이 바로 각 자리 숫자의 합 판정법을 설명해 줍니다. $10$진법에서는 $10$의 각 거듭제곱이 모두 법 $3$에서 $1$과 합동이므로, 전체 수는 각 자리 숫자의 합과 같은 나머지를 가집니다.

그리고 실제로 나누어 보면

$$231 = 3 \cdot 77 = 3 \cdot 7 \cdot 11$$

이므로 $231$은 소수가 아니라 합성수입니다.

정수론에서 자주 하는 실수

$1$을 소수로 보는 경우

$1$은 소수가 아닙니다. 소수는 양의 약수가 정확히 두 개여야 하는데, $1$의 양의 약수는 하나뿐입니다.

나눗셈의 성질에서 조건을 잊는 경우

$b \mid a$라는 표현은 $b \ne 0$일 때만 의미가 있습니다. $0$으로 나누는 것은 허용되지 않습니다.

등호와 합동을 혼동하는 경우

$17 \equiv 5 \pmod{12}$는 $17 = 5$라는 뜻이 아닙니다. 두 수의 차가 $12$의 배수라는 뜻입니다.

나눗셈 판정법을 지나치게 일반화하는 경우

어떤 판정법은 $10$진법의 성질 덕분에 빠르게 쓸 수 있습니다. 그렇다고 모든 약수에 대해 간단한 자릿수 규칙이 있는 것은 아닙니다.

정수론은 어디에 나타날까?

학교 수학 수준에서 정수론은 인수분해, 나머지 문제, 나눗셈의 성질에 대한 증명, 시계 형태의 문제에서 자주 등장합니다. 또한 분수를 약분하거나, 공약수를 찾거나, 반복되는 주기가 있는 문제를 풀 때도 나타납니다.

더 깊은 수준에서는 소수와 모듈러 산술이 암호학과 컴퓨터 과학에서도 핵심 역할을 합니다. 이런 배경지식이 없어도 개념을 사용하는 데는 문제가 없지만, 정수론이 응용 분야에서 계속 등장하는 이유를 이해하는 데는 도움이 됩니다.

직접 해 보기

같은 논리를 $462$에도 적용해 보세요. 먼저 각 자리 숫자의 합으로 $3$으로 나누어떨어지는지 확인한 뒤, 소수인지 합성수인지 판단할 수 있을 만큼 인수분해해 보세요.

방법을 확인하고 싶다면, 수학 풀이 도구에서 비슷한 나눗셈 또는 나머지 문제를 풀어 보고 모듈러 산술 단계가 자신의 풀이와 어떻게 대응되는지 비교해 보세요.