数論

概要

素因数・gcd・Bézoutから、法上の演算と逆元、CRTへ進む。整数境界の正確な扱いを揃えた後、剰余周期・乗法的位数・巡回群の指数化をつなぎ、BSGSで反復到達時刻を探索する。床和と有理近似ではEuclid互除法による縮小を比較し、Stern–Brocot木の経路へ応用する。発展は数値半群、素体でも使えるFrobenius恒等式、拡大有限体、Gaussian整数、総和篩の順に読む。群の計数には約数反転、総和篩には商一定区間という既習の道具を持ち込む。

数論構造への変換

整数条件を合同・整除・指数・約数格子などの数論構造へ変換する。

考え方

整数を値のまま扱うか、素因数指数・剰余・gcd・周期へ移すかを選ぶ。巨大な範囲は商の一定区間やEuclidの互除法で圧縮し、除算には可逆性や丸めの条件を付ける。

成立条件と計算量

入力値Uに対するlog U、√U、Uの費用は大きく違う。modを取っても割算が自由になるわけではない。各単元で整数の存在条件と、答えを計算する手順を分けて確認する。

章の構成

項目は各章の読書順に並べています。親子関係は順序と独立しているため、階層を字下げで表さず、子Unitには「概念上の親」を示します。導入項目は関連手法の見取り図で、発展的なUnitは対象色を目安に後から戻って学べます。

問題一覧

この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

導入対象の目安: 緑色(800–1199)。素因数・gcd・剰余を整数条件の表現として使い分ける入口。

対象色の読み方は本書の読み方を参照してください。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-chapter-number-theory

習得する技能

  • 整数条件を合同・整除・指数・約数格子などの数論構造へ変換する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: なし。

このUnitを直接前提とする単元: なし。

整数条件をgcd・合同・素因数指数・約数格子へ翻訳し、有限状態化と反転の基礎を作る。

このUnitでは扱わないもの

  • なし

根拠