原始根 - AtCoderInfo

1. 概要 本記事では，素数を法とする原始根について解説します．特に原始根の存在の証明を主な目標とします． これは $p$ を素数とするとき，$\mathbb{F}_p$ の元のうち $0$ でないもの全体が（あるいは $p$ を法として $1$ 以上 $p-1$ 以下の整数全体が）等比数列の規則で並べられることを主張する定理です．例えば $p=11$ とするとき，初項 $1$，公比 $2$ の等比数列は $$ 1, 2, 4, 8, 5, 10, 9, 7, 3, 6, 1, 2, 4, 8, 5, 10, 9, 7, 3, 6, 1, 2, 4, 8, 5, 10, 9, 7, 3, 6, \ldots $$ のようになり，$1, 2, \ldots, 10$ がすべて現れる長さ $10$ の列が周期的に繰り返されます． 原始根は $p$ を法とする乗算や指数に関する問題を加算や乗算に