자연수: 종합과 도전 과제

요약

이 수업은 자연수를 다루는 단원을 마무리한다. 집합의 언어와 페아노 공리에서 이항정리에 이르는 연역 사슬을 다시 세우면서, 각 고리에서 어떤 원리가 쓰이고 어떤 결과가 얻어지는지를 짚는다. 또 이룬 것을 강좌의 계획 안에 자리매김하고, 자연수 사이의 뺄셈과 나눗셈의 한계가 왜 수 체계를 다루는 다음 단원으로 이어지는지를 설명한다. 끝으로, 수업들의 문제보다 어렵고 여러 수업의 도구를 엮어야 하는 열 개의 도전 과제를 제시한다.

학습 목표

단원의 결과들의 논리적 순서를 다시 세우고, 각 결과가 기대는 원리를 밝힌다.
귀납법, 정렬성, 나머지가 있는 나눗셈, 소인수분해의 유일성, 합동식이 서로 어떻게 연결되는지 설명한다.
자연수 사이의 뺄셈과 나눗셈의 한계에서 출발하여 수 체계를 확장할 필요성을 정당화한다.
귀납법, 나누어떨어짐, 위치적 기수법, 세기를 결합하는 문제를 푼다.

단원에서 이룬 것

이 단원은 몇 안 되는 원리에서 자연수의 산술을 이끌어 내되, 그 성질 가운데 어느 것도 자명하다고 받아들이지 않는 것을 목표로 삼았다. 이 목표는 각각 제자리에서 밝힌 몇 가지 유보 아래에서 이루어졌다. 그 유보란 나머지 모든 것을 적는 언어인 소박한 집합론과 양화사의 부정의 규칙, 데데킨트의 재귀 정리가 보장하며 집합론에 속한다는 이유로 받아들인, 재귀로 정의되는 함수의 존재, 세기의 바탕이 되는, 유한집합의 원소의 개수의 유일성과 그 부분집합의 유한성, 유한 곱의 인수를 재배열할 수 있게 해 주는 일반화된 교환법칙, 그리고 이 단원이 예제와 문제에서 미리 사용했고 다음 단원이 구성하는 정수, 유리수, 실수의 기초 규칙이다. 이런 유보 아래에서, 지나온 길은 네 구간으로 이루어진 하나의 연역 사슬로 읽을 수 있다.

기초: 집합, 공리, 연산, 순서

집합, 관계, 함수에 관한 수업은 단원을 적는 언어를 정하고, 집합론에서 받아들이는 얼마 안 되는 것을 밝힌 뒤, 동치 관계와 분할이 하나의 생각의 두 면임을 증명하였다. 곧, 동치 관계의 동치류는 분할을 이루고, 모든 분할은 단 하나의 동치 관계에서 나온다. 이 결과는 나머지에 따른 정수의 분류와 합동식에서 다시 나타나며, 다음 단원은 이를 이용해 정수와 유리수를 쌍들의 동치류로 구성한다. 페아노 공리에 관한 수업에서는 자연수를 $1$ , 후자 연산, 다섯 공리로 정의하였다. 둘째부터 넷째까지의 공리는 수열이 멈추지도 제자리로 돌아오지도 않음을 보장하고, 다섯째 공리인 수학적 귀납법의 원리는 $1$ 에서 출발하여 도달하는 자연수 말고는 다른 자연수가 없음을 보장한다. 기본 연산과 순서에 관한 수업은 재귀 정리를 이용해 후자 위에 재귀적 정의의 사다리를 세웠고, 그 사다리에서 각 연산은 바로 앞의 연산으로 정의된다:

n + S(m) = S(n + m), \qquad n \cdot S(m) = n \cdot m + n, \qquad b^{S(n)} = b^n \cdot b

이 정의들로부터 귀납법으로 교환법칙, 결합법칙, 분배법칙, 소거법칙을 이끌어 냈고, 덧셈으로부터 삼분법, 추이성, 단조성과 함께 순서를 얻었다. 뺄셈과 나눗셈은 역연산으로 정의되었지만, 어떤 경우에만 그러하다. $a - b$ 는 $b < a$ 일 때 존재하고, $\frac{a}{b}$ 는 $b$ 가 $a$ 의 약수일 때 존재한다.

증명의 원리

합, 수열, 귀납법에 관한 수업은 증명의 수단을 넓혔다. 보통의 귀납법이 강한 귀납법과 정렬성 원리를 함의함을 증명하고, $1$ 과 다른 모든 자연수는 어떤 수의 후자라는 보조정리와 순서의 성질을 이용하면 거꾸로 정렬성이 귀납법을 함의함을 증명하였다. 그래서 각 증명은 자신에게 가장 자연스러운 원리를 쓸 수 있다. 또 합에 재귀적 정의와 계산을 가능하게 하는 성질을 주었고, 망원 합으로 공식은 확인할 뿐 아니라 이끌어 낼 수도 있음을 보였다. 정렬성 원리는 그 뒤의 거의 모든 존재 증명의 도구가 되었다. 집합의 가장 작은 원소를 고르고 최소 반례로 추론할 수 있게 해 주기 때문이다.

나누어떨어짐의 산술

정렬성을 이용해 나누어떨어짐에 관한 수업은 모든 정수가 자연수로 나눌 때 단 하나의 몫과 단 하나의 나머지를 가짐을 증명하였다. 이 정리에 아래의 네 결과가 기대며, 각 결과는 앞의 결과들에 의지한다:

경우를 나누어 증명할 수 있게 해 주는, 나머지에 따른 정수의 분류와 배수 판정법. 배수 판정법은 $d$ 의 배수만큼 차이 나는 두 수가 $d$ 로 나눌 때 같은 나머지를 남긴다는 사실로 귀착된다.
소수에 관한 수업에서, 정렬성과 나머지가 있는 나눗셈으로 증명한 유클리드 보조정리와, 그에 기대는 산술의 기본 정리. 곧, $1$ 보다 큰 모든 자연수는 단 한 가지 방식으로 소수들의 곱이 된다. 유일성으로부터 약수의 개수, 완전제곱수의 특징, 나누어떨어지지 않는 근의 무리성을 이끌어 냈다.
최대공약수에 관한 수업에서, 나머지가 있는 나눗셈을 끝날 때까지 되풀이하는 유클리드 호제법, 그로부터 이끌어지는 베주 항등식, 일차 디오판토스 방정식의 완전한 풀이.
합동식에 관한 수업에서, 앞의 모든 것을 계산으로 바꾼 것. 법 $n$ 에 대한 합동은 덧셈, 곱셈과 양립하는 동치 관계이며, 그 동치류들이 $\mathbb{Z}_n$ 을 이룬다. 베주 항등식은 어떤 나머지가 가역인지, 일차 합동식이 언제 해를 갖는지를 결정하고 중국인의 나머지 정리를 준다. 그리고 유클리드 보조정리는 역원과 함께 페르마의 소정리를 준다.

표기와 세기

위치적 기수법에 관한 수업은 나머지가 있는 나눗셈을 거듭 적용하여 모든 자연수가 어떤 밑에서든 단 한 가지 방식으로 쓰임을 증명하였고, 이로써 모든 밑에서 계산 절차와 배수 판정법을 정당화하였다. 조합론과 이항정리에 관한 수업은 출발점으로 돌아갔다. 세는 일이야말로 자연수를 낳은 연산이기 때문이다. 전단사 함수를 통한 원소의 개수의 정의로부터 증명한 합의 법칙과 곱의 법칙(곱의 법칙은 합의 법칙으로부터 귀납법으로 증명하였다)은 이항계수, 파스칼의 법칙, 이항정리로 이어졌고, 이항정리의 증명은 귀납법, 합의 기호, 세기를 하나로 모은다.

아래 그림은 네 구간을 하나의 사슬로 모은 것이다. 가운데 열의 각 마디는 정의나 정리이며, 논리적 순서에 따라 번호가 붙고, 그 증명이 쓰는 앞의 고리들과 호로 이어진다. 그 둘레에 떠 있는 것이 받침, 곧 사슬이 거듭 의지하는 원리와 도구이다. 각 받침은 자신에게 기대는 고리들과 실선으로, 자신이 세워지는 고리와 점선으로 이어지며, 증명 없이 받아들이는 받침은 둥근 테로 그려진다. 받침을 누르면 그것을 쓰는 고리가 모두 강조되고, 각 고리는 그것이 증명되는 수업으로 이어진다.

사슬의 받침

A수학적 귀납법의 원리. 어떤 성질이 $1$ 에 대하여 성립하고, 임의의 자연수 $k$ 에 대하여 성립한다고 가정하면 그 후자 $S(k)$ 에 대하여도 성립한다면, 그 성질은 모든 자연수에 대하여 성립한다. 확립되는 곳: 2. 페아노 공리.
B재귀 정리. $1$ 에서의 값과, $S(n)$ 에서의 값을 주는 규칙( $n$ 에서의 값으로부터 구하는 것)을 정하면, 그것들을 만족하는 자연수 위의 함수가 단 하나 존재한다. 덧셈, 곱셈, 거듭제곱, 합, 계승이 이렇게 정의된다. 존재는 받아들이고, 유일성은 귀납법으로 증명한다. 이 단원에서는 증명 없이 받아들인다.
C강한 귀납법. 어떤 성질이 $1$ 에 대하여 성립함과, $1$ 부터 $n$ 까지의 모든 자연수에 대하여 성립한다고 가정하면 $n + 1$ 에 대하여도 성립함을 증명하면 충분하다. 확립되는 곳: 9. 강한 귀납법.
D정렬성. 자연수로 이루어진 공집합이 아닌 모든 집합은 가장 작은 원소를 가지며, 이로써 최소 반례로 추론할 수 있다. 확립되는 곳: 10. 정렬성 원리.
E나머지가 있는 나눗셈. 모든 정수 $a$ 와 모든 자연수 $b$ 에 대하여, 단 하나의 몫 $q$ 와 단 하나의 나머지 $r$ 이 존재하여 $a = bq + r$ 이고 $0 \leq r < b$ 이다. 확립되는 곳: 12. 나머지가 있는 나눗셈.
F일차결합. 정수 $d$ 가 정수 $a$ 와 $b$ 의 약수이면, 그것은 $ax + by$ 의 약수이다. 단, $x$ 와 $y$ 는 임의의 정수이다. 특히 그 합과 차의 약수이다. 확립되는 곳: 11. 나누어떨어짐의 성질.
G미리 사용한 수. 정수, 유리수, 실수의 계산과 순서에 관한 기초 규칙(부호, 소거, 분수, 근)은 이 단원에서 증명 없이 미리 사용한다. 그 구성은 다음 단원의 내용이다. 이 단원에서는 증명 없이 받아들인다.
H원소의 개수. $\{1, \ldots, n\}$ 과의 사이에 전단사 함수가 있는 집합은 $n$ 개의 원소를 가진다. 이 수가 단 하나라는 것과 유한집합의 부분집합이 유한하다는 것은 받아들인다. 이 단원에서는 증명 없이 받아들인다.

제1구간 기초: 집합, 공리, 연산, 순서
- 집합, 관계, 함수의 언어를 정하고, 동치 관계와 분할이 서로 대응함을 증명한다.
- 자연수를 $1$ 과 후자에서 출발하여 페아노의 다섯 공리로 정의한다.
- 후자 위에 재귀적 정의의 사다리를 세운다. 덧셈, 곱셈, 거듭제곱이다.
- 교환법칙, 결합법칙, 분배법칙, 소거법칙을 귀납법으로 이끌어 낸다.
- 덧셈으로부터 삼분법, 추이성, 단조성과 함께 순서를 얻고, 차와 몫이 언제 존재하는지 밝힌다.
1. 동치 관계와 분할. 집합 위의 동치 관계의 동치류는 그 집합의 분할을 이루고, 모든 분할은 단 하나의 동치 관계의 동치류 전체의 집합이다.
  증명된 수업: 집합, 관계, 함수.
2. 페아노 공리. 자연수는 $1$ 에서 후자에 의해 생성된다. $1$ 은 어떤 수의 후자도 아니고, 서로 다른 자연수는 서로 다른 후자를 가지며, $1$ 과 자신의 각 원소의 후자를 포함하는 모든 집합은 모든 자연수를 포함한다.
  증명된 수업: 자연수와 페아노 공리.
3. 재귀적 덧셈. $n + 1 = S(n)$ 과 $n + S(m) = S(n + m)$ 로 정의되는 덧셈은 교환법칙, 결합법칙, 소거법칙을 만족한다.
  사용: 2. 페아노 공리. 받침: A (수학적 귀납법의 원리), B (재귀 정리). 증명된 수업: 자연수의 기본 연산과 순서 관계.
4. 곱셈과 거듭제곱. $n \cdot 1 = n$ 과 $n \cdot S(m) = n \cdot m + n$ 로 정의되는 곱셈은 교환법칙, 결합법칙, 분배법칙, 소거법칙을 만족하고, 거듭제곱은 $b^n b^m = b^{n + m}$ , $(b^n)^m = b^{nm}$ , $(ab)^n = a^n b^n$ 를 만족한다.
  사용: 3. 재귀적 덧셈. 받침: A (수학적 귀납법의 원리), B (재귀 정리). 증명된 수업: 자연수의 기본 연산과 순서 관계.
5. 순서, 뺄셈, 나눗셈. $a < b$ 가 $a + k = b$ 를 뜻할 때( $k$ 는 어떤 자연수), 두 자연수 사이에는 $a < b$ , $a = b$ , $b < a$ 의 관계 가운데 정확히 하나가 성립하고, 순서는 추이적이며 덧셈과 곱셈에 의해 보존된다. 차 $a - b$ 는 $b < a$ 일 때에만 존재하고, 몫 $\frac{a}{b}$ 는 $b$ 가 $a$ 의 약수일 때에만 존재하며, 둘 다 소거법칙에 의해 단 하나이다.
  사용: 2. 페아노 공리, 3. 재귀적 덧셈, 4. 곱셈과 거듭제곱. 받침: A (수학적 귀납법의 원리). 증명된 수업: 자연수의 기본 연산과 순서 관계.
제2구간 증명의 원리
- 보통의 귀납법, 강한 귀납법, 정렬성 원리가 동치임을 증명한다.
- 합을 재귀적으로 정의하고 그 성질을 이끌어 낸다.
- 공식을 확인하는 데 그치지 않고 망원 합으로 이끌어 낸다.
- 등차수열과 등비수열의 합을 구한다.
1. 한 자연수에서 시작하는 귀납법. $n_0$ 에 대하여 성립하고 각 자연수 $k \geq n_0$ 에서 $k + 1$ 로 넘어가는 성질은 모든 자연수 $n \geq n_0$ 에 대하여 성립한다.
  사용: 5. 순서, 뺄셈, 나눗셈. 받침: A (수학적 귀납법의 원리). 증명된 수업: 합, 수열, 귀납법.
2. 합과 망원 합. 재귀적으로 정의된 합은 선형이고, 이어지는 합들로 나눌 수 있으며, 첨자의 이동과 순서의 뒤집기를 허용한다. 이웃한 값들의 차의 합은 마지막 값에서 첫 값을 뺀 것과 같다: $\sum_{k=1}^{n} (b_{k + 1} - b_k) = b_{n + 1} - b_1$ .
  사용: 4. 곱셈과 거듭제곱, 6. 한 자연수에서 시작하는 귀납법. 받침: A (수학적 귀납법의 원리), B (재귀 정리). 증명된 수업: 합, 수열, 귀납법.
3. 등차수열과 등비수열. 등차수열의 $n$ 개 항의 합은 $\frac{n(a_1 + a_n)}{2}$ 이고, 첫째항이 $a$ 이고 공비가 $r \neq 1$ 인 등비수열의 합은 $a \cdot \frac{r^n - 1}{r - 1}$ 이다.
  사용: 7. 합과 망원 합. 받침: A (수학적 귀납법의 원리), G (미리 사용한 수). 증명된 수업: 합, 수열, 귀납법.
4. 강한 귀납법. 어떤 성질이 $1$ 에 대하여 성립하고, $1$ 부터 $n$ 까지의 모든 자연수에 대하여 성립한다고 가정하면 $n + 1$ 에 대하여도 성립한다면, 그 성질은 모든 자연수에 대하여 성립한다.
  사용: 6. 한 자연수에서 시작하는 귀납법. 받침: A (수학적 귀납법의 원리). 증명된 수업: 합, 수열, 귀납법.
5. 정렬성 원리. 원소를 하나 이상 가진 자연수의 집합은 모두 가장 작은 원소를 가진다. $1$ 과 다른 모든 자연수는 어떤 수의 후자라는 보조정리와 순서의 성질을 이용하면 거꾸로 정렬성이 귀납법을 함의하고, 세 원리는 동치가 된다.
  사용: 5. 순서, 뺄셈, 나눗셈. 받침: C (강한 귀납법). 증명된 수업: 합, 수열, 귀납법.
제3구간 나누어떨어짐의 산술
- 정렬성으로 몫과 나머지의 존재와 유일성을 증명한다.
- 정수를 나머지에 따라 분류하고, 그것에 바탕을 두어 배수 판정법을 세운다.
- 소수가 무한히 많음, 유클리드 보조정리, 소인수분해의 유일성을 그 결과들과 함께 증명한다.
- 유클리드 호제법으로 최대공약수를 계산하고, 그로부터 베주 항등식을 이끌어 내며, 일차 디오판토스 방정식을 푼다.
- 합동식으로 계산하고, 어떤 나머지가 가역인지 판정하며, 일차 합동식과 법이 서로소인 연립 합동식을 풀고, 페르마의 소정리를 증명한다.
1. 나누어떨어짐의 성질. 정수 사이의 나누어떨어짐은 반사적이고 추이적이며, 정수 $a > 0$ 의 약수는 $-a$ 와 $a$ 사이에 있고, $d$ 가 $a$ 와 $b$ 의 약수이면 모든 결합 $ax + by$ 의 약수이다.
  사용: 5. 순서, 뺄셈, 나눗셈. 받침: G (미리 사용한 수). 증명된 수업: 나누어떨어짐과 나머지가 있는 나눗셈.
2. 나머지가 있는 나눗셈. 모든 정수 $a$ 와 모든 자연수 $b$ 에 대하여, 단 하나의 몫 $q$ 와 단 하나의 나머지 $r$ 이 존재하여 $a = bq + r$ 이고 $0 \leq r < b$ 이다.
  받침: D (정렬성), G (미리 사용한 수). 증명된 수업: 나누어떨어짐과 나머지가 있는 나눗셈.
3. 나머지와 판정법. 두 정수가 $d$ 로 나눌 때 같은 나머지를 남길 필요충분조건은 그 차가 $d$ 의 배수인 것이다. 이로부터 합, 곱, 거듭제곱의 나머지와 $3$ , $9$ , $11$ 의 배수 판정법이 따른다.
  받침: A (수학적 귀납법의 원리), E (나머지가 있는 나눗셈), F (일차결합). 증명된 수업: 나누어떨어짐과 나머지가 있는 나눗셈.
4. 소인수와 무한성. 모든 자연수 $n > 1$ 은 소인수를 가지며, $n$ 이 합성수이면 그 가장 작은 소인수 $p$ 는 $p^2 \leq n$ 을 만족한다. 이로부터 어떤 유한한 목록도 모든 소수를 담지 못함이 따른다.
  사용: 5. 순서, 뺄셈, 나눗셈, 11. 나누어떨어짐의 성질. 받침: D (정렬성), F (일차결합). 증명된 수업: 소수와 산술의 기본 정리.
5. 유클리드 보조정리. 소수가 곱 $ab$ 의 약수이면, 그 소수는 $a$ 의 약수이거나 $b$ 의 약수이다. 또 여러 인수의 곱의 약수이면, 그 인수들 가운데 어느 하나의 약수이다.
  받침: A (수학적 귀납법의 원리), D (정렬성), E (나머지가 있는 나눗셈), F (일차결합). 증명된 수업: 소수와 산술의 기본 정리.
6. 산술의 기본 정리. 모든 자연수 $n > 1$ 은 소수들의 곱이고, 그 분해는 인수의 순서를 빼면 단 하나이다.
  사용: 4. 곱셈과 거듭제곱, 15. 유클리드 보조정리. 받침: D (정렬성). 증명된 수업: 소수와 산술의 기본 정리.
7. 약수와 무리수인 근. $n = p_1^{e_1} \cdots p_k^{e_k}$ 이면, 그 약수는 수 $p_1^{f_1} \cdots p_k^{f_k}$ (단, $0 \leq f_i \leq e_i$ )이고, 그 개수는 $(e_1 + 1) \cdots (e_k + 1)$ 이다. 자연수 $n > 1$ 이 완전한 $k$ 제곱수일 필요충분조건은 그 분해의 모든 지수가 $k$ 의 배수인 것이다. 그렇지 않으면 자연수 $a$ 와 $b$ 로서 $a^k = n b^k$ 인 것은 없다. 곧 그 $k$ 제곱근은 무리수이다.
  사용: 15. 유클리드 보조정리, 16. 산술의 기본 정리. 받침: A (수학적 귀납법의 원리), G (미리 사용한 수). 증명된 수업: 소수와 산술의 기본 정리.
8. 유클리드 호제법. $a = bq + r$ 이면, 쌍 $a, b$ 와 쌍 $b, r$ 은 같은 공약수를 가진다. 따라서 $\operatorname{gcd}(a, b)$ 는 잇따른 나눗셈의 마지막으로 0이 아닌 나머지이다.
  받침: D (정렬성), E (나머지가 있는 나눗셈), F (일차결합). 증명된 수업: 최대공약수와 최소공배수.
9. 베주 항등식. 정수 $x$ 와 $y$ 가 존재하여 $ax + by = \operatorname{gcd}(a, b)$ 이고, 최대공약수는 이 꼴로 쓸 수 있는 가장 작은 자연수이다.
  사용: 18. 유클리드 호제법. 받침: A (수학적 귀납법의 원리), F (일차결합), G (미리 사용한 수). 증명된 수업: 최대공약수와 최소공배수.
10. 최대공약수와 최소공배수의 곱. $\operatorname{gcd}(a, b) \cdot \operatorname{lcm}(a, b) = ab$ 이 성립하고, $a$ 와 $b$ 의 모든 공배수는 그 최소공배수의 배수이다.
  사용: 4. 곱셈과 거듭제곱, 16. 산술의 기본 정리, 17. 약수와 무리수인 근. 받침: D (정렬성), E (나머지가 있는 나눗셈), F (일차결합). 증명된 수업: 최대공약수와 최소공배수.
11. 디오판토스 방정식. 방정식 $ax + by = c$ 가 정수해를 가질 필요충분조건은 $d = \operatorname{gcd}(a, b)$ 가 $c$ 의 약수인 것이며, 그때 모든 해는 $x = x_0 + \frac{b}{d} t$ 와 $y = y_0 - \frac{a}{d} t$ 이다. 단, $t$ 는 정수이다.
  사용: 19. 베주 항등식, 20. 최대공약수와 최소공배수의 곱. 받침: F (일차결합), G (미리 사용한 수). 증명된 수업: 최대공약수와 최소공배수.
12. 합동과 나머지. 두 정수가 법 $n$ 에 대하여 합동일 필요충분조건은 $n$ 으로 나눌 때 같은 나머지를 남기는 것이다. 합동은 덧셈, 곱셈과 양립하는 동치 관계이며, 그 $n$ 개의 동치류, 곧 나머지 $0, 1, \ldots, n - 1$ 의 동치류가 $\mathbb{Z}_n$ 을 이룬다.
  사용: 1. 동치 관계와 분할, 13. 나머지와 판정법. 받침: E (나머지가 있는 나눗셈), F (일차결합). 증명된 수업: 합동식과 모듈러 산술.
13. 가역인 나머지. 정수 $a$ 가 법 $n$ 에 대한 역원을 가질 필요충분조건은 $\operatorname{gcd}(a, n) = 1$ 인 것이며, 그때 역원은 법 $n$ 에 대하여 단 하나이다. 합동식 $ax \equiv b \pmod{n}$ 가 해를 가질 필요충분조건은 $d = \operatorname{gcd}(a, n)$ 가 $b$ 의 약수인 것이며, 그때 해는 $d$ 개이다(법 $n$ 에 대하여).
  사용: 22. 합동과 나머지, 19. 베주 항등식, 21. 디오판토스 방정식. 받침: F (일차결합). 증명된 수업: 합동식과 모듈러 산술.
14. 중국인의 나머지 정리. 자연수 $m$ 과 $n$ 이 서로소이면, $x \equiv a \pmod{m}$ 와 $x \equiv b \pmod{n}$ 로 이루어진 연립 합동식은 해를 가지며, 그 해는 법 $mn$ 에 대하여 단 하나이다.
  사용: 22. 합동과 나머지, 19. 베주 항등식, 20. 최대공약수와 최소공배수의 곱. 받침: G (미리 사용한 수). 증명된 수업: 합동식과 모듈러 산술.
15. 페르마의 소정리. $p$ 가 소수이고 정수 $a$ 의 약수가 아니면 $a^{p - 1} \equiv 1 \pmod{p}$ 이다. 또 모든 정수 $a$ 에 대하여 $a^p \equiv a \pmod{p}$ 이다.
  사용: 22. 합동과 나머지, 15. 유클리드 보조정리, 23. 가역인 나머지. 증명된 수업: 합동식과 모듈러 산술.
제4구간 표기와 세기
- 모든 자연수가 어떤 밑에서든 단 한 가지 방식으로 쓰임을 증명한다.
- 모든 밑에서 세로셈 덧셈과 배수 판정법을 정당화한다.
- 합의 법칙과 곱의 법칙으로 세고, 그로부터 이항계수와 파스칼의 법칙을 얻는다.
- 귀납법, 합의 기호, 세기를 하나로 모으는 이항정리를 증명한다.
1. 위치적 표기. 모든 밑 $b \geq 2$ 에 대하여, 모든 자연수는 단 한 가지 방식으로 $a_k b^k + \cdots + a_1 b + a_0$ 의 꼴로 쓰인다. 단, 숫자는 $0$ 부터 $b - 1$ 까지이고 $a_k \neq 0$ 이다.
  받침: C (강한 귀납법), D (정렬성), E (나머지가 있는 나눗셈). 증명된 수업: 위치적 기수법.
2. 모든 밑에서의 계산과 판정법. 세로셈 덧셈은 합의 표기를 주고, 밑 $b$ 에서 어떤 수는 $b - 1$ 로 나눌 때 각 자리 숫자의 합과 같은 나머지를 남기고, $b + 1$ 로 나눌 때 교대합과 같은 나머지를 남긴다.
  사용: 7. 합과 망원 합, 13. 나머지와 판정법, 26. 위치적 표기. 받침: A (수학적 귀납법의 원리), E (나머지가 있는 나눗셈). 증명된 수업: 위치적 기수법.
3. 세기의 원리. 공통 원소가 없는 두 집합으로서 원소가 각각 $m$ 개와 $n$ 개인 것들의 합집합은 $m + n$ 개의 원소를 가지며, 두 과정으로 이루어진 선택으로서 각각 $m$ 이지와 $n$ 이지인 것은 $mn$ 이지로 이루어진다.
  사용: 3. 재귀적 덧셈, 4. 곱셈과 거듭제곱, 5. 순서, 뺄셈, 나눗셈. 받침: A (수학적 귀납법의 원리), H (원소의 개수). 증명된 수업: 기초 조합론과 이항정리.
4. 이항계수와 파스칼의 법칙. 원소가 $n$ 개인 집합은 $\binom{n}{k} = \frac{n!}{k!\,(n - k)!}$ 개의 부분집합(원소가 $k$ 개인 것)을 가진다. $\binom{n + 1}{k} = \binom{n}{k - 1} + \binom{n}{k}$ 이 성립하며, 이로부터 계수들은 파스칼의 삼각형을 이루고, 제 $n$ 행의 합은 $2^n$ 이다.
  사용: 28. 세기의 원리. 받침: B (재귀 정리), H (원소의 개수). 증명된 수업: 기초 조합론과 이항정리.
5. 이항정리. 모든 수 $x$ 와 $y$ (자연수, 또는 다음 단원을 앞당겨 실수)와 모든 자연수 $n$ 에 대하여 $(x + y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n - k} y^k$ 이 성립한다.
  사용: 7. 합과 망원 합, 29. 이항계수와 파스칼의 법칙. 받침: A (수학적 귀납법의 원리), G (미리 사용한 수). 증명된 수업: 기초 조합론과 이항정리.

수 체계를 향하여. 사슬은 자연수로 충분하지 않게 되는 곳에서 멈춘다. 뺄셈과 나눗셈은 어떤 경우에만 존재하고, 방정식 $x^2 = n$ 은 $n$ 이 완전제곱수가 아닐 때 유리수 해를 갖지 않는다. 다음 단원은 이를 메우기 위해 자연수를 확장한다.