• 정수론을 보기 전에 먼저 읽는 기호와 기본 개념
• 최대공약수는 어떻게 구할까
• 나머지가 같다는 말은 왜 중요할까
• 소수는 정수론의 기본 재료다
• 큰 거듭제곱과 RSA까지 연결하기
• 정리
• FAQ

정수론을 보기 전에 먼저 읽는 기호와 기본 개념

저는 정수론을 공부할 때 계산보다 먼저 기호를 읽는 법을 잡는 편이 훨씬 중요하다고 봅니다. 기호를 읽지 못하면 문장 전체가 끊겨 보이고, 반대로 기호가 읽히면 정의와 정리가 문장처럼 연결되기 시작합니다. 이 단원에서는 약수와 배수, 최대공약수, 모듈로 합동, 거듭제곱의 나머지 계산이 계속 등장하므로 먼저 익숙해져야 합니다.

캔버스에서 자주 나오는 기호 읽는 법

a ∣ b            : a가 b를 나눈다
b mod m          : b를 m으로 나눈 나머지
gcd(a, b)        : a와 b의 최대공약수
a ≡ b (mod m)    : a와 b는 mod m에서 합동이다
bⁿ mod m         : b의 n제곱을 m으로 나눈 나머지

예를 들어 a ∣ b는 a가 b의 약수라는 뜻입니다. b = ac를 만족하는 정수 c가 존재하면 성립한다고 이해하면 됩니다. 또 a ≡ b (mod m)은 두 수를 m으로 나눴을 때 나머지가 같다는 뜻이며, 더 정확히는 a-b가 m으로 나누어떨어진다는 의미입니다.

처음에는 기호가 많아 보이지만 실제로는 전부 정수 사이의 관계를 간단하게 적기 위한 표기입니다. 저는 이 부분을 먼저 익혀두면 뒤에서 나오는 정리들이 훨씬 덜 딱딱하게 느껴진다고 생각합니다.

약수와 배수는 어떻게 읽을까

3 ∣ 12   → 12 = 3 × 4 이므로 참
5 ∣ 12   → 12 = 5 × c 를 만족하는 정수 c가 없으므로 거짓
7 ∣ 21   → 21 = 7 × 3 이므로 참

약수와 배수는 정수론의 출발점입니다. a가 b를 나눈다는 말은 나눗셈 결과가 정수로 딱 떨어진다는 뜻입니다. 그래서 a ∣ b가 성립하면 a는 b의 약수이고, b는 a의 배수입니다.

형성평가에서 자주 나오는 함정은 나눗셈 기호를 그대로 약수 관계로 착각하는 경우입니다. 예를 들어 a ∣ b와 a ∣ c라고 해서 일반적으로 a ∣ (b ÷ c)가 되는 것은 아닙니다. 약수 관계는 덧셈, 뺄셈, 곱셈 쪽에서는 잘 이어지지만, 나눗셈은 정수 조건이 깨질 수 있어서 조심해야 합니다.

최대공약수는 어떻게 구할까

최대공약수는 두 정수를 동시에 나누는 가장 큰 자연수입니다. 저는 최대공약수를 단순히 답 하나를 구하는 개념으로 보기보다, 두 수가 얼마나 공통된 구조를 가지고 있는지 보여주는 기준으로 이해하는 편이 좋다고 봅니다. 여기서 핵심 도구가 유클리드 호제법입니다.

유클리드 호제법을 끝까지 따라가 보기

gcd(252, 198)
252 = 198 × 1 + 54
198 = 54 × 3 + 36
54 = 36 × 1 + 18
36 = 18 × 2 + 0
따라서 gcd(252, 198) = 18

유클리드 호제법은 큰 수를 작은 수로 나누고, 나온 나머지로 다시 계산을 이어가는 방식입니다. 핵심은 gcd(a, b) = gcd(b, r)라는 성질입니다. 즉, a를 b로 나눈 나머지를 r이라고 하면 원래 두 수의 최대공약수는 b와 r의 최대공약수와 같습니다.

이 과정을 계속 반복하면 결국 나머지가 0이 되는 순간이 나오고, 그 직전의 나누는 수가 최대공약수가 됩니다. 계산이 길어 보여도 원리는 한 가지뿐이라서, 한 줄씩 그대로 내려오면 됩니다.

베주의 항등식은 왜 같이 기억해야 할까

gcd(a, b) = d 이면
ax + by = d 를 만족하는 정수 x, y가 존재한다
예: gcd(30, 18) = 6
30 × (-1) + 18 × 2 = 6

베주의 항등식은 최대공약수가 두 수의 정수 선형결합으로 표현된다는 사실을 말합니다. 저는 이 정리를 보면 최대공약수가 단순한 계산 결과가 아니라, 두 수를 정수 계수로 조합해서 만들 수 있는 가장 기본적인 공통 단위처럼 느껴집니다.

이 내용은 나중에 모듈로 역원이나 RSA의 키 계산을 이해할 때도 연결됩니다. 실제로는 확장 유클리드 호제법을 이용해 ax + by = d 꼴의 계수를 거꾸로 찾아가며 필요한 값을 구합니다. 지금 단계에서는 최대공약수가 단순히 숫자 하나로 끝나지 않고, 식으로도 표현될 수 있다는 점만 분명히 잡아두면 충분합니다.

나머지가 같다는 말은 왜 중요할까

정수론에서 모듈로 합동은 매우 자주 등장합니다. 저는 이 개념을 처음 볼 때 새로운 연산처럼 느끼기보다, 같은 나머리를 가지는 수들을 한 묶음으로 보는 관점이라고 이해하면 훨씬 편하다고 생각합니다. 시계가 12시간 단위로 반복되는 구조를 떠올리면 직관을 잡기 쉽습니다.

모듈로 합동의 정의를 숫자로 이해하기

17 ≡ 5 (mod 12)
이유: 17 - 5 = 12 이고 12는 12로 나누어떨어진다
29 ≡ 5 (mod 12)
이유: 29 - 5 = 24 이고 24는 12로 나누어떨어진다

a ≡ b (mod m)은 a-b가 m의 배수라는 뜻입니다. 같은 말을 나머지 관점으로 바꾸면, a와 b를 m으로 나눴을 때 나머지가 같다는 뜻입니다. 그래서 17과 5는 12로 나눴을 때 모두 나머지 5를 남기므로 mod 12에서 같은 부류로 볼 수 있습니다.

이 개념이 중요한 이유는 큰 수를 더 작은 대표값으로 바꿔 계산할 수 있기 때문입니다. 특히 거듭제곱처럼 숫자가 급격히 커지는 계산에서는 합동이 계산량을 크게 줄여줍니다.

합동의 기본 성질은 어떻게 쓰일까

a ≡ b (mod m), c ≡ d (mod m) 이면
(a + c) ≡ (b + d) (mod m)
(a - c) ≡ (b - d) (mod m)
(a × c) ≡ (b × d) (mod m)
예: 17 ≡ 5 (mod 12)
17² ≡ 5² ≡ 25 ≡ 1 (mod 12)

합동은 덧셈, 뺄셈, 곱셈에서 자연스럽게 이어집니다. 그래서 계산할 때 큰 수를 계속 들고 가지 않고, 먼저 작은 나머지로 바꾼 뒤 계산할 수 있습니다. 저는 이 부분이 정수론에서 가장 실용적인 장면 중 하나라고 생각합니다.

다만 합동식에서는 나눗셈을 아무 때나 해도 되는 것은 아닙니다. 어떤 수로 나누려면 그 수가 해당 모듈러 환경에서 역원을 가져야 합니다. 이 점을 놓치면 합동식 계산에서 가장 자주 하는 실수가 나옵니다.

소수는 정수론의 기본 재료다

소수는 1보다 큰 자연수 중에서 1과 자기 자신만을 양의 약수로 가지는 수입니다. 합성수는 1보다 크지만 소수가 아닌 자연수입니다. 저는 소수를 정수론의 원자 같은 존재로 이해하는 편이 좋다고 봅니다. 왜냐하면 모든 2 이상의 자연수는 결국 소수들의 곱으로 분해되기 때문입니다.

소인수분해와 산술의 기본정리

84 = 2 × 42
   = 2 × 2 × 21
   = 2² × 3 × 7

360 = 2 × 180
    = 2 × 2 × 90
    = 2³ × 3² × 5

산술의 기본정리는 2 이상의 모든 자연수가 소수이거나 소수의 곱으로 유일하게 표현된다는 내용입니다. 여기서 중요한 단어는 유일하게입니다. 순서를 제외하면 소인수분해 결과는 하나로 정해집니다.

이 정리는 정수론 전체의 뼈대 역할을 합니다. 최대공약수, 최소공배수, 약수의 개수, 인수분해 기반 계산이 모두 이 구조 위에서 자연스럽게 설명됩니다.

소수는 끝이 없고, 찾는 방법도 있다

에라토스테네스의 체 예시
2는 소수 → 2의 배수 제거
3은 소수 → 3의 배수 제거
5는 소수 → 5의 배수 제거
남는 수를 차례로 확인

메르센 소수 형태
Mₙ = 2ⁿ - 1

소수는 무한히 많습니다. 즉, 아무리 많은 소수를 이미 알고 있어도 그보다 더 큰 소수가 존재합니다. 그래서 소수를 찾는 방법도 오래전부터 연구되어 왔고, 대표적인 고전적 방법이 에라토스테네스의 체입니다.

메르센 소수는 2의 거듭제곱에서 1을 뺀 형태의 수 가운데 소수인 경우를 말합니다. 모든 2ⁿ-1이 소수인 것은 아니지만, 이 형태는 큰 소수 탐색과 연결되기 때문에 정수론과 암호학 맥락에서 자주 언급됩니다.

큰 거듭제곱과 RSA까지 연결하기

정수론이 흥미로운 이유는 추상적인 성질이 실제 계산과 암호 기술로 이어지기 때문입니다. 저는 이 장의 마지막을 볼 때 페르마의 작은 정리, 빠른 모듈러 거듭제곱, RSA를 따로 외우기보다 하나의 흐름으로 묶어보는 것이 가장 중요하다고 생각합니다.

페르마의 작은 정리와 나머지 거듭제곱 알고리즘

페르마의 작은 정리
p가 소수이고 p가 a를 나누지 않으면
a^(p-1) ≡ 1 (mod p)

빠른 계산 예시
3¹³ mod 7
13 = 8 + 4 + 1
3² ≡ 2 (mod 7)
3⁴ ≡ 4 (mod 7)
3⁸ ≡ 2 (mod 7)
따라서
3¹³ = 3⁸ × 3⁴ × 3 ≡ 2 × 4 × 3 = 24 ≡ 3 (mod 7)

페르마의 작은 정리는 소수와 합동식이 만나는 대표적인 정리입니다. 이 정리 자체를 외우는 것도 필요하지만, 저는 왜 유용한지를 먼저 보는 편이 좋다고 봅니다. 거듭제곱의 나머지를 줄일 수 있기 때문에 계산량이 크게 줄어듭니다.

나머지 거듭제곱 알고리즘은 지수를 이진수처럼 분해해서 필요한 제곱만 곱하는 방식입니다. 그래서 bⁿ mod m을 무식하게 n번 곱하지 않고도 훨씬 빠르게 계산할 수 있습니다. RSA 같은 공개키 암호에서 이런 계산 효율은 필수입니다.

RSA는 왜 소수와 연결될까

RSA의 아주 단순한 흐름
1. 큰 소수 p, q를 고른다
2. n = p × q 를 만든다
3. 공개키로 암호화한다
4. 개인키로 복호화한다
핵심 아이디어: 곱하는 것은 쉽지만 다시 소인수분해하는 것은 매우 어렵다

RSA는 공개키 암호 방식의 대표적인 예시입니다. 암호화에 쓰는 키는 공개하고, 복호화에 필요한 키는 비밀로 유지합니다. 여기서 중요한 기반이 큰 수의 소인수분해가 어렵다는 점입니다.

조금 더 정확히 보면 RSA는 큰 소수 p, q로 n = pq를 만들고, φ(n) = (p-1)(q-1)을 바탕으로 키를 구성합니다. 이때 공개 지수 e는 φ(n)과 서로소가 되도록 고르고, 개인 지수 d는 ed ≡ 1 (mod φ(n))을 만족하도록 정합니다. 바로 이 값을 찾을 때 유클리드 호제법과 베주 항등식이 실질적으로 쓰입니다.

정리하면, 유클리드 호제법은 최대공약수와 역원 계산으로 연결되고, 모듈로 합동은 암호 계산의 언어가 되며, 소수와 소인수분해는 RSA의 안전성과 연결됩니다. 저는 이 지점에서 정수론이 단순한 수학 단원이 아니라 실제 정보보호 기술의 기초라는 사실이 드러난다고 생각합니다.

결론

저는 정수론 단원을 공부할 때 약수와 배수, 최대공약수, 합동식, 소수, 빠른 모듈러 계산, RSA를 각각 따로 외우기보다 하나의 흐름으로 이해하는 것이 가장 중요하다고 봅니다. 먼저 기호를 읽고, 유클리드 호제법으로 계산 원리를 익히고, 모듈로 합동으로 나머지 관점을 잡고, 소수와 산술의 기본정리로 정수의 구조를 이해한 뒤, 마지막에 페르마의 작은 정리와 RSA까지 연결하면 이 정수론 장 전체가 훨씬 선명하게 보입니다.

많이 받는 질문

Q. a ∣ b와 a ≡ b (mod m)은 같은 뜻인가요?
같지 않습니다. a ∣ b는 a가 b의 약수라는 뜻이고, a ≡ b (mod m)은 a와 b의 차가 m의 배수라는 뜻입니다. 하나는 나눗셈 관계이고, 다른 하나는 같은 나머지 관계입니다.

Q. 1은 왜 소수가 아닌가요?
소수는 양의 약수가 정확히 1과 자기 자신 두 개뿐인 수입니다. 1은 약수가 하나뿐이라서 소수 정의에 들어가지 않습니다. 이 구분이 있어야 소인수분해의 유일성도 깔끔하게 유지됩니다.

Q. RSA에서 왜 큰 소수를 사용하나요?
큰 소수 두 개를 곱해 만든 수는 계산하기는 쉽지만, 다시 원래 소수로 분해하는 일은 매우 어렵습니다. RSA는 이 비대칭적인 난이도 차이를 활용하는 암호 방식입니다.