整数論まとめ：定義・定理・アルゴリズムを一覧で整理【学部整数論・競技プログラミング】
整数論の全体像を一記事で．整除・合同式からp進数・代数的整数まで，学部整数論と競技プログラミングに必要な定義・定理・アルゴリズムを体系的にまとめた．各トピックの依存関係図付き．
整数の整除と合同式 ― 整数論の出発点を固める
整除の定義から出発し，割り算の原理の存在と一意性を厳密に証明する．合同式の定義と基本性質，合同式の演算規則を体系的に扱い，剰余類環$\mathbb{Z}/n\mathbb{Z}$の構成まで解説する教科書スタイルの記事．
最大公約数とユークリッド互除法 ― アルゴリズムの代数的基盤
gcd/lcmの定義と性質を厳密に定め，ユークリッド互除法の正当性と計算量$O(\log \min(a,b))$を証明する．ベズーの等式と拡張ユークリッド互除法を扱い，一次合同式$ax \equiv b \pmod{n}$の解法を体系的に解説する．
素数と算術の基本定理 ― 整数の原子分解
素数の定義と基本性質を定め，素数の無限性のユークリッドによる証明を与える．算術の基本定理（存在と一意性）を厳密に証明し，Miller-Rabin素数判定法やエラトステネスの篩を解説する．
合同式の応用と剰余類の群構造 ― $(\mathbb{Z}/n\mathbb{Z})^*$ の構造
既約剰余類群$(\mathbb{Z}/n\mathbb{Z})^*$の構造を解明する．オイラー関数$\varphi(n)$の計算公式を導出し，フェルマーの小定理，オイラーの定理，ウィルソンの定理を証明する．元の位数と原始根の存在条件を議論する．
原始根と離散対数 ― 巡回群としての $(\mathbb{Z}/p\mathbb{Z})^*$
$(\mathbb{Z}/p\mathbb{Z})^*$が巡回群であることを証明し，原始根の個数が$\varphi(p-1)$であることを示す．指数（離散対数）の概念を導入し，$(\mathbb{Z}/p^k\mathbb{Z})^*$の構造定理を扱い，離散対数問題（DLP）を解説する．
中国剰余定理と応用 ― 連立合同式と環の直積分解
中国剰余定理を環の同型写像として代数的に証明する．一般の場合（$\gcd \neq 1$）への拡張，Garnerのアルゴリズム，$\varphi$の乗法性のCRTによる証明，および競技プログラミングへの応用を扱う．
二次剰余と相互法則 ― 平方剰余の理論
ルジャンドル記号を定義し，オイラーの規準を証明する．ガウスの補題を経て二次の相互法則を証明し，ヤコビ記号への拡張とTonelli-Shanksアルゴリズムを解説する．
数論的関数と乗法的関数 ― 整数の関数たち
乗法的関数（$\varphi$, $\sigma$, $\mu$, $d$）を体系的に定義し，ディリクレ畳み込みの環構造を解説する．メビウス反転公式を厳密に証明し，包除原理との関係を明らかにする．
連分数とディオファントス近似 ― 有理近似の理論
有限・無限連分数の定義と収束の証明を与え，近似分数の性質を厳密に示す．最良有理近似の理論，ペル方程式$x^2 - Dy^2 = 1$の解法，Stern-Brocot木を解説する．
素数の分布 ― 素数定理への道
素数計数関数$\pi(x)$を定義し，チェビシェフの評価から素数定理$\pi(x) \sim x / \ln x$に至る道筋を解説する．メルテンスの定理，ディリクレの算術級数定理の主張，双子素数予想など素数分布の深い結果を紹介する．
$p$進付値と局所的手法入門 ― 素数ごとに整数を見る
$p$進付値$v_p(n)$と$p$進絶対値を定義し，オストロフスキーの定理を紹介する．$p$進整数$\mathbb{Z}_p$の構成，ヘンゼルの補題，局所-大域原理を解説する．
代数的整数入門 ― 整数の概念を拡張する
ガウス整数$\mathbb{Z}[i]$とアイゼンシュタイン整数$\mathbb{Z}[\omega]$を具体例として代数的整数環を導入する．$\mathbb{Z}[\sqrt{-5}]$での一意分解の崩壊を示し，イデアルと素イデアル分解による救済，類数の概念を解説する．