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$ を法とする乗算や指数に関する問題を加算や乗算に関する問題に置き換えるための強力な道具です．また，競技プログラミングにおける重要なトピックとしては，高速フーリエ変換（FFT，NTT）を理解する上で重要です．

2. 前提知識

AtCoder Algorithm Lectures における次の講座の内容を前提とします．

3. 位数と原始根

本記事を通して，$p$ と書けば特に断らずとも素数を表すこととします．

【定義 1】

$\mathbb{F}_p$ の元であって $0$ でない全体を $\mathbb{F} _ p ^ {\times}$ と書く．これを $\mathbb{F}_p$ の乗法群（multiplicative group）という．

参考：群について

$\mathbb{F} _ p ^ {\times}$ の元同士で乗算・除算を行うことができます．このことは代数学の用語で $\mathbb{F} _ p ^ {\times}$ は群（group）であると表されます．（形式的には群とは，集合と二項演算の組であって，単位元や逆元の存在などの条件を満たすものとして定義されます）．

本記事では群に対する理論を展開することはありません．ただし，位数の定義や基本的な性質は群に一般化できるので，興味のある方は確認してみてください．なお，原始根の存在定理は一般の群では成り立ちません．

【定義 2】

$a\in \mathbb{F}_p^{\times}$ とする．$a ^ m=1$ を満たす正整数のうち最小のものを $a$ の位数（order）という．

なお，Fermat の小定理より位数は定義できて，$p-1$ 以下の正整数である．

【補題 3】

$a \in \mathbb{F}_p^{\times}$ の位数を $m$ とするとき，次が成り立つ．

非負整数 $n_1,n_2$ について，$a ^ {n_1} = a ^ {n_2}$ であることと $n_1\equiv n_2\pmod{m}$ は同値である．
非負整数 $n$ について $a ^ n = 1$ であることと，$n$ が $m$ の倍数であることは同値である．
位数 $m$ は $p-1$ の約数である．
$a ^ 0, a ^ 1, \ldots, a ^ {m-1}$ はすべて異なる．

1 を示します．$n_1\leq n_2$ として示せばよいです．$n_2-n_1$ を $m$ で割ったときの商を $q$，余りを $r$ とします．（特に $0\leq r < m$ です．）

$n_2-n_1=qm+r$ より $a ^ {n_2-n_1} = (a ^ {m}) ^ q\cdot a ^ r=1 ^ q\cdot a ^ r=a ^ r$ なので，$a ^ {n_1}=a ^ {n_2}$ と $a ^ r=1$ は同値です．$0\leq r < m$ であることと位数の定義から，これは $r=0$ と同値です．以上で 1 が示されました．

2 は 1 において $n_2=0$ とすれば示されます．3 は 2 において $n=p-1$ として Fermat の小定理を用いると示されます．4 も 1 から分かります． $\blacksquare$

【補題 3】より，等比数列 $a ^ 0, a ^ 1, a ^ 2, \ldots$ は，$m$ 種類の値を周期 $m$ で繰り返すことが分かります．ここに $0$ を除くすべての値が現れるというのが原始根の定義です．

【定義 4】（原始根）

$g\in \mathbb{F}_p^{\times}$ の位数が $p-1$ であるとき，$g$ を原始根（primitive root）という．

$g$ が原始根であるとき，【補題 3】より $g ^ 0, \ldots, g ^ {p-2}$ は相異なるため，任意の $a\in \mathbb{F}_p^{\times}$ は $a=g ^ i$ と表せます．$a_1 = g ^ {i_1}, a_2 = g ^ {i_2}$ であるとき $a_1a_2=g ^ {i_1+i_2}$ であることなどから，$\mathbb{F} _ p ^ {\times}$ の掛け算に関する問題を $\mathbb{Z}/(p-1)\mathbb{Z}$ の加算 $i_1+i_2$ に関する問題に置き換えて調べられるようになります．そのような応用例は，6 節で扱います．

3.1. 具体例

$p=7$ とするとき，各 $a\in \mathbb{F} _ p ^ {\times}$ のべき乗は次のようになります．

$n$	$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$
$1 ^ n$	$1$	$1$	$1$	$1$	$1$	$1$	$1$	$1$	$1$	$1$
$2 ^ n$	$1$	$2$	$4$	$1$	$2$	$4$	$1$	$2$	$4$	$1$
$3 ^ n$	$1$	$3$	$2$	$6$	$4$	$5$	$1$	$3$	$2$	$6$
$4 ^ n$	$1$	$4$	$2$	$1$	$4$	$2$	$1$	$4$	$2$	$1$
$5 ^ n$	$1$	$5$	$4$	$6$	$2$	$3$	$1$	$5$	$4$	$6$
$6 ^ n$	$1$	$6$	$1$	$6$	$1$	$6$	$1$	$6$	$1$	$6$

このことから，$a=1,2,3,4,5,6$ の位数は順に $1,3,6,3,6,2$ となります．また，原始根は $3$ と $5$ の $2$ 個です．

$p=11$ とするとき，$g=2$ は原始根となります．

$n$	$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
$2 ^ n$	$1$	$2$	$4$	$8$	$5$	$10$	$9$	$7$	$3$	$6$	$1$

$p=13$ とするとき，$g=2$ は原始根となります．

$n$	$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$	$11$	$12$
$2 ^ n$	$1$	$2$	$4$	$8$	$3$	$6$	$12$	$11$	$9$	$5$	$10$	$7$	$1$

$p=17$ とするとき，$g=3$ は原始根となります．

$n$	$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$	$11$	$12$	$13$	$14$	$15$	$16$
$3 ^ n$	$1$	$3$	$9$	$10$	$13$	$5$	$15$	$11$	$16$	$14$	$8$	$7$	$4$	$12$	$2$	$6$	$1$

プログラムを書けば，次を確かめることもできます．

$p=998244353$ とするとき $g=3$ は原始根となる．
$p=1000000007$ とするとき $g=5$ は原始根となる．

4. 原始根の存在証明

4.1. Euler の totient 関数

【定義 5】（Euler の totient 関数）

正整数 $n$ に対して，$0$ 以上 $n-1$ 以下の整数のうち $n$ と互いに素なものの個数を $\varphi(n)$ と書く．$\varphi$ を Euler の totient 関数（Euler's totient function）という．

小さな $n$ に対する $\varphi(n)$ の値は次の表の通りです．

$n$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
$\varphi(n)$	$1$	$1$	$2$	$2$	$4$	$2$	$6$	$4$	$6$	$4$

$n$ の素因数分解を $n=\prod_{i}p_i^{e_i}$ （ただし $e_i>0$）とするとき，

$$\varphi(n)=n\prod_i\left(1-\frac{1}{p_i}\right)$$

となります．このことは中国剰余定理で証明します．本記事内でこの公式を用いることはありません．

【補題 6】
正整数 $n$ に対して $$\sum_{d\mid n}\varphi(d)=n$$ が成り立つ．ただし，$d\mid n$ は $d$ が $n$ の約数であるということを表す記号であり，左辺はすべての $n$ の約数 $d$ に対する $\varphi(d)$ の総和である．

$d$ を $n$ の約数とするとき，整数 $0\leq x< n$ のうちで $\gcd(n,x)=d$ を満たすものの個数を $a_d$ とします．

$\gcd(n,x)=d$ であるような $x$ は，$0\leq y< n/d$ かつ $\gcd(y,n/d)=1$ を満たす整数 $y$ を用いて $x=dy$ と書けるものです．したがってその個数は $a_d=\varphi(n/d)$ です．

$a_d$ の総和が $n$ であることは明らかなので，$\sum _ {d \mid n}\varphi(n / d) = n$ が成り立ちます．$d$ が $n$ の約数全体を動くとき，$n/d$ も $n$ の約数全体を動くので，$\sum _ {d \mid n}\varphi(d) = n$ が成り立ちます． $\blacksquare$

【補題 7】

$d$ が $p-1$ の約数であるとき，$\mathbb{F} _ p ^ {\times}$ の元であって位数が $d$ であるものの個数は $0$ または $\varphi(d)$ である．

$0$ 個でないとして，$\varphi(d)$ 個であることを示します．$a$ を位数が $d$ であるとします．

このとき，【補題 3】より $d$ 個の数 $a ^ i$ （$0 \leq i < d$）はすべて異なります．また，これらはすべて $x ^ d=1$ を満たします．

$\mathbb{F}_p$ において $d$ 次方程式の解は $d$ 個以下である（素数を法とする多項式【定理 5】）から，$x ^ d=1$ を満たす $x$ はこれら以外には存在しません．

したがって，位数 $d$ の元の個数を求めるには，$a ^ i$ （$0\leq i<d$）のうちで位数 $d$ のものの個数を求めればよいです．

$a ^ i$ の位数は，$mi\equiv 0\pmod{d}$ を満たす最小の正整数 $m$ なので，$\dfrac{d}{\gcd(d,i)}$ です．よって $a ^ i$ の位数が $d$ となるのは $\gcd(d,i)=1$ の場合であり，その個数は $\varphi(d)$ です． $\blacksquare$

【定理 8】（原始根の存在）

$d$ が $p-1$ の約数であるとき，$\mathbb{F} _ p ^ {\times}$ の元であって位数が $d$ であるものの個数は $\varphi(d)$ 個である．特に原始根は $\varphi(p-1)$ 個存在する．

位数 $d$ の元の個数を $a_d$ と書くことにします．【補題 3】より $a_d>0$ となる $d$ は $p-1$ の約数に限られます．また【補題 7】より $p-1$ の約数 $d$ に対して $a_d\leq \varphi(d)$ です．よって【補題 6】より $\sum_{d=1} ^ {p-1} a_d \leq p-1$ となります．

一方で $a_d$ の定義から明らかに $\sum_{d=1}^{p-1}a_d=p-1$ です．したがって上の評価において等号が成り立つため，すべての $p-1$ の約数 $d$ に対して $a_d=\varphi(d)$ が成り立ちます． $\blacksquare$

5. 原始根を求めるアルゴリズム

原始根のひとつを $p$ の簡単な式を使って計算するような公式は知られていません．原始根を求める際には，探索アルゴリズムを利用するのが一般的です．

【命題 9】

$a\in \mathbb{F}_p^{\times}$ に対して，次は同値である．

$a$ は原始根である．
任意の $p-1$ の素因数 $q$ に対して $a ^ {(p-1)/q}\neq 1$．

$a$ が原始根ならば $a ^ {(p-1)/q}\neq 1$ となることは明らかです．逆を示します．

$a$ が原始根でないとすると，その位数は $p-1$ の約数かつ，$p-1$ より小さいです．したがってある $p-1$ の素因数 $q$ が存在して，$a$ の位数は $(p-1)/q$ の約数です．このとき $a ^ {(p-1)/q}= 1$ なので示されました． $\blacksquare$

したがって，次のようなアルゴリズムにより原始根を求めることが可能です．

def find_primitive_root(p):
  Q := distinct prime factors of (p - 1)
  
  def is_primitive_root(a):
    for q in Q:
      if pow(a, (p-1)/q) mod p == 1:
         return False
    return True
  
  while True:
    a := random integer such that 1<=a<p
    if is_primitive_root(a):
      return a

pow(a, (p-1)/q) mod p の部分を繰り返し二乗法により計算すれば，このアルゴリズムの期待時間計算量は，素因数分解に関する部分を除けば

$$\mathrm{O}\left(\frac{p-1}{\varphi(p-1)}\cdot |Q|\log p\right)$$

となります（アルゴリズムが乱択を含むため，期待時間計算量を評価しています）．$|Q|\leq \log_2 p$ であることから，これは $\mathrm{O} \left( \frac{p-1}{\varphi(p-1)} \cdot \log ^ 2 p\right)$ とも書けます．

本記事では解説しませんが，$\frac{p-1}{\varphi(p-1)}=\mathrm{O}(\log\log p)$ であることが知られています（{{aal:素数に関する計算量評価}} 参照）．したがって上のアルゴリズムの期待時間計算量は $\mathrm{O} \left( ( \log \log p)(\log ^ 2 p) \right)$ です．なおアルゴリズム全体では，通常 $p-1$ を素因数分解する部分の計算量が支配的となります．

乱択をやめて $a=1,2,3,\ldots$ の順に探索するという方法でも（期待時間計算量は悪化するものの）十分高速である場合が多いです．例えば $p\leq 10 ^ 9$ ならば最小原始根は $151$ 以下であることが確かめられるので，$1\leq a\leq 151$ を探索すれば解が出力されます．

6. 原始根の応用

原始根の応用例のうち代表的なものをいくつか紹介します．

6.1. 原始根を用いたべき乗の計算

次の問題を考えます．

【問題 10】

$p$ を素数とします．$Q$ 個のクエリに答えてください．

クエリでは，非負整数 $a, n$ が与えられるので，$a ^ n\bmod p$ を出力してください．

この問題は $\mathrm{O}(p+Q)$ 時間で解くことができます．まず，原始根をひとつ求めて $g$ としておきます．

次に $g ^ 0,g ^ 1,\ldots,g ^ {p-2}\bmod p$ を計算してテーブルに格納しておきます．さらに各 $1\leq a\leq p-1$ に対して $a\equiv g ^ i\pmod{p}$ となる $i$ も求めておきます．これらの事前計算は $\mathrm{O}(p)$ 時間で行えます．

クエリは $a\equiv 0\pmod{p}$ なら自明です．そうでないときには $a\equiv g ^ i\pmod{p}$ となる $i$ をとります．さらに $r=(in\bmod (p-1))$ とすれば，$a ^ n\equiv g ^ {in}\equiv g ^ r\pmod{p}$ となります．この値をテーブルから読み取ることで，クエリにはクエリごとに $\mathrm{O}(1)$ 時間で答えられます．$\blacksquare$

この解法は，$\mathrm{O}(p)$ 時間の事前計算を要するため，$p=10 ^ 9$ 程度が前提となる問題では使えず，競技プログラミングにおける実用機会は少ないです．（より高速な事前計算により $a=g ^ i$ となる $i$ を $\mathrm{O}(1)$ 時間で求める方法もありますが，本記事では解説しません．）ただし，以下の応用例ではこの計算方法が前提となるので，よく理解しておいてください．

6.2. $p$ を法とする $k$ 乗数

【定義 11】

$a\in \mathbb{F}_p$ が $\boldsymbol{k}$ 乗数であるとは，$a=b^k$ を満たす $b\in \mathbb{F}_p$ が存在することをいう．

$k=2$ の場合には平方剰余（quadratic residue）であるともいう．平方剰余でないものを平方非剰余（quadratic nonresidue）という．

【定理 12】

$g\in \mathbb{F}_p^{\times}$ を原始根とし，$a=g ^ i\in\mathbb{F}_p^{\times}$ （$0\leq i < p-1$）とする．$k$ を非負整数とするとき，次は同値である．

$a$ は $k$ 乗数である．
$i$ は $\gcd(k,p-1)$ の倍数である．
$k'=(p-1)/\gcd(k,p-1)$ とするとき，$a ^ {k'}=1$．

$\text{1}\implies\text{2}$ を示します．$a$ が $k$ 乗数であるとします．$a=b ^ k$ であるとします．$a\neq 0$ より $b\neq 0$ なので，$b$ も原始根によって $b=g ^ j$ と表せます．すると $g ^ i=a=b ^ k=g ^ {jk}$ となります．したがって $i=(jk\bmod (p-1))$ です．ここから $i$ が $\gcd(k,p-1)$ の倍数であることが分かります．

$\text{2}\implies\text{3}$ を示します．仮定より $i=j\cdot \gcd(k,p-1)$ を満たすような非負整数 $j$ が存在します．このとき $a ^ {k'}=g ^ {ik'}=g ^ {j(p-1)}=1$ となります．

$\text{3}\implies\text{1}$ を示します．$g ^ {ik'}=a ^ {k'}=1$ より $ik'\equiv 0\pmod{p-1}$ です．したがって $i$ は $\gcd(k,p-1)$ の倍数なので，$i\equiv jk\pmod{p-1}$ を満たす非負整数 $j$ が存在します．このとき $b=g ^ j$ とすれば $b ^ k=g ^ {jk}=g ^ i=a$ となるので，$a$ は $k$ 乗数です．

以上で示されました． $\blacksquare$

【系 13】

$k$ を非負整数とする．$\mathbb{F}_p^{\times}$ の元であって $k$ 乗数であるものの個数は，$\dfrac{p-1}{\gcd(k,p-1)}$ である．

【定理 12】より求める個数は $0$ 以上 $p-1$ 未満の $\gcd(k,p-1)$ の倍数の個数であるので，その個数は $\dfrac{p-1}{\gcd(k,p-1)}$ です． $\blacksquare$

なお【系 13】では $0$ を除いて数えていることに注意してください．$0$ も含めると $k$ 乗数の個数は $1+\dfrac{p-1}{\gcd(k,p-1)}$ となります．

特に $k=2$ とした場合の平方剰余について，簡単な性質をまとめておきます．

【系 14】

$p$ が奇素数であるとし，$a,b\in \mathbb{F}_p^{\times}$ であるとする．

$a,b$ が平方剰余であるとき $ab$ は平方剰余である．
$a$ が平方剰余であり，$b$ が平方非剰余であるとき，$ab$ は平方非剰余である．
$a$ が平方非剰余であり，$b$ が平方非剰余であるとき，$ab$ は平方剰余である．
$a$ が平方剰余であることは，$a ^ {(p-1)/2}=1$ と同値である．
$\mathbb{F}_p^{\times}$ の元であって平方剰余・非剰余であるものの個数はどちらも $\frac{p-1}{2}$ である．
$p\equiv 1\pmod{4}$ ならば $-1$ は平方剰余，$p\equiv 3\pmod{4}$ ならば $-1$ は平方非剰余である（平方剰余の第 1 補充則）．

$a=g ^ i$ とすれば，平方剰余・非剰余は $i$ が偶数・奇数のどちらであるかに対応します．このことから 1, 2, 3 が分かります．

4 は【定理 12】で示しました．

5 は平方剰余については【系 13】で示しました．その個数を全体から引くことで平方非剰余の個数も分かります．

6 は 4 から分かります． $\blacksquare$

6.3. $1$ のべき根

Fermat の小定理により任意の $a\in \mathbb{F}_p^{\times}$ は $1$ の $p-1$ 乗根であり，原始根の存在はそれらが等比数列をなすことを意味します．

より一般に，$d$ が $p-1$ の約数のとき，$1$ の $d$ 乗根は $d$ 個あり，それらは等比数列をなします．

【定理 15】

$d$ を $p-1$ の約数とするとき，位数 $d$ の元が存在する．$r$ を位数 $d$ の元とするとき，$1$ の $d$ 乗根，つまり $x^d=1$ を満たす $x\in \mathbb{F}_p$ は $1, r, r^2, \ldots, r^{d-1}$ の $d$ 個である．

さらにこれらを $a_0, a_1, \ldots, a_{d-1}$ とするとき，非負整数 $k$ について次が成り立つ．

$$ \sum_{j=0}^{d-1}a_j^k= \begin{cases} d & (d\mid k)\\ 0 & (d\nmid k) \end{cases} $$

$d$ 次方程式の解が $d$ 個以下であることから $1$ の $d$ 乗根が $1, r, r ^ 2, \ldots, r ^ {d-1}$ の $d$ 個であることが分かります．その $k$ 乗和 $\sum_{j=0} ^ {d-1} r ^ {kj}$ は公比 $r ^ k$ の等比数列の和です．

$R=r ^ k$ とすると，$(1-R)\sum _ {j=0} ^ {d-1} R ^ j = 1 - R ^ d=1-r ^ {kd}=0$ となります．$k\not\equiv 0\pmod{d}$ のときは $R\neq 1$ なので，$\sum_{j=0} ^ {d-1}R ^ j=0$ となります．

$k\equiv 0\pmod{d}$ のときは，$R=1$ なので，$\sum _ {j=0} ^ {d-1} R ^ j = \sum _ {j = 0} ^ {d-1}1=d$ です． $\blacksquare$

【系 16】

$k$ を非負整数とするとき，次が成り立つ．

$$ \sum_{n=1}^{p-1}n^k\equiv \begin{cases} -1& (p-1\mid k)\\ 0& (p-1\nmid k) \end{cases} \pmod{p} $$

【定理 15】において $d=p-1$ とすると分かります． $\blacksquare$

7. 関連問題

ここで挙げた問題は，本記事では扱っていないレベルのアルゴリズムを想定しており，本記事を学んだ段階では正答するのが難しいものも多いので注意してください．

問題について

1 は原始根の個数を求める問題です．

2 は原始根を求めるだけの基本的な問題ですが，$\mathrm{O}(\sqrt{n})$ 時間よりも高速な素因数分解アルゴリズムを前提としています．

3, 4 は原始根を用いて，指数を $p-1$ を法とする乗算に置き換えて考察する問題です．原始根以上に高度な知識は不要ですが，難易度は高めです．なお原始根を用いるとはいっても，具体的に原始根を求める必要はありません．

5 は原始根を用いる解法が想定される解法のひとつです．

6, 7, 8 はほぼ同じ問題で，「$p$ を法とする乗算」を「$p-1$ を法とする加算」に変換するという原始根の考え方を学ぶのに最適な問題のひとつです．ただし，解法では高速フーリエ変換（FFT・NTT）が想定されているため，高速フーリエ変換を学習したあとで取り組むのが良いと思います．

9 は【定理 15】を用いる問題です．

8. まとめ

本記事では，原始根の存在を証明し，その応用例として，特に $k$ 乗数や $1$ の $d$ 乗根などの性質について解説しました．

原始根の応用は，原始根を求めたり，数をそのべき乗として表すという単純なものだけに留まりません．特に，原始根が存在するという事実から，原始根を具体的に求めずとも，$p$ を法とする乗算や指数の性質について様々なことが導かれることが，応用例や関連問題を通して分かると思います．

本記事で扱ったのは素数 $p$ を法とする原始根ですが，原始根は素数べきを法とする場合や，有限体の場合にも一般化される概念です．そのような一般化も AtCoder Algorithm Lectures で解説する予定です．また本記事の内容は，高速フーリエ変換（FFT，NTT）の解説でも前提となります．

9. 参考文献

Wikipedia．指数（初等整数論）．https://ja.wikipedia.org/wiki/指数(初等整数論)．（閲覧日: 2026-04-01）．
Wikipedia．Primitive root modulo n．https://en.wikipedia.org/wiki/Primitive_root_modulo_n．（閲覧日: 2026-04-01）．
37zigen．原始根のアルゴリズム．https://37zigen.com/primitive-root/．（閲覧日: 2026-04-01）．
cp-algorithms．Primitive Root．https://cp-algorithms.com/algebra/primitive-root.html．（閲覧日: 2026-04-01）．

トップページ：AtCoder Algorithm Lectures