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$ 以下の整数全体が）等…