방송대 방통대 이산수학 13강 - 정수론 - 요약 노트 시험족보 예상문제 - 올에이클래스

이산수학 13강 - 정수론

정수의 나눗셈과 최대공약수에서 출발하여 유클리드 호제법, 모듈로 합동과 합동의 연산 법칙을 학습한다. 이어서 소수와 소인수분해, 소수의 무한성, 페르마의 작은 정리와 빠른 나머지 거듭제곱을 살펴보고 이 개념들이 RSA 암호의 수학적 기반이 되는 이유를 이해한다.

1. 나눗셈 알고리즘

몫과 나머지

정수 a와 양의 정수 b가 주어지면 a를 b로 나눈 몫과 나머지를 이용해 a=bq+r로 나타낼 수 있다. 이때 q와 r은 유일한 정수이며 0≤r<b를 만족한다. 이것을 나눗셈 알고리즘 또는 나눗셈 정리라고 한다.

나머지의 범위를 0 이상 b 미만으로 정하는 것은 몫과 나머지의 유일성을 보장하기 위해서이다. 예를 들어 17을 5로 나누면 17=5·3+2이므로 몫은 3, 나머지는 2이다. 음의 정수도 같은 범위를 사용한다. -7=-3·3+2이므로 -7을 3으로 나눈 나머지는 2이다.

나눗셈 알고리즘을 이용한 분류

정수를 어떤 양의 정수로 나눈 나머지에 따라 여러 경우로 분류할 수 있다. 강의록의 예처럼 임의의 정수 a를 3으로 나누면 나머지는 0, 1, 2 중 하나이므로 a=3q, 3q+1, 3q+2 중 하나이다. 각 경우를 제곱하면 a²은 3k 또는 3k+1 꼴임을 확인할 수 있다.

나눗셈 알고리즘의 핵심은 단순히 나눗셈을 계산하는 것이 아니라, 모든 정수를 가능한 나머지에 따라 빠짐없이 분류하는 데 있다. 이 방식은 정수의 성질을 경우별로 증명할 때 자주 사용된다.

2. 약수와 배수

나누어떨어짐

정수 a와 b에 대해 어떤 정수 k가 존재하여 b=ak가 되면 “a가 b를 나눈다”라고 하며 a|b로 쓴다. 이때 a는 b의 약수이고 b는 a의 배수이다. a가 b를 나누지 않으면 a∤b로 나타낸다.

예를 들어 3|12는 12=3·4이므로 참이고, 5∤12는 12를 5와 정수의 곱으로 나타낼 수 없으므로 참이다. a|b라는 표기에서 왼쪽이 나누는 수, 오른쪽이 나누어지는 수라는 순서를 주의해야 한다.

나누어떨어짐의 기본 성질

조건	따라오는 결론	이유
a|b, a|c	a|(b+c)	b=ak, c=aℓ이면 b+c=a(k+ℓ)
a|b	a|bc	b=ak이면 bc=a(kc)
a|b, b|c	a|c	b=ak, c=bℓ이면 c=a(kℓ)

이 성질들은 약수 관계를 증명할 때 직접 사용된다. 특히 a|b와 a|c이면 a는 b와 c의 정수 선형결합 bx+cy도 나눈다. 이는 최대공약수와 베주 항등식으로 이어지는 중요한 관찰이다.

3. 최대공약수와 서로소

최대공약수

0이 아닌 정수 a와 b를 모두 나누는 양의 정수 가운데 가장 큰 수를 최대공약수라고 하며 gcd(a,b)로 쓴다. a와 b를 모두 나누는 수는 공약수이고, gcd(a,b)는 그 공약수 가운데 가장 크다.

gcd(a,b)=1이면 a와 b는 서로소라고 한다. 서로소라는 말은 두 수가 각각 소수라는 뜻이 아니라 공통인 양의 약수가 1뿐이라는 뜻이다. 예를 들어 8과 15는 모두 합성수이지만 gcd(8,15)=1이므로 서로소이다.

베주 항등식

베주 항등식에 따르면 d=gcd(a,b)일 때 ax+by=d를 만족하는 정수 x, y가 존재한다. 반대로 a와 b의 정수 선형결합으로 표현되는 양의 공약수 가운데 가장 작은 양의 값이 최대공약수가 된다.

특히 a와 b가 서로소인 것과 ax+by=1을 만족하는 정수 x, y가 존재하는 것은 동치이다. 이 관계는 모듈로 연산에서 역원이 존재하는 조건과 RSA 암호의 키 관계를 이해하는 데 중요하다.

시험 핵심: “a와 b가 서로소”는 gcd(a,b)=1이며, 베주 항등식으로는 ax+by=1인 정수 x, y가 존재한다는 뜻이다.

4. 유클리드 호제법

기본 원리

a=bq+r이면 gcd(a,b)=gcd(b,r)이다. a와 b의 공약수는 b와 r=a-bq의 공약수이고, 반대 방향도 성립하기 때문이다. 이 성질을 나머지가 0이 될 때까지 반복하여 최대공약수를 구하는 방법이 유클리드 호제법이다.

계산 절차

gcd(287,91)을 구해 보자.

287=91·3+14 → gcd(287,91)=gcd(91,14)

91=14·6+7 → gcd(91,14)=gcd(14,7)

14=7·2+0 → gcd(14,7)=7

나머지가 0이 된 순간의 나누는 수 7이 최대공약수이다. 큰 두 수의 모든 약수를 직접 나열하지 않아도 나머지를 반복 계산하여 빠르게 최대공약수를 얻을 수 있다는 것이 장점이다.

알고리즘 순서: 큰 수를 작은 수로 나눈다 → 두 수를 작은 수와 나머지로 바꾼다 → 나머지가 0이 될 때까지 반복한다 → 마지막 0이 아닌 나머지가 최대공약수이다.

5. 모듈로 연산과 합동

모듈로 연산

정수 n을 양의 정수 m으로 나누었을 때의 나머지를 n mod m이라고 한다. 나눗셈 알고리즘에 따라 n=mq+r이고 0≤r<m이면 n mod m=r이다. 예를 들어 25 mod 7=4이고 -3 mod 5=2이다.

모듈로 합동

정수 a와 b를 m으로 나눈 나머지가 같으면 a와 b는 법 m에 대해 합동이라고 하며 a≡b (mod m)으로 쓴다. 이는 m|(a-b)와 동치이다. 예를 들어 25≡11 (mod 7)인 이유는 25-11=14가 7의 배수이기 때문이다.

합동과 나머지는 밀접하지만 표기의 역할은 다르다. a mod m은 하나의 나머지 값을 뜻하고, a≡b (mod m)은 두 정수가 같은 나머지 부류에 속한다는 관계를 뜻한다.

합동은 동치관계

법 m에 대한 합동은 반사성, 대칭성, 추이성을 모두 만족하여 동치관계가 된다. 따라서 정수 전체는 같은 나머지를 갖는 동치류들로 분할된다. 법 5에서는 [0], [1], [2], [3], [4]의 다섯 동치류가 생긴다.

성질	합동식
반사성	a≡a (mod m)
대칭성	a≡b이면 b≡a (mod m)
추이성	a≡b, b≡c이면 a≡c (mod m)

6. 합동의 연산 법칙

합동식은 덧셈과 곱셈에 대해 보존된다. a≡b (mod m), c≡d (mod m)이면 a+c≡b+d (mod m), ac≡bd (mod m)이다. 같은 수를 더하거나 곱하는 경우에도 합동 관계가 유지되며, 자연수 k에 대해 a^k≡b^k (mod m)이다.

주어진 합동	가능한 연산
a≡b (mod m)	a+c≡b+c (mod m)
a≡b (mod m)	ac≡bc (mod m)
a≡b, c≡d (mod m)	a+c≡b+d, ac≡bd (mod m)
a≡b (mod m)	ak≡bk (mod m)

합동식의 약분

일반 등식처럼 합동식의 공통인수를 언제나 약분할 수 있는 것은 아니다. ac≡bc (mod m)에서 c를 약분해 a≡b (mod m)을 얻으려면 c와 m이 서로소인 조건이 필요하다. 예를 들어 2·1≡2·3 (mod 4)이지만 1과 3은 법 4에서 합동이 아니다.

합동식에서 덧셈·곱셈·거듭제곱은 안전하게 사용할 수 있지만 나눗셈이나 약분은 별도의 조건이 필요하다. 공통인수와 법이 서로소인지 먼저 확인한다.

7. 소수와 소인수분해

소수와 합성수

1보다 큰 자연수 p의 양의 약수가 1과 p뿐이면 p를 소수라고 한다. 1보다 큰 자연수 가운데 소수가 아닌 수는 합성수이다. 1은 소수도 합성수도 아니다.

합성수 n은 √n 이하인 소인수를 적어도 하나 갖는다. 따라서 어떤 수가 소수인지 판별할 때 n-1까지 모두 나눌 필요 없이 √n 이하의 소수로 나누어떨어지는지만 확인하면 된다. 예를 들어 101의 제곱근은 10보다 조금 크므로 2, 3, 5, 7로 나누어떨어지는지 검사하면 충분하다.

산술의 기본정리

산술의 기본정리에 따르면 1보다 큰 모든 자연수는 소수들의 곱으로 표현할 수 있고, 소인수의 순서를 제외하면 그 표현은 유일하다. 예를 들어 17640=2³·3²·5·7²이다. 이 유일성은 최대공약수, 최소공배수와 여러 정수론 계산의 기초가 된다.

에라토스테네스의 체

주어진 범위의 소수를 모두 찾으려면 에라토스테네스의 체를 사용할 수 있다. 2부터 시작하여 아직 지워지지 않은 가장 작은 수를 소수로 선택하고 그 수의 배수를 지운다. 이 과정을 √n 이하의 소수까지 반복하면 지워지지 않은 수들이 n 이하의 소수이다.

8. 소수의 무한성과 분포

소수는 무한히 많다

소수가 유한개 p₁,p₂,…,pₙ뿐이라고 가정하고 N=p₁p₂⋯pₙ+1을 만든다. N을 목록의 어떤 소수 pᵢ로 나누어도 나머지가 1이므로 어느 pᵢ도 N을 나누지 못한다. N 자체가 소수이거나 목록에 없는 소인수를 가지므로 처음의 유한성 가정과 모순된다. 따라서 소수는 무한히 많다.

메르센 소수

메르센 수는 2^p-1 꼴의 수이다. 2^p-1이 소수라면 지수 p도 소수여야 한다. 그러나 p가 소수라고 해서 2^p-1이 항상 소수인 것은 아니다. 강의록의 예처럼 2¹¹-1=2047=23·89이므로 합성수이다.

소수의 밀도

π(x)를 x 이하의 소수 개수라고 하면 소수정리에 따라 x가 충분히 클 때 π(x)≈x/ln x이다. 따라서 x 근처의 자연수를 임의로 고를 때 소수일 대략적인 확률은 1/ln x로 볼 수 있다. x가 커질수록 소수는 드물어지지만 계속 나타난다.

구분: “소수가 무한히 많다”는 존재에 관한 정리이고, π(x)≈x/ln x는 큰 범위에서 소수가 얼마나 분포하는지를 나타내는 근사 관계이다.

9. 페르마의 작은 정리

p가 소수이고 a가 p의 배수가 아니면 a^p-1≡1 (mod p)이다. 이것이 페르마의 작은 정리이다. 같은 내용을 모든 정수 a에 대해 a^p≡a (mod p)로도 표현할 수 있다.

예를 들어 p=11이고 a=7이면 7¹⁰≡1 (mod 11)이다. 따라서 7²²²의 나머지를 구할 때 지수 222를 10으로 나누어 222=10·22+2로 바꿀 수 있다. 7²²²=(7¹⁰)²²·7²≡1²²·49≡5 (mod 11)이다.

이 정리는 큰 지수의 거듭제곱을 모듈로 계산할 때 지수를 줄이는 근거를 제공하며, 소수와 합동 연산이 RSA 암호에 연결되는 핵심 원리 가운데 하나이다.

a^p-1≡1 (mod p) 형태에는 p∤a라는 조건이 필요하다. 반면 a^p≡a (mod p)는 p의 배수인 a까지 포함하여 모든 정수 a에 대해 성립한다.

10. 나머지 거듭제곱과 RSA 암호

반복 제곱법

큰 지수의 bⁿ mod m을 직접 계산하면 수가 지나치게 커진다. 나머지 거듭제곱 알고리즘은 지수 n을 이진수로 표현하고 b, b², b⁴, b⁸처럼 제곱을 반복하면서 매 단계 m으로 나눈 나머지만 유지한다. 필요한 이진 자릿수에 해당하는 값들만 곱하면 계산량을 크게 줄일 수 있다.

예를 들어 5⁶ mod 7을 계산하자. 6=(110)₂=4+2이므로 5⁶=5⁴·5²이다. 5²≡4 (mod 7), 5⁴≡4²≡2 (mod 7)이므로 5⁶≡2·4≡1 (mod 7)이다.

RSA와 소수의 관계

RSA는 큰 소수와 모듈로 거듭제곱을 이용하는 공개키 암호 방식이다. 암호화와 복호화 과정에서는 큰 지수의 나머지를 효율적으로 계산해야 하므로 반복 제곱법이 필요하다. 또한 서로소, 최대공약수, 베주 항등식과 페르마의 작은 정리 같은 정수론 개념이 키의 구성과 복호화 관계를 설명하는 기반이 된다.

RSA의 안전성은 큰 정수의 소인수분해가 계산적으로 어렵다는 점과 관련된다. 소수는 키를 만드는 중요한 재료이고, 합동식은 암호화된 값과 복호화된 값의 관계를 표현하는 언어가 된다.

핵심 연결: 큰 소수 선택 → 서로소와 최대공약수 확인 → 모듈로 역원 관계 구성 → 반복 제곱으로 큰 거듭제곱의 나머지 계산이라는 흐름으로 정수론 개념이 RSA에 활용된다.

핵심 개념 정리

나눗셈 알고리즘은 a=bq+r, 0≤r<b인 유일한 몫과 나머지를 보장한다. a|b는 b가 a와 어떤 정수의 곱임을 뜻하고, gcd(a,b)는 두 수의 가장 큰 양의 공약수이다. 유클리드 호제법은 gcd(a,b)=gcd(b,r)을 반복하여 최대공약수를 빠르게 구한다.

a≡b (mod m)은 m|(a-b), 즉 a와 b가 m으로 나눈 나머지가 같다는 뜻이다. 합동은 동치관계이며 덧셈·곱셈·거듭제곱에 대해 보존된다. 단, 공통인수를 약분하려면 그 인수와 법 m이 서로소인지 확인해야 한다.

소수는 1과 자기 자신만을 양의 약수로 갖는 1보다 큰 자연수이다. 모든 1보다 큰 자연수는 순서를 제외하면 유일한 소인수분해를 갖고, 소수는 무한히 많다. 페르마의 작은 정리와 반복 제곱법은 큰 모듈로 거듭제곱을 효율적으로 계산하게 하며 RSA 암호의 수학적 기반이 된다.

최종 정리: 정수론의 중심에는 나누어떨어짐과 나머지가 있다. 최대공약수, 합동, 소수, 모듈로 거듭제곱은 서로 분리된 개념이 아니라 큰 정수의 계산과 공개키 암호를 가능하게 하는 하나의 연결된 체계이다.

예상문제 20선

1. 나눗셈 알고리즘에서 a=bq+r일 때 나머지 r의 범위는?

① -b<r<b ② 0<r≤b ③ 0≤r≤b ④ 0≤r<b

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
나머지는 0 이상이고 나누는 양의 정수 b보다 작아야 한다. 이 조건에서 몫과 나머지가 유일해진다.

2. 정수의 나누어떨어짐 a|b의 뜻은?

① a=bk인 정수 k가 존재한다. ② b=ak인 정수 k가 존재한다. ③ a와 b가 반드시 소수이다. ④ a를 b로 나눈 나머지가 1이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
a|b는 어떤 정수 k가 존재하여 b=ak로 쓸 수 있다는 뜻이다. a가 나누는 수이고 b가 나누어지는 수이다.

3. a|b이고 a|c일 때 반드시 성립하는 것은?

① a|(b+c) ② b|a ③ c|a ④ b|c

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
b=ak, c=aℓ로 쓰면 b+c=a(k+ℓ)이므로 a는 b+c를 나눈다.

4. gcd(a,b)=1의 의미는?

① a와 b가 같은 수이다. ② a와 b가 모두 소수이다. ③ a와 b가 서로소이다. ④ a가 b의 배수이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
최대공약수가 1인 두 정수를 서로소라고 한다. 각 수가 소수일 필요는 없다.

5. a와 b가 서로소임을 나타내는 베주 항등식은?

① ax+by=1인 정수 x,y가 존재한다. ② ax-by=0인 자연수 x,y만 존재한다. ③ a+b=1이다. ④ ab=1이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
gcd(a,b)=1인 것과 ax+by=1을 만족하는 정수 x,y가 존재하는 것은 동치이다.

6. 유클리드 호제법의 핵심 관계는?

① gcd(a,b)=a+b ② gcd(a,b)=ab ③ gcd(a,b)=gcd(a,q) ④ a=bq+r이면 gcd(a,b)=gcd(b,r)

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
나눗셈의 나머지 r을 이용해 두 수를 b와 r로 바꾸어도 최대공약수는 변하지 않는다.

7. 유클리드 호제법으로 gcd(287,91)을 구한 결과는?

① 14 ② 7 ③ 6 ④ 1

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
287=91·3+14, 91=14·6+7, 14=7·2이므로 마지막 0이 아닌 나머지는 7이다.

8. 25 mod 7의 값은?

① 2 ② 3 ③ 4 ④ 5

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
25=7·3+4이고 0≤4<7이므로 25 mod 7=4이다.

9. a≡b (mod m)과 동치인 조건은?

① a+b가 m의 배수이다. ② m|(a-b) ③ a가 b를 나눈다. ④ a=b만 가능하다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
법 m에서 합동이라는 것은 두 수의 차 a-b가 m의 배수라는 뜻이며, 두 수의 나머지가 같다는 뜻이다.

10. 법 m에 대한 합동 관계가 만족하는 관계의 성질은?

① 반사성·대칭성·추이성 ② 대칭성만 ③ 반사성·비대칭성 ④ 추이성을 만족하지 않는다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
합동은 반사성, 대칭성, 추이성을 모두 만족하므로 정수 집합 위의 동치관계이다.

11. a≡b, c≡d (mod m)일 때 일반적으로 옳지 않은 것은?

① a+c≡b+d (mod m) ② ac≡bd (mod m) ③ a-c≡b-d (mod m) ④ 조건 없이 a/c≡b/d (mod m)

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
합동식의 덧셈·뺄셈·곱셈은 보존되지만 나눗셈이나 약분에는 역원 또는 서로소 조건이 필요하다.

12. ac≡bc (mod m)에서 c를 약분하여 a≡b (mod m)을 얻기 위한 충분한 조건은?

① c=m ② c가 짝수이다. ③ c와 m이 서로소이다. ④ a와 b가 소수이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
c와 m이 서로소이면 c는 법 m에서 역원을 가지므로 양변에서 c를 약분할 수 있다.

13. 소수의 정의로 옳은 것은?

① 0보다 큰 모든 정수 ② 1과 자기 자신 외에도 약수가 많은 수 ③ 1보다 크고 양의 약수가 1과 자기 자신뿐인 자연수 ④ 모든 홀수

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
소수는 1보다 큰 자연수 가운데 양의 약수가 1과 자기 자신뿐인 수이다. 1은 소수가 아니다.

14. 합성수 n의 소수 판별에서 확인하면 충분한 약수의 범위는?

① n보다 큰 소수 ② 항상 2만 ③ n부터 2n까지의 수 ④ √n 이하의 소수

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
합성수라면 적어도 하나의 소인수가 √n 이하에 존재한다. 따라서 √n 이하의 소수로 나누어지는지 확인하면 된다.

15. 산술의 기본정리가 말하는 내용은?

① 1보다 큰 모든 자연수의 소인수분해는 순서를 제외하면 유일하다. ② 모든 자연수는 소수이다. ③ 소수는 유한개이다. ④ 모든 홀수는 메르센 소수이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
산술의 기본정리에 따라 1보다 큰 자연수는 소수들의 곱으로 표현되며 그 표현은 소인수 순서를 제외하면 유일하다.

16. 에라토스테네스의 체의 주된 용도는?

① 최대공약수 하나를 구하는 것 ② 주어진 범위의 소수들을 찾는 것 ③ 모든 합동식을 약분하는 것 ④ RSA 암호문을 직접 해독하는 것

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
에라토스테네스의 체는 작은 소수의 배수들을 차례로 지워 주어진 범위의 소수를 모두 찾는 알고리즘이다.

17. 2^p-1이 소수일 때 지수 p에 대해 반드시 옳은 것은?

① p는 짝수이다. ② p는 합성수이다. ③ p=1이다. ④ p는 소수이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
2^p-1이 소수라면 p도 소수여야 한다. 그러나 p가 소수라는 조건만으로 2^p-1이 항상 소수가 되는 것은 아니다.

18. 소수정리에 따른 π(x)의 근삿값은?

① x/ln x ② ln x/x ③ x² ④ 2x

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
x가 충분히 클 때 x 이하의 소수 개수 π(x)는 x/ln x에 가까워진다.

19. p가 소수이고 p∤a일 때 페르마의 작은 정리는?

① a^p≡1 (mod p) ② a^(p+1)≡0 (mod p) ③ a^(p-1)≡1 (mod p) ④ a²≡a (mod p)

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
p가 소수이고 a가 p의 배수가 아니면 a^(p-1)≡1 (mod p)이다.

20. 나머지 거듭제곱 알고리즘에서 지수를 이진수로 표현하는 주된 이유는?

① 나머지를 항상 0으로 만들기 위해 ② 반복 제곱으로 필요한 거듭제곱만 빠르게 조합하기 위해 ③ 소수를 합성수로 바꾸기 위해 ④ 최대공약수 계산을 생략하기 위해

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
지수를 이진수로 나타내면 b, b², b⁴, b⁸처럼 반복 제곱한 값 중 필요한 것만 곱해 큰 거듭제곱의 나머지를 효율적으로 구할 수 있다.