정수론 (Number Theory)

정수론은 정수, 특히 소수의 성질을 연구한다. 질문은 초등학생도 이해할 만큼 단순하지만 답은 매우 깊은 경우가 많아 ‘수학의 여왕’이라고도 불린다. 오늘날 인터넷 보안에 쓰이는 암호(RSA 등)가 정수론에 바탕을 둔다.

무엇을 배우나요

나누어떨어짐과 소수

정수 $a$, $b$($b>0$)에 대해 $a=bq+r$, $0\le r<b$인 몫 $q$와 나머지 $r$이 하나씩 존재한다(나눗셈 정리). 1보다 크고 1과 자기 자신만을 약수로 갖는 수를 소수라 한다.

최대공약수와 유클리드 호제법

$\gcd(a,b)=\gcd(b,\ a \bmod b)$를 반복하면 최대공약수를 빠르게 구할 수 있다. 또 $\gcd(a,b)=ax+by$를 만족하는 정수 $x,y$가 존재한다(베주 항등식).

합동식

$a\equiv b \pmod{n}$은 $n$이 $a-b$를 나눈다는 뜻이다. 시계처럼 나머지만 보는 계산이다.

$$a^{p-1}\equiv 1 \pmod{p} \quad (p\text{는 소수},\ p\nmid a)$$

이것이 페르마의 소정리이며, 오일러 정리 $a^{\varphi(n)}\equiv1 \pmod n$로 일반화된다.

더 나아가

이차잉여와 이차상호법칙, 디오판토스 방정식(정수해를 찾는 방정식), 소수의 분포(소수 정리 $\pi(x)\sim \frac{x}{\ln x}$), 해석적 정수론과 대수적 정수론으로 이어진다.

대표 정리

  • 산술의 기본정리: 1보다 큰 모든 정수는 소수의 곱으로 나타낼 수 있고, 그 방법은 순서를 무시하면 하나뿐이다.
  • 유클리드의 정리: 소수는 무한히 많다.
  • 중국인의 나머지 정리: 서로소인 법들에 대한 연립 합동식은 곱의 법에 대해 해가 하나뿐이다.

선수 지식

중등 약수와 배수, 소인수분해. 대학 과정은 수학기초론(증명)과 대수학(군, 환)이 도움이 된다.

학습 로드맵

  • 약수와 배수 → 소수와 소인수분해 → 최대공약수
  • 합동식 → 페르마·오일러 정리 → 중국인의 나머지 정리
  • 이차잉여 → 디오판토스 방정식 → 암호에의 응용

이 항목의 내용

  1. 약수와 배수
  2. 소수와 소인수분해
  3. 최대공약수와 유클리드 호제법
  4. 합동식
  5. 페르마·오일러 정리
  6. 중국인의 나머지 정리
  7. 이차잉여
  8. 디오판토스 방정식
  9. 암호에의 응용
알림: 보호된 콘텐츠입니다.