정수론이란 제목이 말해주듯이 정수의 성질을 연구하는 학문입니다. 정수는 여러 종류의 수 체계 중에서 가장 기본인 것처럼, 정수론은 수학의 가장 기본이 되는 분야입니다. 실제로 초 ․ 중 ‧ 고등학교 과정의 수와 연산, 문자와 식의 영역에서 다루는 소인수분해, 최대공약수, 최소공배수, 다항식의 곱셈공식, 인수분해, 약수와 배수, 나머지정리, 항등식, 다항식의 인수분해 등이 정수론의 주요 주제입니다.

피타고라스나 유클리드에 의하여 기원전 500년경부터 학문적 기초가 정립되었으며, 현대 정수론은 ‘마지막 정리’로 유명한 페르마로부터 시작되어, 오일러, 가우스, 힐베르트 등을 거치면서 발전해 왔습니다. 정수론의 연구 주제는 매우 세분화되고 다양해졌지만, 큰틀에서 볼 때 소수 연구와 정수계수 방정식풀이 연구로 양분할 수 있습니다. 한편 연구 방법에 따라 해석적, 대수적, 산술적 정수론으로 분류하기도 합니다. 가우스는 학문적 아름다움과 가치로 인해 정수론을 수학의 여왕이라 부르기까지 했으며, 순수수학 중에서도 가장 순수한 분야라고 오랫동안 인식되어 왔습니다. 그러나 1950년이 이후 컴퓨터의 발전과 더불어 암호학이나 부호이론 등에의 응용성이 크게 부각되고 있습니다.

저자는 오랫동안 2, 3학년 대학생들에게 정수론을 강의해 왔습니다. 대학 환경이 시시각각으로 변화하는 상황에서 고등학교 과정의 연계성을 고려한 교재가 필요하게 되었습니다. 또한 정수론의 내용이 변한 것은 아니지만 전통적으로 이론과 엄밀한 증명을 요구하던 내용에서, 조금은 직관적인 사고와 추론을 기르는 강의로 바꾸어야 한다는 당위성도 생겼습니다. 아울러 정수이론의 응용으로서 암호론을 강조할 필요도 생겼습니다. 이 책은 기초정수론을 위한 교재입니다. 학생들 눈높이에 맞추기 위해 어렵고 복잡한 증명 대신에 많은 예제를 다룸으로서 학생들이 단계별로 접근할 수 있게 했습니다. 학생들 쉽게 읽을 수 있게 구성하면서, 스스로 해결할 수 있는 수준의 예제는 교재에 빈 여백을 주어 자신의 아이디어를 쓸 수 있도록 했습니다. 연습문제의 해답을 충실히 넣었습니다.

Chapter 01 정수 1

1.1 정수의 성질(Integer) • 1

1.2 최대공약수와 최소공배수(GCD, LCM) • 4

1.3 배수 판정(Multiple) • 11

1.4 귀납법(Mathematical induction) • 15

Chapter 02 소인수분해 17

2.1 소수(Prime number) • 17

2.2 소인수분해(Prime factorization) • 19

Chapter 03 소수 판정법 24

3.1 소수 판정의 방법들(Primality test) • 24

3.2 암호에서의 소수 판정(Primality test in cryptography) • 34

3.3 Maple 패키지에서의 소수 정리들(Maple for primes) • 37

3.4 재미있는 소수 이야기 • 41

Chapter 04 디오판토스 방정식 45

4.1 방정식 풀이(Solving equation) • 46

4.2 고차방정식 풀이(Solving higher degree polynomial) • 48

4.3 디오판토스 방정식(Diophantos equation) • 51

4.4 디오판토스 연립방정식(System of Diophantos equations) • 59

Chapter 05 합동 68

5.1 합동식(Congruence equation) • 68

5.2 잉여류(Residue class) • 75

5.3 오일러 phi 함수(Euler phi function) • 80

5.4 합동의 응용(Application of congruence) • 85

Chapter 06 정수론적 함수 89

6.1 정수론적 함수(Number theoretic function) • 89

6.2 가우스 함수(Gauss function) • 95

6.3 뫼비우스 함수(Möbious function) • 97

Chapter 07 페르마 정리와 오일러 정리 101

7.1 윌슨 정리(Wilson theorem) • 101

7.2 페르마 정리(Fermat theorem) • 108

7.3 오일러 정리(Euler theorem) • 113

7.4 페르마와 오일러 정리에 대한 대수적 접근(Algebraic view) • 117

7.5 페르마 정리를 사용한 소수 판정(Primality test by Fermat theorem) • 121

7.6 카마이클 수(Carmichael number) • 126

Chapter 08 합동방정식 131

8.1 합동방정식 풀기(Solving congruence equation) • 132

8.2 연립일차합동식(System of linear congruence equations) • 136

8.3 고차합동방정식  ? ? ≡ ? ????  ?(Higher congruence equation) • 142

8.4 합동식 응용(Application of congruence equation) • 144

Chapter 09 원시근 147

9.1 위수(Order) • 147

9.2 원시근(Primitive root) • 152

9.3 지수(Index) • 157

Chapter 10 이차합동방정식 I 163

10.1 이차방정식의 개념과 풀이과정(Solving quadratic equation) • 163

10.2 이차 잉여(Quadratic residue) • 165

10.3 르장드르 기호(Legendre symbol) • 175

10.4 이차 잉여의 상반법칙(Quadratic reciprocity) • 188

Chapter 11 이차합동방정식 II 199

11.1 야코비 기호(Jacobi symbol) • 199

11.2 크로네커 기호(Kronecker symbol) • 205

11.3 소수 거듭제곱에 대한 이차합동방정식 • 211

Chapter 12 연분수 218

12.1 유한단순연분수(Finite simple continued fraction) • 220

12.2 무한단순연분수(Infinite simple continued fraction) • 233

12.3 연분수의 응용(Application of continued fraction) • 245

Chapter 13 피보나치수열, 피타고라스 세 쌍, 펠 수열 259

13.1 피보나치수열(Fibonacci sequence) • 259

13.2 피타고라스 세 쌍(Pythagorean triple) • 268

13.3 피타고라스 세 쌍과 피보나치수열 • 273

13.4 펠 수와 펠 수열(Pell number and sequence) • 276

Chapter 14 암호론 I 281

14.1 암호의 역사(History of cryptography) • 281

14.2 RSA 암호체계(RSA cryptography) • 284

14.3 빠른 지수법(Fast exponentiation) • 290

14.4 배낭암호(Knapsack cryptography) • 293

Chapter 15 암호론 II 302

15.1 행렬을 이용한 암호 • 302

15.2 함수를 이용한 암호 • 305

15.3 힐 암호(Hill cryptosystem) • 306

15.4 암호이론의 실생활에서의 응용(Application of cryptography) • 313

Chapter 16 흥미로운 수 I 318

16.1 완전수(Perfect number) • 318

16.2 메르센 수와 메르센 소수(Mersenne number, Mersenne prime) • 330

16.3 Maple 패키지에서 완전수 찾기(Maple for perfect number) • 338

16.4 완전수의 여러 변형들(Some perfect numbers) • 340

Chapter 17 흥미로운 수 II 345

17.1 페르마 수(Fermat number) • 345

17.2 페르마 수와 작도 가능 다각형(Fermat number and constructible polygon) • 352

17.3 쌍둥이 소수(Twin prime) • 354

Chapter 18 여러 가지 정수표 357

18.1 1∼10,000까지의 소수표 • 357

18.2 소수개수 정리:1부터 사이의 소수의 개수 • 360

18.3 소수 분포의 그래프 • 361

18.4 오일러 함수 ??? (? ≤  ≤ ???)과 약수의 목록 • 362

18.5 원시근과 지수 표 • 365

18.6 ? 의 여러 가지 표현 • 366

18.7 자연로그  의 여러 가지 표현 • 367

■ 연습문제 해답 • 369