数論入門
Introduction to Number Theory
入門（高校数学レベル）
この章について
数論入門では、整数の基本的な性質を学ぶ。約数と倍数の関係、素数の概念、ユークリッドの互除法に加え、剰余による整数の分類、整数に関する証明技法、n進法まで、数論の基礎を固める。
前提知識
- 自然数の四則演算（小学校レベル）
目次
1. 整数の性質
整数の定義、整除性、約数と倍数、最大公約数・最小公倍数。
- 整数とは何か・数の分類
- 整除性と約数・倍数
- 最大公約数（GCD）と最小公倍数（LCM）
2. 素数と素因数分解
素数の定義と無限性、算術の基本定理、素因数分解の応用。
- 素数とは・エラトステネスの篩
- 素数の無限性（ユークリッドの証明）
- 算術の基本定理と暗号への応用
3. ユークリッドの互除法
GCDを効率的に求めるアルゴリズム。拡張互除法と1次不定方程式。
- 互除法の原理とアルゴリズム
- 拡張ユークリッドの互除法
- 1次不定方程式 $ax + by = c$ への応用
4. 剰余と整数の分類
除法の原理と剰余による場合分け。偶奇やmod 3での分類。
- 除法の原理（商と余りの存在と一意性）
- 偶数と奇数の四則演算
- 剰余分類の応用（カレンダー・チェックディジット）
5. 整数の性質の証明
整数に関する証明の基本技法。直接証明、背理法、帰納法。
- 直接証明と対偶法
- 背理法（$\sqrt{2}$ の無理性）
- 数学的帰納法と場合分け
6. n進法
位取り記数法の原理。2進法・16進法とコンピュータの関係。
- 位取り記数法と基数
- 2進法・8進法・16進法の変換
- 応用（コンピュータの内部表現・色コード）
7. 循環小数と循環節
分数の小数展開が有限で終わるか、無限に繰り返すか。
- 有限小数と循環小数の条件
- 循環小数から分数への変換
- 循環節の長さと位数
8. 有理数体
四則演算が自由にできる数の体系 $\mathbb{Q}$ の構造。
- 有理数の定義と同値関係
- 体の公理（加法・乗法の性質）
- 稠密性と実数体への拡張
主要な定理
除法の原理
任意の整数 $a$ と正整数 $b$ に対して、
$$a = bq + r \quad (0 \leq r < b)$$を満たす整数 $q$（商）と $r$（余り）が一意に存在する。
算術の基本定理
任意の正整数 $n > 1$ は、素数の積として一意的に表される（順序を除く）。
$$n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$$ユークリッドの定理
素数は無限に存在する。
ベズーの等式
整数 $a, b$ に対して、$\gcd(a, b) = d$ ならば、$ax + by = d$ を満たす整数 $x, y$ が存在する。
このレベルで理解できる応用
チェックディジット
ISBN（書籍コード）、JANコード（バーコード）、クレジットカード番号などには検査用の数字が付いている。これは剰余演算で計算され、入力ミスを検出する。例えばISBN-13では、各桁に1と3を交互にかけて足し合わせ、その和が10で割り切れるようにチェックディジットが決まる。
カレンダー計算
ある日付が何曜日かを求める公式（ツェラーの公式など）は、7を法とする剰余演算を使う。「今日から100日後は何曜日？」も $(100 \mod 7) = 2$ なので2日後の曜日とわかる。
時計算術
12時間制の時計は自然に「12を法とする合同式」になっている。「今9時、15時間後は？」は $(9 + 15) \mod 12 = 0$、つまり12時。これは合同式の最も身近な例。
パズル・ゲーム
数独の解の存在や、「川渡り問題」「水差し問題」などの古典パズルは、GCDや整除性で解析できる。例えば「5リットルと3リットルの容器で4リットルを量る」は $\gcd(5, 3) = 1$ が4を割るので可能。
コンピュータと2進法
コンピュータは内部的にすべてのデータを2進法で扱う。整数、小数、文字、画像、音声——あらゆるデータが0と1の列として表現される。16進法（#FF0000 = 赤）やIPアドレス（192.168.1.1）も、n進法の身近な応用である。
学習のポイント
- 整除性の理解：「$a$ が $b$ を割り切る」という関係を正確に把握する
- 素数の重要性：素数が整数論において果たす基本的な役割を理解する
- アルゴリズム的思考：ユークリッドの互除法を通じて、計算の効率性を学ぶ
- 剰余と場合分け：余りによる分類で、整数の性質を系統的に調べる技法を身につける
- 証明技法の習得：直接証明、背理法、帰納法など、整数に関する基本的な証明法を学ぶ
- 記数法の理解：10進法以外の表記を学び、コンピュータとの関わりを知る