Overview

Number Theory(정수론)은 정수와 그 속성에 대한 이론이다. 개념 자체는 대부분 초,중학교 수학에서 배웠을 것이다. 이를 이론으로 정리하였다.

Divisibility

• Divide: $a$와 $b$가 정수이고 $a ≠ 0$일 때, $b = ac$가 되는 정수 $c$가 존재하면 $a$는 $b$를 나눈다고 한다.
• factor, multiple: $a$가 $b$를 나누면 $a$는 $b$의 factor(인수)라고 하고, $b$는 $a$의 multiple(배수)라고 한다.
• $a \mid b$: $a$가 $b$를 나눈다는 의미.
• $a \nmid b$: $a$가 $b$를 나누지 않는다는 의미.

Divisibility Theorem

정수 a, b, c에 대해,

• $a\mid b$이고 $a\mid c$라면, $a\mid (b+c)$이다.
  • e.g. 3 | 6 and 3 | 9, so 3 | 15
• $a\mid b$라면, 모든 $c$에 대해 $a\mid bc$이다.
  • e.g. 5 | 10, so 5 | 20, 5 | 30, 5 | 40, …
• $a\mid b$이고 $b\mid c$라면, $a\mid c$이다.
  • e.g. 4 | 8 and 8 | 24, so 4 | 24

Primes

Prime(소수)는 1보다 크고, 1과 자기 자신 만을 약수로 가지는 양의 정수를 말한다.

Composite(합성수)는 1보다 크고, 소수가 아닌 양의 정수를 말한다.

• 모든 양의 정수는 소수의 곱으로 고유하게 쓸 수 있으며, 여기서 소수는 크기가 커지는 순서대로 쓴다. e.g. 60 = 2 * 2 * 3 * 5
• 만약 n이 합성수라면, n의 prime divisor(소인수)는 $≤ \sqrt n$
  • Proof

The Division Algorithm

$a$가 정수이고 $d$가 양의 정수라고 하자.

$0 ≤ r < d$를 만족하는 유일한 정수 $q$와 $r$이 존재하여 $a = dq + r$이 된다.