フェルマーの小定理より、素数pに対して、(a,p)=1ならばが成り立つ。
しかしながら、p-1よりも小さなkでを満たすような数aもあるかもしれない。
このようにaをk乗して初めて法pの世界で1になる、即ちを満たすkを、pを法とするaの位数（order）と呼ぶ。これを次のように書く。
[定義]p：素数とする。
このとき、となるgを、pの原始元（原始根・生成元）という。
つまり、gをp-1乗して初めて1になるような元のことである。
例：p=5
原始元はp-1となる値aということなので、4（＝p-1=5-1)となる値は2と3である（括弧の中の値が原始元と覚えておけばよい）。つまり、の原始元は2,3ということになる。
[系]p：素数とする。
「a：原始元」⇒「」
一般に、必ずしも素数でない正整数m、mと素なaに対して、次が成り立つ。
これをオイラーの定理と呼ぶのであった。
先ほどと同様に考えて、aを何乗かすると法mの世界で1になる。
そこで、が成り立つような最小の正整数kを、mに関するaの位数という。これを
と表記する。
そして、正整数mに対しても原始元が定義できる。
[定義]を満たすgを、mの原始元と呼ぶ。
例：4の原始元は？
まず、である。
原始元の候補は1,2,3であり、それらが乗したときに1になるものが4の原始元である。
ゆえに、4の原始元は3のみである。 ◇
原始元は元の位数と密接な関係を持っている。
[定理]奇素数pに関するaの位数q（=ordp(a)）は、p-1の約数である。
即ち、
[考察]
[証明]背理法を用いる。位数がp-1を割り切らないと仮定する。すると、
と書ける。
また、次のような計算ができる。
（∵フェルマーの小定理）
（∵元の位数の定義より、
）
よって、が成り立つ。
しかし、r＜qであるが、qの最小性（位数の定義）に反するので矛盾。
ゆえに、位数はp-1を割り切る。 □
法が素数べきのときに、原始元が存在することを示す。
[定理]n=pe、pは奇素数、e≧1のとき、法nに関する原始元が存在する。
[証明]
[1]e=1のとき、[定理]「pが素数のとき、法pに関する原始元が存在する」より、題意が成り立つ。
[2]e＞1のとき
法pe-1に関する原始元が存在すると仮定して、法peに関する原始元が存在することを示す。
仮定と（正整数mの）原始元の定義より、を満たす整数aが存在する。
これは次のように展開できる。
（∵オイラー関数の性質）
よって、[定理]「nが自然数、aをnと互いに素な整数とする。このとき、次は同値である。
[1]
[2]以下の2条件が成り立つ。
(a)sは自然数で、
(b)ならば、mはsの倍数である」より、次が成り立つ。
また、法peに関するaの位数をmとすると、次が成り立つ。
（∵???） ←(**)
つまり、(*),(**)より、法peに関するaの位数であるmはsの倍数、即ちmはの倍数である。
一方、[系]「はφ(n)の約数である」より、法peに関するaの位数は、
の約数である。
よって、法peに関するaの位数は、の倍数、かつ
の約数である。
つまり、法peに関するaの位数は、である。
(i)法peに関するaの位数がの場合、aが法peに関する原始元である。
(ii)法peに関するaの位数がの場合
[定理]「nを自然数とする。
(1)のとき、
である。ただし、dはsとeの最大公約数である。
(2)のとき、
である」の(1)より、次が成り立つ。
ここで、が示されれば、(p-1,pe-1)=1なので、上記定理の(2)と(***)より、次が成り立つ。
つまり、より、peの原始元は存在し、
の原始元である。
後は、を示す。
（∵[定理]「pが奇素数、e≧1のとき、次が成り立つ。
」より）
よって、[定理]「nが自然数、aをnと互いに素な整数とする。このとき、次は同値である。
[1]
[2]以下の2条件が成り立つ。
(a)sは自然数で、
(b)ならば、mはsの倍数である」の[2]より、次が成り立つ。
そこで、次のようにおく。
（∵元の位数の定義）
ここでm＜e-1であると仮定すると、次のように展開を進めることができる。
（∵m＜e-1より、m+2≦e）
（∵[定理]「pが奇素数、e≧1のとき、次が成り立つ。
」より）
これは矛盾する。
よって、m=e-1である。
したがって、が成り立つ。 □
次に、nが2のべきの場合を考える。
[定理]n=2e、e≧3、aが奇数のときに、次が成り立つ。
[証明]
[1]e=3の場合、、即ち
を示す。
すべてのaについて、元の位数を列挙すると次の通りである。
いずれも2以下であり、、題意が成り立つ。
[2]e＞3の場合
と仮定する。
このとき、次が成り立つ。
（∵仮定）
←(*)
このとき、は次のように展開できる。
（∵(*)）
（∵e＞3）
[定理]「「」⇒「
」」より、
である。
したがって、、題意が成り立つ。 □
[定理]nがpe,2pe,（pは奇素数、e≧1）,1,2,4のときのみ、法nに関する原始元が存在する。
[証明]
[1]n=1のとき
一方、であり、
を満たすa=1が原始元である。
[2]n=2のとき
一方、であり、
を満たすa=1が原始元である。
[3]n=4のとき
一方、であり、
を満たすa=3が原始元である。
[4]n=pe（pは素数、e≧1）のとき
[定理]「n=pe、pは奇素数、e≧1のとき、法nに関する原始元が存在する」から明らかである。
[5]n=2pe（pは奇素数、e≧1）のとき
[4]より、法peに関する原始元が存在し、原始元をaとすると、次が成り立つ。
（∵法peに関する原始元が存在し、原始元をaとする）
（∵元の位数の定義より）
（∵[定理]「nが自然数、aをnと互いに素な整数とする。このとき、次は同値である。
[1]
[2]以下の2条件が成り立つ。
(a)sは自然数で、
(b)ならば、mはsの倍数である」）
ここで、なので、
となり、aは法n=2peに関する原始元である。
[6]それ以外のとき
[定理]「m1,m2を2より大きな互いに素なし自然数とし、n=m1m2とする。
このとき、nと互いに素な整数aについて、次が成り立つ。
」より、n=m1m2（m1,m2は3以上の互いに素な自然数）のときは、常に
が成り立つ」より、
になり、原始元は存在しない。 □
の個数は2個であることは確認した。このようにすべての原始元を調べて個数をカウントするのでは時間がかかる。実は、原始元には個数に関する次のような定理が成り立つ。
[定理]pを奇素数とする。このとき、の原始元、即ちpの原始元はφ(p-1)個である。ただし、φ(・)はオイラー関数である。
[観察]定理を証明する前に、数値例で定理の妥当性を確認してみる。
p=19のとき、pの原始元（φ(p)=p-1乗ではじめて1になるもの）は、2,3,10,13,14,15の6個である。
一方、φ(p-1)=φ(19-1)=φ(18)=φ(2・32)=18(1-1/2)(1-1/3)=6
よって、（pの原始元の個数）＝φ(p-1)＝6が成り立つことが観察できた。
[証明]
また、「gk：原始元」⇔「(k,p-1)=1」
よって、原始元の数＝φ（p-1)になる。 □
[別証]d|p-1として、位数dである整数bが存在したとする。
すると、が成り立つ。
よって、mod pでbのべき乗を作ると、
…(*)
となる。
これらはすべてd乗すると、1に一致する（∵）。
よって、方程式の根であり、ラグランジュの定理より、d次の合同方程式の解の個数はdを超えないので、(*)がすべてである。
次に、(*)の中で「位数がdである数」の個数を調べる。ここで、bjの位数をeとおく。
すると、より、
（∵[定理]「m：正整数、(a,m)=1とする。このとき、
ならば、
」より）
（∵証明最初の仮定より、
）
（∵(j,d)=g,j/g=j1,d/g=d1,(j1,d1)=1とおく）
（∵両辺をdで割った）
…(**)（∵(j1,d1)=1の状況で両辺をj1で割った）
他方、bの位数はdより、
（∵j=gj1）
（∵gd1=d）
∴
（∵bjの位数をeとおいていたので）
…(***)
(**)(***)より、e=d1である。
よって、
（∵仮定）
（∵
）
bjの位数がdとなるための条件は、j＜dより、(j,d)=1である。
のうちで、この条件を満たすものは個である。
jはp-1のどの約数についても同様である。
特に、位数p-1となる数、即ちpの原始元はφ(p-1)個である。 □
[考察]で考えると、それに含まれる原始元はφ(φ(n))になる。まず
の要素の個数はφ(n)になり、それにφを計算するので、全体としてφ(φ(n))個になる。 ◇
以上のことから、原始元は全体の数から見てもたくさんあることがわかる。は要素数がp-1個なので、その中の原始元はφ(p-1)個になる。例えば、p=7で考えると、次のように原始元の個数を計算できる。
ところで、が成り立つ。
p=19のとき、p-1=18の約数を位数に持つ個数を調べる。
| #(位数が1の個数)=#{1}=1 | φ(1)=1 |
| #(位数が2の個数)=#{18}=1 | φ(2)=1 |
| #(位数が3の個数)=#{7,11}=1 | φ(3)=2 |
| #(位数が6の個数)=#{8,12}=1 | φ(6)=2 |
| #(位数が9の個数)=#{4,5,6,9,16,17}=1 | φ(9)=6 |
| #(位数が18の個数)=#{2,3,10,13,14,15}=1 | φ(18)=6 |
表の左の列の数の和は18であり、右の列の和の和は18になり、一致していること確認できる。
φ(n)はnによって異なるが、平均すると（≒0.6）という事実がある[HW79]。よって、φ(φ(n))は平均すると約0.36ということになる。つまり、全体の36%が原始元として取れるということである。
[定理]
p：素数、g：の原始元とする。
このとき、とおくと、次が成り立つ。
[証明]場合分けして考える。
[1]⊆を示す。
であるから、
は明らかに成り立つ。
[2]⊇を示す。
を示すためには、
を示せばよい。
ここで、各aiがすべて異なれば、が成り立つ。そこで、「i≠j」⇒「ai≠aj」を示せればよい。
背理法を用いる。仮にあるi＞jに対して、「gi (mod p)=g j (mod p)」が成り立つと仮定すると、(g,p)=1よりが得られる。
この左辺の指数部は0＜i-j＜p-1となる。しかし、これはgの位数がp-1であることに反する。よって、矛盾が生じる。 □
例：次の条件のときで考える。
[1]g=2のとき
よって、{a0,a1,a2,a3}={1,2,4,3}={1,2,3,4}が成り立っていることがわかる。
[2]g=3のとき
よって、{a0,a1,a2,a3}={1,3,4,2}={1,2,3,4}が成り立っていることがわかる。
いずれにしても、gの値がいずれにしても定理が必ず成立することが確かめられた。
暗号の世界では原始元が活躍する。そのためコンピュータで効率的に原始元を生成する必要が生じる。例えば、ElGamal暗号などにおいては、大きな素数pに対して、の原始元gを生成する必要がある。
素朴なアプローチは全数探索である。まず、をランダムに選び、次にそれが原始元かどうかを判定すればよい。原始元の定義から、
が成り立てば、gは原始元である。しかし、この方法ではpκの計算量がかかってしまう（κ：ビット数）。指数時間の計算量ではチューリングマシンにとって効率的ではない。
そのため、多項式時間で原始元を判定するような効率のよい方法を考えなければならない。判定アルゴリズムが効率的ならば、ランダムに選択するのも効率的なので、生成という全体で見ても効率的になる。
[補題]
p-1がと素因数分解されたとする。このとき、次が成り立つ。
「gがmod pの原始元である」⇔「（…(*)）」
[証明]矢印の向きを分けて考える。
[1]⇒を示す。
gが原始元であれば、明らかに成り立つ。なぜならば、gが原始元なら、mod pの世界でp-1乗しないと≡1にならないからである。
[2]←を示す。
対偶を使って示す。つまり、示したい主張は「gがmod pの原始元でない」⇒「」（…(**)）である。
gが原始元でないならば、[定理]「∀a;ordp|p-1」より、「ordp(g)|p-1」を満たす。よって、あるm≧2に対して、p-1=ordp(g)×mが成り立つ。
仮定と組み合わせると、次が成り立つ。
よって、qi|mが成り立つ。
このとき、
（∵
）
これは(**)を満たす。 □
例：p=11とする。p-1=10の素因数は2と5である。
[1]（上記の定理を利用して）2が生成元か調べる
どちらの結果も1に一致しないので、2は生成元である。
[2]3が生成元か調べる
1に一致するものがあったので、3は生成元ではない。 ◇
この定理を使うと、(*)をt+1回チェックするだけで、原始元かどうかを判定できることになる。
ところが、この定理は原始元の判定アルゴリズムに利用できそうだが、実際には使うことはできない。なぜならば、ElGamal暗号のときはp=1,024ビットなので、pを素因数分解することは無理である。この定理を使うためには、p-1の素因数分解を知らなければならないため、直接使うことは不可能である。
そこで、実装においては次のように行う。
1：qをランダムに選び、素数判定アルゴリズムで判定する。普通にMiller-Rabinアルゴリズムを使えばよい。
2：次にp=2q+1を計算し、このpが素数かどうかを素数判定アルゴリズムで判定する。
3：もしp,qどちらも素数ならば、p-1の素因数は2とqとすでに知っているので、上記の原始元かどうかを判定するアルゴリズムを利用できる。図の原始元生成アルゴリズムはgの選択と原始元判定アルゴリズムの組合わせを意味としている。
ちなみに、たった2つの素因数なので、と
のたった2回のチェックのみで原始元の判定ができる。もし両方の合同式が満たされない場合は、gはmod pの原始元となるわけである。
