この左辺の指数部は0<i-j<p-1となる。これはgの位数がp-1であることに反する。よって、矛盾が生じる。例:次の条件のときで考える。5)よって、{a0,a1,a2,a3}={1,2,4,3}={1,2,3,4}が成り立っていることがわかる。5)よって、{a0,a1,a2,a3}={1,3,4,2}={1,2,3,4}が成り立っていることがわかる。いずれにしても、gの値がいずれにしても定理が必ず成立することが確かめられた。暗号の世界では原始元が活躍する。そのためコンピュータで効率的に原始元を生成する必要が生じる。原始元gを生成する必要がある。素朴なアプローチは全数探索である。ランダムに選び、次にそれが原始元かどうかを判定すればよい。成り立てば、gは原始元である。この方法ではpκの計算量がかかってしまう(κ:ビット数)。指数時間の計算量ではチューリングマシンにとって効率的ではない。そのため、多項式時間で原始元を判定するような効率のよい方法を考えなければならない。判定アルゴリズムが効率的ならば、ランダムに選択するのも効率的なので、生成という全体で見ても効率的になる。素因数分解されたとする。このとき、次が成り立つ。(...(*))」[証明]矢印の向きを分けて考える。gが原始元であれば、明らかに成り立つ。pの世界でp-1乗しないと≡1にならないからである。