다음을 만족하는 집합 $\mathbb{N}$을 자연수 집합이라 하자: A1) $1\in \mathbb{N}$ A2) $\forall n\in\mathbb{N}, S(n)\in\mathbb{N}$ A3) $\forall n\in\mathbb{N}, S(n)\neq 1$ A4) $S(n)=S(m)\implies m=n$ A5) $1\in M \subset \mathbb{N} \text{ and } \forall m\in M, S(m)\in M \implies M=\mathbb{N}$
다음을 만족하는 기호 $+$를 자연수에서의 덧셈으로 정의한다: $\forall m, n\in \mathbb{N} \Rightarrow+:\mathbb{N}\times \mathbb{N}\rightarrow\mathbb{N}$ 1) $m+1=S(m)$ 2) $m+S(n)=S(m+n)$ 이때 결합, 교환, 소거법칙은 수학적 귀납법으로 증명 가능.
다음을 만족하는 기호 $\times$를 자연수에서의 곱셈으로 정의한다: $\forall m, n\in \mathbb{N} \Rightarrow\times:\mathbb{N}\times \mathbb{N}\rightarrow\mathbb{N}$ 1) $m\times1=m$ 2) $m\times S(n)=m\times n + m$ 분배 → 교환 → 결합 (귀납법) → 소거 (귀류법)
정렬성의 원리: 공집합이 아니고 음이 아닌 정수들을 원소로 갖는 집합은 반드시 최소원소를 가진다 즉, $\exists a \text{ s.t. }\forall b\in S, a\leq b$
아르키메데스 원리: $\forall a, b\in\mathbb{N}, \exists n\in\mathbb{N}\text{ s.t. }na\geq b$
유한 귀납법의 기본원리 (1, 2, 3)
이항계수 ${n\choose k}=\frac{n!}{k!(n-k)!}$
나눗셈 정리 : $\forall a, b\in \mathbb{Z}, \exists! q,r \text{ s.t. }a=qb+r,0\le r<\left|b\right|$
$a\mid b \iff \exists c\in\mathbb{Z}, b=ac$
else $a \nmid b$
최대공약수 $\operatorname{gcd}(a,b)=d\in\mathbb{N} \text { s.t. }\\ \text{a) }d\mid a, d\mid b\\ \text{b) }\forall c \text{ s.t. }c\mid a, c\mid b \Rightarrow c\leq d$
$\forall a, b\in\mathbb{Z}, (a, b)\neq (0, 0)\Rightarrow \exists x, y\in \mathbb{Z}: \operatorname{gcd}(a, b)=ax+by$
$\forall a, b\in \mathbb{Z}, (a, b)\ne (0, 0), \text{gcd}(a, b)=1$ 이면 $a, b$를 서로 소라 한다.
유클리드 보조정리: $a\mid bc, \gcd(a, b)=1 \implies a\mid c$
유클리드 알고리즘: $a=qb+r \Longrightarrow \gcd(a, b)=\gcd(b, r)$