1. 概要 本記事では，中国剰余定理（Chinese Remainder Theorem, CRT）について解説します．中国剰余定理は，どの $2$ つも互いに素であるような正整数 $m_0,m_1,\ldots,m_{n-1}$ に対して，合同式 $$ x\equiv a _ 0\pmod{m _ 0},\quad x\equiv a _ 1\pmod{m…

1. 概要 本記事では，Euclid の互除法（Euclidean Algorithm）について解説します． Euclid の互除法は 2 つの整数の最大公約数（gcd）を求めるアルゴリズムとして有名です．しかし，その応用は最大公約数を求めることだけに留まりません． 特に Euclid の互…

1. 概要 本記事では合同式の基礎的な考え方について説明します． 合同式は，整数全体を $m$ で割ったときの余り（剰余）に応じて分類するものです．競技プログラミングでは特に「答えを $m$ で割った余りで出力せよ」という形式が頻出で，そのような問題では…

1. 概要 本記事では，$\mathbb{F}_p$ 係数の多項式に関する重要事項について解説します． 議論の大部分は，多項式について中学・高校の数学で学んだ内容の再確認になると思います．ただし，中学・高校の数学では，多項式の係数として主に実数（や複素数）を…

1. 概要 本記事では，素数の基礎的な性質について解説します． $2$ 以上の整数 $p$ のうちで，$1,p$ 以外に約数を持たないものを素数ということはよく知られていると思います．非自明な約数がないというのが素数の定義ですが，「$ab$ が $p$ の倍数ならば $a…

1. 概要 競技プログラミングの学習をしていると，次のような結果を目にすることがあると思います． $N$ 以下の素数の個数は $\displaystyle \frac{N}{\log N}$ 程度である（素数定理）． $N$ 以下の素数の逆数の総和 $\displaystyle \sum_{p\leq N}\frac{1}{…

1. 概要 本記事では，素数を法とする原始根について解説します．特に原始根の存在の証明を主な目標とします． これは $p$ を素数とするとき，$\mathbb{F}_p$ の元のうち $0$ でないもの全体が（あるいは $p$ を法として $1$ 以上 $p-1$ 以下の整数全体が）等…