数論入門

Introduction to Number Theory

入門（高校数学レベル）

この章について

数論入門では、整数の基本的な性質を学ぶ。約数と倍数の関係、素数の概念、そして2000年以上前から知られているユークリッドの互除法まで、数論の基礎を固める。

任意の正整数 $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を割るので可能。