정수를 나누면 몫과 나머지가 나옵니다. 이 단순한 사실에서 최대공약수, 나머지 연산(합동), 페르마 소정리가 나오고, 결국 인터넷 보안의 바탕인 RSA 암호에 이릅니다. 고등학교에서 배운 약수·배수를 계산 도구로 발전시키는 강입니다.
정수론은 정수의 나눗셈을 다룹니다. 오래된 분야지만 오늘날 암호(인터넷의 HTTPS)가 바로 이 강의 정리 위에 서 있습니다. 5강의 동치관계로 정수를 나머지별로 묶는 합동이 중심 도구입니다.
10.1 나눗셈 정리
정리 10.1 (나눗셈 정리). 정수 a a a d d d a = d q + r a = dq + r a = d q + r 0 ≤ r < d 0 \le r < d 0 ≤ r < d q q q r r r q q q 몫 (quotient), r r r 나머지 (remainder)라 하고 r = a m o d d r = a \bmod d r = a mod d
증명 개요. 존재: 집합 { a − d q ∣ q ∈ Z } ∩ { 0 , 1 , 2 , … } \{a - dq \mid q \in \mathbb{Z}\} \cap \{0, 1, 2, \dots\} { a − d q ∣ q ∈ Z } ∩ { 0 , 1 , 2 , … } r r r r < d r < d r < d r ≥ d r \ge d r ≥ d r − d r - d r − d d q + r = d q ′ + r ′ dq + r = dq' + r' d q + r = d q ′ + r ′ d ∣ r − r ′ d \mid r - r' d ∣ r − r ′ ∣ r − r ′ ∣ < d |r - r'| < d ∣ r − r ′ ∣ < d r = r ′ r = r' r = r ′
음수에도 나머지는 0 이상입니다: − 7 = 3 ⋅ ( − 3 ) + 2 -7 = 3 \cdot (-3) + 2 − 7 = 3 ⋅ ( − 3 ) + 2 − 7 m o d 3 = 2 -7 \bmod 3 = 2 − 7 mod 3 = 2
10.2 최대공약수와 유클리드 호제법
정의 10.2. 정수 a a a b b b 최대공약수 (greatest common divisor, gcd) gcd ( a , b ) \gcd(a, b) g cd( a , b ) gcd ( a , b ) = 1 \gcd(a, b) = 1 g cd( a , b ) = 1 a a a b b b 서로소 (coprime)입니다.
정리 10.3. a = b q + r a = bq + r a = b q + r gcd ( a , b ) = gcd ( b , r ) \gcd(a, b) = \gcd(b, r) g cd( a , b ) = g cd( b , r )
증명. d d d a a a b b b r = a − b q r = a - bq r = a − b q d d d b b b r r r a = b q + r a = bq + r a = b q + r
이 정리를 되풀이하면 유클리드 호제법 (Euclidean algorithm)이 됩니다.
예제 10.4. gcd ( 252 , 198 ) \gcd(252, 198) g cd( 252 , 198 )
252 = 198 ⋅ 1 + 54 , 198 = 54 ⋅ 3 + 36 , 54 = 36 ⋅ 1 + 18 , 36 = 18 ⋅ 2 + 0 252 = 198 \cdot 1 + 54, \quad 198 = 54 \cdot 3 + 36, \quad 54 = 36 \cdot 1 + 18, \quad 36 = 18 \cdot 2 + 0 252 = 198 ⋅ 1 + 54 , 198 = 54 ⋅ 3 + 36 , 54 = 36 ⋅ 1 + 18 , 36 = 18 ⋅ 2 + 0 마지막으로 0이 아닌 나머지 18이 최대공약수입니다. 나머지가 매번 줄어들므로 반드시 끝나고, 두 단계마다 나머지가 절반 아래로 줄어들어 매우 빠릅니다.
10.3 베주 항등식
정리 10.5 (베주 항등식). 정수 a a a b b b gcd ( a , b ) = a x + b y \gcd(a, b) = ax + by g cd( a , b ) = a x + b y x x x y y y
증명 (구성). 유클리드 호제법을 거꾸로 거슬러 올라갑니다. 예제 10.4에서
18 = 54 − 36 = 54 − ( 198 − 54 ⋅ 3 ) = 4 ⋅ 54 − 198 = 4 ( 252 − 198 ) − 198 = 4 ⋅ 252 − 5 ⋅ 198 18 = 54 - 36 = 54 - (198 - 54 \cdot 3) = 4 \cdot 54 - 198 = 4(252 - 198) - 198 = 4 \cdot 252 - 5 \cdot 198 18 = 54 − 36 = 54 − ( 198 − 54 ⋅ 3 ) = 4 ⋅ 54 − 198 = 4 ( 252 − 198 ) − 198 = 4 ⋅ 252 − 5 ⋅ 198 이므로 x = 4 x = 4 x = 4 y = − 5 y = -5 y = − 5 확장 유클리드 호제법 (extended Euclidean algorithm)이라 합니다. □
따름정리 10.6. a a a b b b a x + b y = 1 ax + by = 1 a x + b y = 1 x x x y y y
10.4 합동
정의 10.7 (합동). m ∣ a − b m \mid a - b m ∣ a − b a a a b b b m m m a ≡ b ( m o d m ) a \equiv b \pmod m a ≡ b ( mod m ) a m o d m = b m o d m a \bmod m = b \bmod m a mod m = b mod m
합동은 동치관계이고(5강의 예제 5.10), 동치류는 나머지 0 , 1 , … , m − 1 0, 1, \dots, m-1 0 , 1 , … , m − 1
정리 10.8. a ≡ b a \equiv b a ≡ b c ≡ d ( m o d m ) c \equiv d \pmod m c ≡ d ( mod m ) a + c ≡ b + d a + c \equiv b + d a + c ≡ b + d a c ≡ b d ( m o d m ) ac \equiv bd \pmod m a c ≡ b d ( mod m )
증명. a = b + k m a = b + km a = b + k m c = d + l m c = d + lm c = d + l m a c = b d + ( b l + d k + k l m ) m ac = bd + (bl + dk + klm)m a c = b d + ( b l + d k + k l m ) m
그래서 큰 수의 나머지는 중간중간 나머지를 취해 계산해도 됩니다.
예제 10.9. 7 100 m o d 5 7^{100} \bmod 5 7 100 mod 5 7 ≡ 2 7 \equiv 2 7 ≡ 2 2 4 = 16 ≡ 1 ( m o d 5 ) 2^4 = 16 \equiv 1 \pmod 5 2 4 = 16 ≡ 1 ( mod 5 ) 7 100 ≡ 2 100 = ( 2 4 ) 25 ≡ 1 7^{100} \equiv 2^{100} = (2^4)^{25} \equiv 1 7 100 ≡ 2 100 = ( 2 4 ) 25 ≡ 1
10.5 모듈러 역원
정의 10.10. a a ˉ ≡ 1 ( m o d m ) a\bar a \equiv 1 \pmod m a a ˉ ≡ 1 ( mod m ) a ˉ \bar a a ˉ a a a m m m 역원 (inverse)이라 합니다.
정리 10.11. a a a m m m gcd ( a , m ) = 1 \gcd(a, m) = 1 g cd( a , m ) = 1
증명. gcd ( a , m ) = 1 \gcd(a, m) = 1 g cd( a , m ) = 1 a x + m y = 1 ax + my = 1 a x + m y = 1 a x ≡ 1 ax \equiv 1 a x ≡ 1 x x x a x ≡ 1 ax \equiv 1 a x ≡ 1 a x − 1 = m y ax - 1 = my a x − 1 = m y a a a m m m
m m m p p p 1 , … , p − 1 1, \dots, p-1 1 , … , p − 1 { 0 , 1 , … , p − 1 } \{0, 1, \dots, p-1\} { 0 , 1 , … , p − 1 }
n을 바꾸면 나머지 연산의 덧셈표·곱셈표와, 0이 아닌 원소마다 곱셈 역원이 있는지가 바뀝니다 이 위젯은 JavaScript가 필요합니다
예제 10.12. 3 x ≡ 4 ( m o d 7 ) 3x \equiv 4 \pmod 7 3 x ≡ 4 ( mod 7 ) 3 ⋅ 5 = 15 ≡ 1 3 \cdot 5 = 15 \equiv 1 3 ⋅ 5 = 15 ≡ 1 3 ˉ = 5 \bar 3 = 5 3 ˉ = 5 x ≡ 20 ≡ 6 ( m o d 7 ) x \equiv 20 \equiv 6 \pmod 7 x ≡ 20 ≡ 6 ( mod 7 )
10.6 페르마 소정리
정리 10.13 (페르마 소정리). p p p p ∤ a p \nmid a p ∤ a a p − 1 ≡ 1 ( m o d p ) a^{p-1} \equiv 1 \pmod p a p − 1 ≡ 1 ( mod p )
증명. a , 2 a , … , ( p − 1 ) a a, 2a, \dots, (p-1)a a , 2 a , … , ( p − 1 ) a p p p i a ≡ j a ia \equiv ja ia ≡ j a a a a i ≡ j i \equiv j i ≡ j 1 , … , p − 1 1, \dots, p-1 1 , … , p − 1 a p − 1 ( p − 1 ) ! ≡ ( p − 1 ) ! ( m o d p ) a^{p-1}(p-1)! \equiv (p-1)! \pmod p a p − 1 ( p − 1 )! ≡ ( p − 1 )! ( mod p ) ( p − 1 ) ! (p-1)! ( p − 1 )! p p p
예제 10.14. 3 100 m o d 11 3^{100} \bmod 11 3 100 mod 11 3 10 ≡ 1 3^{10} \equiv 1 3 10 ≡ 1 3 100 = ( 3 10 ) 10 ≡ 1 3^{100} = (3^{10})^{10} \equiv 1 3 100 = ( 3 10 ) 10 ≡ 1
10.7 RSA의 원리
두 큰 소수 p p p q q q n = p q n = pq n = pq φ = ( p − 1 ) ( q − 1 ) \varphi = (p-1)(q-1) φ = ( p − 1 ) ( q − 1 ) gcd ( e , φ ) = 1 \gcd(e, \varphi) = 1 g cd( e , φ ) = 1 e e e e d ≡ 1 ( m o d φ ) ed \equiv 1 \pmod \varphi e d ≡ 1 ( mod φ ) d d d 정리 10.11 ). ( n , e ) (n, e) ( n , e ) d d d
암호화: c = m e m o d n c = m^e \bmod n c = m e mod n
복호화: m = c d m o d n m = c^d \bmod n m = c d mod n
복호화가 맞는 이유는 e d = 1 + k φ ed = 1 + k\varphi e d = 1 + k φ m e d ≡ m ( m o d n ) m^{ed} \equiv m \pmod n m e d ≡ m ( mod n ) n n n p p p q q q e e e d d d
예제 10.15. p = 5 p = 5 p = 5 q = 11 q = 11 q = 11 n = 55 n = 55 n = 55 φ = 40 \varphi = 40 φ = 40 e = 3 e = 3 e = 3 3 d ≡ 1 ( m o d 40 ) 3d \equiv 1 \pmod{40} 3 d ≡ 1 ( mod 40 ) d = 27 d = 27 d = 27 m = 2 m = 2 m = 2 c = 2 3 = 8 c = 2^3 = 8 c = 2 3 = 8 8 27 m o d 55 = 2 8^{27} \bmod 55 = 2 8 27 mod 55 = 2
쓰이는 곳. RSA와 타원곡선 암호(HTTPS), 해시 함수, 난수 생성, 오류 검출 부호(바코드, 카드 번호의 검증 숫자)가 이 강의 나머지 연산을 씁니다.
10.8 이 장의 요약
유클리드 호제법: gcd ( a , b ) = gcd ( b , a m o d b ) \gcd(a, b) = \gcd(b, a \bmod b) g cd( a , b ) = g cd( b , a mod b )
역원은 서로소일 때만 있고, 확장 유클리드 호제법으로 구합니다.
페르마 소정리 a p − 1 ≡ 1 ( m o d p ) a^{p-1} \equiv 1 \pmod p a p − 1 ≡ 1 ( mod p )
문제
10.1 [계산] · 확인 문제
gcd ( 1071 , 462 ) \gcd(1071, 462) g cd( 1071 , 462 )
정답 풀이 1071 = 462 ⋅ 2 + 147 1071 = 462 \cdot 2 + 147 1071 = 462 ⋅ 2 + 147 462 = 147 ⋅ 3 + 21 462 = 147 \cdot 3 + 21 462 = 147 ⋅ 3 + 21 147 = 21 ⋅ 7 147 = 21 \cdot 7 147 = 21 ⋅ 7
10.2 [계산] · 확인 문제
gcd ( 252 , 198 ) = 252 x + 198 y \gcd(252, 198) = 252x + 198y g cd( 252 , 198 ) = 252 x + 198 y
값
답
gcd \gcd g cd[?]
x x x [?]
y y y [?]
정답 풀이 본문 정리 10.5 의 계산으로 18 = 4 ⋅ 252 − 5 ⋅ 198 18 = 4 \cdot 252 - 5 \cdot 198 18 = 4 ⋅ 252 − 5 ⋅ 198
10.3 [계산] · 확인 문제
7 7 7 26 26 26
힌트 1 7 x + 26 y = 1 7x + 26y = 1 7 x + 26 y = 1
정답 풀이 26 = 7 ⋅ 3 + 5 26 = 7 \cdot 3 + 5 26 = 7 ⋅ 3 + 5 7 = 5 + 2 7 = 5 + 2 7 = 5 + 2 5 = 2 ⋅ 2 + 1 5 = 2 \cdot 2 + 1 5 = 2 ⋅ 2 + 1 1 = 5 − 2 ⋅ 2 = 5 − 2 ( 7 − 5 ) = 3 ⋅ 5 − 2 ⋅ 7 = 3 ( 26 − 3 ⋅ 7 ) − 2 ⋅ 7 = 3 ⋅ 26 − 11 ⋅ 7 1 = 5 - 2 \cdot 2 = 5 - 2(7 - 5) = 3 \cdot 5 - 2 \cdot 7 = 3(26 - 3 \cdot 7) - 2 \cdot 7 = 3 \cdot 26 - 11 \cdot 7 1 = 5 − 2 ⋅ 2 = 5 − 2 ( 7 − 5 ) = 3 ⋅ 5 − 2 ⋅ 7 = 3 ( 26 − 3 ⋅ 7 ) − 2 ⋅ 7 = 3 ⋅ 26 − 11 ⋅ 7 7 ˉ ≡ − 11 ≡ 15 \bar 7 \equiv -11 \equiv 15 7 ˉ ≡ − 11 ≡ 15 7 ⋅ 15 = 105 = 4 ⋅ 26 + 1 7 \cdot 15 = 105 = 4 \cdot 26 + 1 7 ⋅ 15 = 105 = 4 ⋅ 26 + 1
10.4 [계산] · 확인 문제
2 100 m o d 13 2^{100} \bmod 13 2 100 mod 13
힌트 1 페르마 소정리로 2 12 ≡ 1 ( m o d 13 ) 2^{12} \equiv 1 \pmod{13} 2 12 ≡ 1 ( mod 13 ) 100 = 12 ⋅ 8 + 4 100 = 12 \cdot 8 + 4 100 = 12 ⋅ 8 + 4
정답 풀이 2 100 = ( 2 12 ) 8 ⋅ 2 4 ≡ 16 ≡ 3 ( m o d 13 ) 2^{100} = (2^{12})^8 \cdot 2^4 \equiv 16 \equiv 3 \pmod{13} 2 100 = ( 2 12 ) 8 ⋅ 2 4 ≡ 16 ≡ 3 ( mod 13 )
10.5 [계산]
5 x ≡ 3 ( m o d 17 ) 5x \equiv 3 \pmod{17} 5 x ≡ 3 ( mod 17 )
정답 풀이 5 ⋅ 7 = 35 ≡ 1 5 \cdot 7 = 35 \equiv 1 5 ⋅ 7 = 35 ≡ 1 5 ˉ = 7 \bar 5 = 7 5 ˉ = 7 x ≡ 21 ≡ 4 ( m o d 17 ) x \equiv 21 \equiv 4 \pmod{17} x ≡ 21 ≡ 4 ( mod 17 ) 5 ⋅ 4 = 20 ≡ 3 5 \cdot 4 = 20 \equiv 3 5 ⋅ 4 = 20 ≡ 3
10.6 [계산]
예제 10.15의 RSA(n = 55 n = 55 n = 55 e = 3 e = 3 e = 3 m = 7 m = 7 m = 7 c c c
정답 풀이 7 3 = 343 = 55 ⋅ 6 + 13 7^3 = 343 = 55 \cdot 6 + 13 7 3 = 343 = 55 ⋅ 6 + 13 c = 13 c = 13 c = 13 13 27 m o d 55 = 7 13^{27} \bmod 55 = 7 1 3 27 mod 55 = 7
10.7 [증명]
정수 a a a s s s a ≡ s ( m o d 9 ) a \equiv s \pmod 9 a ≡ s ( mod 9 )
풀이 a = d k 10 k + ⋯ + d 1 ⋅ 10 + d 0 a = d_k 10^k + \cdots + d_1 \cdot 10 + d_0 a = d k 1 0 k + ⋯ + d 1 ⋅ 10 + d 0 10 ≡ 1 ( m o d 9 ) 10 \equiv 1 \pmod 9 10 ≡ 1 ( mod 9 ) 정리 10.8 로 10 i ≡ 1 10^i \equiv 1 1 0 i ≡ 1 a ≡ d k + ⋯ + d 1 + d 0 = s ( m o d 9 ) a \equiv d_k + \cdots + d_1 + d_0 = s \pmod 9 a ≡ d k + ⋯ + d 1 + d 0 = s ( mod 9 )